Advanced Database Management System - Tutorials and Notes: What is stable sorting algorithm in data structures

Search Engine

Please visit, subscribe and share 10 Minutes Lectures in Computer Science

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

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