Searching and Sorting

Linear search checks every item; binary search halves a sorted list. Bubble sort and selection sort put a list in order pass by pass.

Key ideas

Linear search checks the items one by one from the left and works on any list.
Binary search works only on a sorted list: check the middle, then keep the half where the target must be.
In this chapter positions are numbered 1, 2, 3, …, and the middle is the whole part of (low + high) ÷ 2.
Bubble sort compares neighbours from left to right and swaps any pair in the wrong order; after each pass the largest unsorted item has reached the end.
Bubble sort can stop after the first pass that makes no swaps.
Selection sort finds the smallest item of the unsorted part and swaps it to the front of that part, once per pass.

Linear search checks	the position of the item, or all n if it is not there
Binary search, worst case for n items	the smallest k with 2ᵏ > n: 100 items → 7, 1,000 → 10
Bubble pass on 5, 1, 4, 2	1, 4, 2, 5 (3 swaps)
Total bubble swaps	the number of pairs that are out of order
Selection sort, n items	n − 1 passes

Using binary search on a list that is not sorted.
Thinking one bubble pass sorts the whole list.
Mixing the two sorts: selection sort swaps the smallest to the front, bubble sort swaps neighbours.

Bubble sort swaps neighbouring items that are in the wrong order. How many swaps in all does it make to sort 52, 28, 36, 43, 3, 54?

Working: every swap fixes one out-of-order pair; count those pairs

Answer: 7