Question
Which Of The Given Sorting Method Is Stable?
a) Selection sort
b) Quick sort
c) Binary insertion sort
d) Heap sort
Answer
Answer is C . Binary insertion sort
Explanation
Stable Sorting: A sorting algorithm is said to be stable if two objects with equal values appear in the same order in sorted output as they appear in the input data set. For eg:
Binary insertion sort is a sorting algorithm similar to insertion sort, but instead of using linear search as used in insertion sort to find the position where the element should be inserted, binary search is used . Thus, reducing the comparison for inserting from O(N) to O(log N).
The relative order of same value element is maintained as binary search returns the position to be inserted in same order as it appears in unsorted array.If a same element index is after the other same element one, the former one will placed after sorted array making it stable sort.
Other stable Sorting algorithms include: Bubble Sort, Insertion Sort, Merge Sort, Count Sort etc.
Conclusion
If two objects with equal values appear in the same order in sorted output as they appear in the input data set, it is called stable sort. To answer which of the given sorting method is stable: Binary insertion sort is stable sorting algorithm
Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!
