Card 11/ 11
Recap: Elementary Sorting
Three ways to grow a sorted part, their counts on each input, and the one that adapts.
Elementary sorting comes down to the nine ideas below, each listed with the card that covers it. One picture holds them together: every member grows a sorted part by one item per pass, and what tells the three apart is where that item comes from and how far it moves.
| The idea | Where |
|---|---|
| All three grow a sorted part one item per pass; stable, in place and adaptive are the properties that tell sorts apart | Elementary Sorts: Growing a Sorted Part One Item at a Time |
| Bubble sort carries the largest unsorted item right by swapping neighbours, one swap per inversion, and stops after a pass with no swaps | Bubble Sort: Swapping Neighbours Until Nothing Moves |
The swapped flag is the whole early exit; TypeScript's sort() with no comparator compares numbers as text | Bubble Sort in Python, Java and TypeScript |
| Selection sort scans for the smallest remaining item: n(n − 1)/2 comparisons on every input, at most n − 1 swaps, and not stable | Selection Sort: Taking the Smallest of What Remains |
| Only selection sort's swap count changes with the input; Heapsort replaces its scan with a heap | Selection Sort in Python, Java and TypeScript |
| Insertion sort shifts larger items right to open a gap, one shift per inversion, so nearly sorted input costs close to O(n) | Insertion Sort: Sliding Each Item Into Place |
Stopping at an item equal to the key keeps insertion sort stable; bisect.insort finds the place in O(log n) but still shifts | Insertion Sort in Python, Java and TypeScript |
| On the same inputs the counts separate the three, and library sorts keep insertion sort for short runs | Bubble vs Selection vs Insertion Sort |
| Without the no-swap check, bubble sort makes n(n − 1)/2 comparisons even on sorted input | Expecting an O(n) Best Case From a Bubble Sort Without the Early Exit |
The costs to keep are these, for an array of n items.
| Sort | Best case | Worst case | Most moves | Stable |
|---|---|---|---|---|
| Bubble sort | O(n), with the early exit | O(n²) | n(n − 1)/2 swaps | Yes |
| Selection sort | O(n²) | O(n²) | n − 1 swaps | No |
| Insertion sort | O(n) | O(n²) | n(n − 1)/2 shifts | Yes |
Together they let you trace each elementary sort by hand, count its comparisons and moves on a given input, write it in Python, Java and TypeScript, and pick insertion sort when the data is small or nearly sorted.
← → move through sections and cards