Sorting algorithms: implementation and comparison
Implementation:
Implementation of 10 sorting algorithms can be found here, including
- SelectionSort
- InsertSort
- ShellSort
- BubbleSort
- HeapSort
- QuickSort
- MergeSort
- CountingSort
- RadixSort
- BucketSort
Animation for above soring algorithms can be found here.
Comparison:
| Algorithm | Average Time | Worst Time | Best Time | Stable? | Auxiliary Space | Constraints | |:——–:|:——–:|:——–:|:——–:|:——–:|:——–:|:——–:| | SelectionSort | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(\checkmark\) | \(C\) | | | InsertSort | \(O(n^2)\) | \(O(n^2)\) | \(O(n)\) | \(\checkmark\) | \(C\) | | | ShellSort | N/A | N/A | N/A | x | \(C\) | | | BubbleSort | \(O(n^2)\) | \(O(n^2)\) | \(O(n^2)\) | \(\checkmark\) | \(C\) | | | HeapSort | \(O(nlogn)\) | \(O(nlogn)\) | \(O(nlogn)\) | x | \(C\) | | | QuickSort | \(O(nlogn)\) | \(O(n^2)\) | \(O(nlogn)\) | x | \(C\) | | | MergeSort | \(O(nlogn)\) | \(O(nlogn)\) | \(O(nlogn)\) | \(\checkmark\) | \(n\) | | | CountingSort | \(O(n+k)\) | \(O(n+k)\) | \(O(n+k)\) | \(\checkmark\) | \(n+k+C\) | non-negative and within some range| | RadixSort | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(\checkmark\) | \(n+k+C\) | non-negative| | BucketSort | \(O(n)\) | \(O(n)\) | \(O(n)\) | \(\checkmark\) | \(2n+C\) | elements distribute in buckets evenly and independent |
Note: \(C\) is a small constant; \(k\) is the max element; \(n\) is the number of total elements. N/A means it depends on selection of increment value.