#
CMU 15-110: Principles of Computing

Searching and Sorting

**Simulations**

**Searching**

See here for linear search and binary search.

**Sorting**

See here for selection sort and merge sort.

**What You Need To Know**

- How linear search works: check each item in order.
- How binary search works: for a sorted list, keep checking the middle item and eliminating half the remaining items on each check.
- What Big-Oh is. Basically, ignore constants and lower-order terms.
- Linear search through a list with n values is O(n).
- Binary search through a sorted list with n values is O(logn).
- logn is much, much smaller than n
- So binary search is much, much faster than linear search.

- When we say logn without a base, we mean base 2.
- 2
^{10} is about 1 thousand, 2^{20} is about 1 million, 2^{30} is about 1 billion.
- log(1 thousand) is about 10, log(1 million) is about 20, log(1 billion) is about 30.

- How selection sort works: keep selecting the largest remaining element and swapping it into place.
- How merge sort works: keep merging sorted sub-lists of size k into sorted sub-lists of size 2k (so, 1 into 2, then 2 into 4, and so on).
- Selection sort is O(n
^{2}). Prove this.
- The first pass of selection sort takes n steps (n-1 compares and one swap).
- The second pass takes (n-1) steps.
- And so on.
- So: total steps = n + (n-1) + ... + 2 + 1 = (n/2)(n+1)
- So: total steps is O(n
^{2}).

- Merge sort is O(nlogn). Prove this.
- The first pass takes 3n steps -- n compares, n copies down, n copies back up.
- In fact, each pass takes 3n steps.
- So the total steps is 3n * (# of passes).
- There are logn number of passes (since the size of the sorted sublists doubles on each pass).
- So the total steps is 3n * (logn).
- So the total steps is O(nlogn).

- Since logn is much smaller than n, nlogn is much smaller than n
^{2}.
- So merge sort is much, much, much faster than selection sort.