Stability in sorting algorithms:
Background:
Background:
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.
Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
Definition:
Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.
Definition:
A "stable" sorting algorithm keeps the items with the same
sorting key in order.
Suppose we have a list of 5-letter words:
peach straw apple spork
Stable-sorting by the first letter gives us:
apple peach straw spork
In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since 'straw' appears before 'spork' in the input, it also appears before 'spork' in the output).
We could sort the list of words using this algorithm: stable sorting by column 5, then 4,then 3, then 2, then 1. In the end, it will be correctly sorted. Convince yourself of that. (bythe way, that algorithm is called radix sort)
Suppose we have a list of 5-letter words:
peach straw apple spork
Stable-sorting by the first letter gives us:
apple peach straw spork
In an unstable algorithm, straw or spork may be interchanged, but in stable sort, they stay in the same relative positions (that is, since 'straw' appears before 'spork' in the input, it also appears before 'spork' in the output).
We could sort the list of words using this algorithm: stable sorting by column 5, then 4,then 3, then 2, then 1. In the end, it will be correctly sorted. Convince yourself of that. (bythe way, that algorithm is called radix sort)
No comments:
Post a Comment