Which Of The Given Sorting Method Is Stable?
a) Selection sort
b) Quick sort
c) Binary insertion sort
d) Heap sort
Answer is C . Binary insertion sort
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.
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