Wednesday, 19 July 2017

Algorithms | what is the difference between a stable and unstable sort?

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. Whereas a sorting algorithm is said to be unstable if there are two or more objects with equal keys doesn’t appear in the same order before and after sorting.

This is an example of stable sorting here 26 appears twice at position 6 and 8 and their order is preserved in unsorted and sorted array i.e. element 26 at position 6 appear first in the unsorted and sorted array (before and after sorting).

Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort and some algorithms like Heap Sort and Quick Sort are not stable.


There can be sorting algorithm specific ways to make it stable, but in general, any comparison based sorting algorithm which is not stable by nature can be modified to be stable by changing the key comparison operation so that the comparison of two keys considers the position as a factor for objects with equal keys.

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...