Tuesday, 27 February 2018

What is stable sorting algorithm in data structures

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

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents