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.