Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
Quick Sort
Radix Sort
HeapSort
→ see L8 Heap for full implementation — uses a max-heap, O(N log N), in-place but not cache friendly.
Comparison of Sorting Algorithms
| Algorithm | Approach | No. of Comparisons | Best / Worst Case |
|---|---|---|---|
| Selection Sort | each iteration, find minimum, move to front or Every iteration, find largest element in unsorted region, swap with last element in unsorted region. | (n-1) + (n-2) + … + 1 TAKE NOTE OF WHO U SWAP WITH | Best: - input already in ascending order - algorithm returns after a single iteration in the outer loop - O(n) Worst: - input in descending order - n-1 outer loops required - running time same, O(n^2) |
| Insertion Sort | for each element, pull out, move downwards and insert at correct spot ie. Starting with the second element, shift it to its left until it encounters an element ⇐ it. Repeat for the following elements. | depends where u stop | Best: - array already sorted, hence a[j] > next is always false - no shifting of data necessary, inner loop not executed at all - O(n) Worst: - array reversely sorted, hence a[j] > next is always true - need i shifts for i = 1 to n-1 - insertion always occurs at the front - O(n^2) |
| Bubble Sort | comparisons between A[i] and A[i+1] up to last 2 unsorted | (n-1) + (n-2) + … + 1 | [improved version] Best: - input already in ascending order - algorithm returns after single iteration in the outer loop - O(n) Worst: - input in descending order - n-1 iterations in the outer loop needed - O(n^2) running time same |
| Merge Sort | keep halving until individual elements, sort and merge into subarray of 2, then 4, until n/2 and n | O(nlogn) — divide-and-conquer, uses auxiliary array (compare with HeapSort which is in-place) | |
| Radix Sort | Treat each element as a character string. Starting with the least significant digit (character), group each element based on that digit. Repeat for the remaining digits. | O(d*n) - d = max number of digits of the n numeric strings in the array - if d is fixed or bounded: O(n) | |
| Quick Sort | select a pivot, partition the array into two subarrays (elements smaller than the pivot go to the left, larger to the right), and recursively apply the same logic to the subarrays. ie. Choose pivot (first element in this course), divide array into two parts ( =p), quick sort on each of those parts. | Best: - partition always splits array into 2 equal halves - depth of recursion is logn - each level takes n or fewer comparisons - O(n log n) Worst: - worst case is rare, and on average, we get some good splits and bad splits Average: - O(n log n) |