# Introduction to Computer Programming: Lab 5

## 10 kinds of searching (and sorting)

### Goals

• To become more comfortable converting between base-10 and binary representation of numbers.
• To identify parallels between binary search and a basic high-low guessing game.
• To quantify how much faster binary search is than linear search.
• To learn about and implement insertion sort.
• To measure the relative efficiency of selection sort and insertion sort under two different assumptions (random data and nearly sorted data).

### Instructions

• Work on this lab with your partner (or on your own if you have not been assigned one).

• Read over the examples which include the solutions to the pre-lab exercises.

• Work with the supplied starter file.

• You are welcome to download a runnable solution module called `lab5x`. If you place that file in the same folder as the file you are working in, then from the IDLE prompt (`>>>`) you can `import` the solution module to see it in action. For example:

``````>>> import lab5x
>>> ns = [7, 2, 6, 5]
>>> lab5x.insertion_sort(ns)
>>> ns
[2, 5, 6, 7]``````
• In the common case, you will not complete the exercises during our scheduled lab. It is then up to you to complete the lab on your own time.

### Exercises

1. Complete `is_binary(items)` so it returns `True` if `items` is a sequence consisting entirely of 1's and 0's and, if it has more than one bit in it, its leading bit (the one at the end of the list) is a 1. Otherwise it returns `False`.

``````>>> is_binary([0])
True
>>> is_binary([1])
True
>>> is_binary([])
False
>>> is_binary([1, 1, 1, 0, 0, 0, 0, 1])
True
>>> is_binary([1, 0])
False``````
2. Complete `from_bits(bits)` so that it returns the number corresponding to the sequence of 0s and 1s in the list (or tuple) `bits`. The order of the bits should be (visually) the opposite of the order we are used to, so that the bit in position 0 corresponds to the one's place, in position 1 the two's place, in position 2, the four's place and so on. Examples:

``````>>> from_bits([0])
0
>>> from_bits([1])
1
>>> from_bits([0, 1, 1, 1])   # which is 1110 in binary: 8 + 4 + 2 = 14
14
>>> from_bits([1, 1, 1, 0, 0, 0, 0, 1])   # 10000111: 128 + 4 + 2 + 1 = 135
135``````

You can assume that `bits` is not empty, consists entirely of 1's and 0's and that if it has more than one bit in it, its leading bit (the one at the end of the list) is a 1. (In other words that it satisfies `is_binary`.)

3. Complete `make_random_increasing(n, lo, hi)` so it returns a list of `n` randomly increasing numbers, where the difference between any two consecutive numbers in the list is at least `lo` but less than `hi`. Examples:

``````>>> make_random_increasing(0, 100, 1000)
[]
>>> make_random_increasing(5, 0, 10)
[3, 12, 16, 17, 23]
>>> make_random_increasing(10, 100, 200)
[186, 373, 486, 650, 837, 1015, 1203, 1325, 1458, 1595]``````

(Hint: this might be very similar to `make_random_list`, which we developed last week, and can also be found in this week's example file.)

4. Complete the function `binary_search(items, x)` so that it returns the position of `x` in the ordered list `items` if `x` is in the list; otherwise it returns `None`. Follow the model of `guess_hi_lo` in the example file. Be sure to test your function thoroughly.

5. Examine the functions `linear_search_per_sec`, `binary_search_per_sec`, and `compare_search`. Experiment using the latter to quantify how much more efficient binary search is than linear search.

6. Insertion sort works similarly to how some people organize a hand of playing cards: for each item (card) picked up, it is inserted into the list (hand) already being formed so as to preserve order. Consider having this sequence of four numbers: 7, 2, 6, 5. If we first just take 7, we can consider that list, `[7]` to be in order. Then if we insert 2, it must go before the 7, so the 7 has to be slid over one position and the list becomes `[2, 7]`. To insert 6, we the 7 has to be slid over one more position (but the 2 can remain), so we get `[2, 6, 7]`, to insert 5, the 6 and 7 each need to be slid over (and, again, the 2 can remain) to finally get the ordered list `[2, 5, 6, 7]`.

Complete `insert(items, i, x)` so that it inserts `x` into the initially ordered list `items` so as to preserve order. `i` is the position through which at least `items` is ordered (i.e., the slice `items[:i]` can be assumed to be in order. You can assume that the length of `items` is larger than `i` (in other words, there is already room on the list to insert `x` without having to perform an `append` operation. `insert` is side effecting and does not return anything. Examples:

``````>>> ns = [None, None, None, None]   # the None's are just placeholders for this example
>>> insert(ns, 0, 7)
>>> ns
[7, None, None, None]
>>> insert(ns, 1, 2)
>>> ns
[2, 7, None, None]
>>> insert(ns, 2, 6)
>>> ns
[2, 6, 7, None]
>>> insert(ns, 3, 5)
>>> ns
[2, 5, 6, 7]``````
7. Complete `insertion_sort(items)` so that it sorts the list `items` into increasing order. You can use the `is_sorted` function from the example file to test your results as in:

``````>>> ns = make_random_list(1000, 0, 10000)
>>> is_sorted(ns)
False
>>> insertion_sort(ns)
>>> is_sorted(ns)
True``````
8. Examine the function `compare_random_sorts`. Experiment using it to try and measure the relative speeds of selection sort and insertion sort. Which algorithm seems to be faster?

9. Complete `compare_near_sorts` so that it is just like `compare_random_sorts` but that instead of sorting random lists, it sorts lists that are nearly in order meaning they are in order except for a few pieces - you can generate such lists by using `make_random_increasing` and the supplied `shuffle_k` (from the example file). Experiment using `compare_near_sorts`. How do the two algorithms fare on data that is nearly sorted as compared to the previous problem? What can you conclude about the two different sorting algorithms?