Sorting Algorithms Summary
Bubble sort, insertion sort, selection sort, quick sort, heap sort, merge sort, counting sort, bucket sort and radix sort.
Comparison-Based Sorting Algorithms
- Bubble sort algorithm
- Insertion sort algorithm
- Selection sort algorithm
- Quick sort algorithm
- Heap sort algorithm
- Merge sort algorithm
Non Comparison-Based Sorting Algorithms
Time and Space Complexity
Stability
Equal elements have the same order in the input and output if a sorting algorithm is stable.
In below demos, a and b are used to denoted the order of value 2.
Why Selection sort is not stable?
Selection sort works by selecting the smallest element and swapping it with the first element in the unsorted subarray. At the first round, we find the 1 is the least element and swap it with 2a. That way, the relative order of 2a and 2b is changed.
Why Quick sort is not stable?
Quick sort is not stable because it may rearrange equal elements/keys. Supposed that we pick 2a as pivot, values less than or equal to the pivot are moved to the left subarray. The equal element, 2b, is rearranged to the left of 2a. Thus, the original order of 2a and 2b is not preserved.
Why Heap sort is not stable?
When heap sort sorts elements in ascending order, it swaps the largest element at root with the last element in the the heap. In below example, 2a is picked first and put into the back of sorted array. Therefore, we get 2b before 2a in the sorted output.