What is stable sorting algorithm in data structures
What is stable sorting algorithm?
A sorting algorithm is said to be stable if two or more
elements with equal keys (values) appear in the same order in sorted output as
they appear in the unsorted input array.
Sorting stability means that records with the same key
retain their relative order before and after the sort.
Example:
Consider the following list of keys which is unsorted.
|
Index
Values/Keys
|
0
chair
|
1
table
|
2
computer
|
3
keyboard
|
4
pen
|
Let us assume that we sort the given array using the
key’s (value’s) first letter in ascending alphabetical order. Then the result
would be as follows;
|
Index
Values/Keys
|
0
chair
|
1
computer
|
2
keyboard
|
3
pen
|
4
table
|
Here, you can see that the first letter of the keys chair and computer
are same. In the unsorted input the key chair comes before computer.
Also, after sorting, chair comes before computer.
Though they are sorted, their order of appearance has not changed. So the
sorting algorithm is said to be a stable algorithm.
List of stable
sorting algorithms:
Bubble sort
Insertion sort
Merge sort
Radix sort
List of unstable
sorting algorithms
Quick sort
Heap sort
Selection sort
Shell sort
***********
stable sorting in data structures
example for stable sorting algorithm
stable vs non-stable algorithms
when do we need stable sort algorithms
how to find stable sort algorithm
list of stable and not-stable sorting algorithms
No comments:
Post a Comment