Register

ISRO-DEC2017-44

• edited by
1,434 views
3 votes
3 votes

A sorting technique is called stable if

  1. If it takes $O(n\log n)$ time.
  2. It uses divide and conquer technique.
  3. Relative order of occurrence of non-distinct elements is maintained.
  4. It takes $O(n)$ space.
• edited by
User Avatar

2 Answers

Best answer
4 votes
4 votes

Answer is C

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.

  • Merge sort, Insertion sort, selection sort etc are stable
  • Heap Sort, Quick Sort and Shell sort are unstable.

Is there any advantage in implementing stable sort?

  • You have a list with information about destination of the flight and departure time.
  • You first sort the list based on time. You then sort it based on destination.
  • If the second sort is stable we now have all flights bound to same destination together and in increasing order of departure time.
• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
gatecse asked Dec 17, 2017
3,355 views
ISRO-DEC2017-50
The characters of the string $\text{K R P C S N Y T J M}$ are inserted into a hash table of the size of size $10$ using a hash function $h(x)=(ord(x)-ord(A)+1)$ $mod$ $10$ If linear probing is used to resolve collisions, then the following insertion causes the collision $Y$ $C$ $M$ $P$
The characters of the string $\text{K R P C S N Y T J M}$ are inserted into a hash table of the size of size $10$ using a hash function$h(x)=(ord(x)-ord(A)+1)$ $mod$ $10$...
User Avatar
1 votes
1 votes
1 answer
2
gatecse asked Dec 17, 2017
1,871 views
ISRO-DEC2017-48
Quick-sort is run on $2$ inputs shown below to sort in ascending order : $1,2,3\ldots n$ $n,n-1,n-2\ldots 1$ Let $C$1 and $C2$ be the number of comparisons made for A and B respectively. Then, $C1>C2$ $C1=C2$ $C1<C2$ Cannot say anything for arbitrary $n$
Quick-sort is run on $2$ inputs shown below to sort in ascending order :$1,2,3\ldots n$$n,n-1,n-2\ldots 1$Let $C$1 and $C2$ be the number of comparisons made for A and B ...
User Avatar
4 votes
4 votes
1 answer
3
gatecse asked Dec 17, 2017
1,723 views
ISRO-DEC2017-20
Match the following and choose the correct answer for the order $A,B,C,D$ ... -s, c-p, d-q a-r, b-p, c-s, d-q a-q, b-s, c-p, d-r a-s, b-p, c-q, d-r
Match the following and choose the correct answer for the order $A,B,C,D$$$\begin{array}{|ll|ll|}\hline \text{A.} & \text{Strassen matrix multiplication} & \text{p.} & ...
User Avatar
3 votes
3 votes
2 answers
4
gatecse asked Dec 17, 2017
3,028 views
ISRO-DEC2017-18
Consider the recurrence equation $T(n) =\begin{cases} 2T(n-1), & \text{if }n>0 \\ 1, & \text{otherwise} \end{cases}$ Then $T(n)$ is (in $big\, O$ order) $O(n)$ $O(2^n)$ $O(1)$ $O(\log n)$
Consider the recurrence equation$T(n) =\begin{cases}2T(n-1), & \text{if }n>0 \\1, & \text{otherwise}\end{cases}$Then $T(n)$ is (in $big\, O$ order)$O(n)$$O(2^n)$$O(1)$$O(...
User Avatar
Link Copied!