ISRO-DEC2017-44

Question

A sorting technique is called stable if

• A. If it takes $O(n\log n)$ time.
• B. It uses divide and conquer technique.
• C. Relative order of occurrence of non-distinct elements is maintained.
• D. It takes $O(n)$ space.

Comments

https://gateoverflow.in/1465/gate1999_1-12

Answer 1

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.

Answer 2

option C

Relative order of occurrence of non-distinct elements is maintained.