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.
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.
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.
Stable and Unstable sorting algorithms
- Bubble Sort Java Program
- Selection Sort Java Program
- Bucket Sort Java Program
- Radix Sort Java Program
- Tree Sort Java Program
- What isIn-place Algorithm
- Convert Date to String in Java
- Java Program to Count Number of Words in a String
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