Simple Sorting & Searching

Selection, bubble, insertion and pointer sort; linear and binary search; a recursion primer.

1. 3.1Selection SortFind the smallest remaining item and swap it to the front. Repeat. Simple, at most n − 1 swaps, but always O(n²) comparisons. 35 mineasy
2. 3.2Bubble SortCompare neighbours and swap them if they are out of order. After each pass the biggest remaining item has "bubbled" to the end. 35 mineasy
3. 3.3Insertion SortGrow a sorted part on the left by inserting each new item into its correct place, like sorting cards in your hand. Fast on nearly sorted data. 40 mineasy
4. 3.4Pointer SortWhen records are big, don't move them. Sort an array of pointers (or indices) to the records instead, and only small addresses get swapped. 30 minmedium
5. 3.5Linear SearchCheck every item from left to right until you find the key or run out. Works on any array, sorted or not, but costs O(n). 25 mineasy
6. 3.6Binary SearchOn a sorted array, check the middle, then throw away the half that cannot contain the key. Each step halves the problem, so it takes O(log n). 40 minmedium
7. 3.7Recursion PrimerA function that calls itself on a smaller problem until it reaches a base case. You need this for trees (Ch 6) and merge/quick sort (Ch 8). 45 minmedium