April 20, 2022

Stable and Unstable Sorting Algorithms

While reading about different sorting algorithms you would have come across the terms stable sorting algorithms and unstable sorting algorithms. In this post we’ll see what is the difference between stable and unstable sorting algorithms.

Stable sorting algorithm

A sorting algorithm is said to be stable if the order of the same values in the output remains the same as in input array.

stable sorting algorithm

This is an example of stable sorting, element 12 appears twice at index 5 and at index 7. In the output array after sorting is done the order is maintained 12 which was at index 5 appears first and 12 which was at index 7 appears later.

Unstable sorting algorithm

In an unstable sorting algorithm the ordering of the same values is not necessarily preserved after sorting.

Unstable sorting algorithm

Here you can see that the ordering for the same element 12 is not maintained after sorting.

Stability with key, value pair

Application of stability becomes more important when we have key value pairs where keys can be duplicated.

For example suppose records with timestamps are stored in an array as they arrive, so the records are in order of the timestamp in the array. Now you want to sort on cities. If an unstable sort is used to do so the records for each city may not necessarily be in order by timestamp after the sort.

Difference between stable and unstable

Stable and Unstable sorting algorithms

Sorting algorithms which are considered stable are- Insertion sort, Merge Sort, Bubble Sort

Sorting algorithms which are not considered stable are- Selection sort, Shellsort, Quicksort, Heapsort

That's all for the topic Stable and Unstable Sorting Algorithms. If something is missing or you have something to share about the topic please write a comment.

You may also like

No comments:

Post a Comment