10 Searching and sorting: linear search, bisection search, bubble, selection and merge sort, and the recursion they are written with

The total of a basket of prices, first without a base case and then with one

Add up a list of prices by taking the first one and asking the same function for the rest. Here is the attempt with the recursive line and nothing else.

def total(prices):
    """Adds up a list of prices. There is no base case."""
    return prices[0] + total(prices[1:])

basket = [2.5, 3.0, 1.5]
print(total(basket))

Run:

Traceback (most recent call last):
  File "basket.py", line 6, in <module>
    print(total(basket))
          ^^^^^^^^^^^^^
  File "basket.py", line 3, in total
    return prices[0] + total(prices[1:])
                       ^^^^^^^^^^^^^^^^^
  File "basket.py", line 3, in total
    return prices[0] + total(prices[1:])
                       ^^^^^^^^^^^^^^^^^
  File "basket.py", line 3, in total
    return prices[0] + total(prices[1:])
                       ^^^^^^^^^^^^^^^^^
  [Previous line repeated 1 more time]
IndexError: list index out of range

Now the same function with two lines added, and a third call on the empty list to prove the new lines work.

def total(prices):
    """Assumes prices is a list of numbers. Returns their sum."""
    if len(prices) == 0:
        return 0
    return prices[0] + total(prices[1:])

basket = [2.5, 3.0, 1.5]
print('items:', len(basket))
print('total:', total(basket))
print('empty basket:', total([]))

Sample Run:

items: 3
total: 7.0
empty basket: 0

factorial of 5, written as a base case and one multiplication

Write factorial(n) without a loop. The mathematics already has the two sentences in it: 1 factorial is 1, and n factorial is n times (n minus 1) factorial.

def factorial(n):
    """Assumes n is an int and n >= 0. Returns n!."""
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

value = 5
print('factorial of', value, 'is', factorial(value))

Sample Run:

factorial of 5 is 120

To see the four calls that answer actually took, the same function with a print on the way in and a print on the way out.

def factorial(n):
    """Assumes n is an int and n >= 0. Returns n!."""
    print('call   factorial(' + str(n) + ')')
    if n == 0 or n == 1:
        print('base   factorial(1) gives 1')
        return 1
    answer = n * factorial(n - 1)
    print('return factorial(' + str(n) + ') gives', answer)
    return answer

result = factorial(4)
print('result:', result)

Sample Run:

call   factorial(4)
call   factorial(3)
call   factorial(2)
call   factorial(1)
base   factorial(1) gives 1
return factorial(2) gives 2
return factorial(3) gives 6
return factorial(4) gives 24
result: 24

A recursive report over a stock list, the shape the lab asks for

A shop keeps two lists of the same length: the product names and their counts. Print one line for every product whose count is below a limit, saying how many to order. The specification says the search must be recursive, so there is no for anywhere.

def find_low(counts, names, limit, i):
    """Assumes counts and names are lists of the same length, limit an int,
    i an index. Prints every name whose count is below limit, from index i on."""
    if i == len(counts):
        return
    if counts[i] < limit:
        print(limit - counts[i], 'of', names[i], 'must be ordered')
    find_low(counts, names, limit, i + 1)

names = ['gofret', 'benimo', 'simit', 'metro']
counts = [4, 5, 5, 7]
find_low(counts, names, 6, 0)

Sample Run:

2 of gofret must be ordered
1 of benimo must be ordered
1 of simit must be ordered

linear_search on a list in no particular order, with and without the early exit

The lecture's version sets a flag and keeps going to the end. Write it, then write the version that leaves the moment it finds the item, and count the comparisons each one makes.

def linear_search(L, e):
    """Assumes L is a list, e any value. Returns True if e is in L."""
    found = False
    for i in range(len(L)):
        if e == L[i]:
            found = True
    return found

plates = [34, 6, 16, 35, 1]
print(linear_search(plates, 16))
print(linear_search(plates, 7))

Sample Run:

True
False

Now both, with a counter, so the difference is a number rather than an opinion.

def linear_search(L, e):
    """Returns (found, comparisons) with no early exit."""
    found = False
    comparisons = 0
    for i in range(len(L)):
        comparisons += 1
        if e == L[i]:
            found = True
    return found, comparisons

def linear_search_early(L, e):
    """Returns (found, comparisons), stopping at the first match."""
    comparisons = 0
    for i in range(len(L)):
        comparisons += 1
        if e == L[i]:
            return True, comparisons
    return False, comparisons

plates = [34, 6, 16, 35, 1]
print('no early exit, looking for 34:', linear_search(plates, 34))
print('early exit,    looking for 34:', linear_search_early(plates, 34))
print('no early exit, looking for  7:', linear_search(plates, 7))
print('early exit,    looking for  7:', linear_search_early(plates, 7))

Sample Run:

no early exit, looking for 34: (True, 5)
early exit,    looking for 34: (True, 1)
no early exit, looking for  7: (False, 5)
early exit,    looking for  7: (False, 5)

binary_search for 156, 102 and 150 in a sorted list of nine ids

Write the loop version. It should return the index of the value, or -1 when the value is absent. Then run the same function with the window printed at every turn so the three values of mid are visible.

def binary_search(L, e):
    """Assumes L is a list sorted in ascending order.
    Returns the index of e in L, or -1 if e is not in L."""
    first = 0
    last = len(L) - 1
    while first <= last:
        mid = (first + last) // 2
        if e < L[mid]:
            last = mid - 1
        elif e > L[mid]:
            first = mid + 1
        else:
            return mid
    return -1

ids = [102, 118, 125, 137, 140, 156, 171, 188, 190]
print('index of 156:', binary_search(ids, 156))
print('index of 102:', binary_search(ids, 102))
print('index of 150:', binary_search(ids, 150))

Sample Run:

index of 156: 5
index of 102: 0
index of 150: -1

The same search for 188, with the window printed before every comparison.

def binary_search(L, e):
    """Prints the window it is still searching before every comparison."""
    first = 0
    last = len(L) - 1
    while first <= last:
        mid = (first + last) // 2
        print('first', first, 'last', last, 'mid', mid, 'L[mid]', L[mid])
        if e < L[mid]:
            last = mid - 1
        elif e > L[mid]:
            first = mid + 1
        else:
            return mid
    return -1

ids = [102, 118, 125, 137, 140, 156, 171, 188, 190]
print('answer:', binary_search(ids, 188))

Sample Run:

first 0 last 8 mid 4 L[mid] 140
first 5 last 8 mid 6 L[mid] 171
first 7 last 8 mid 7 L[mid] 188
answer: 7

The same search written recursively, with start and end as parameters

Write bisection search again with no loop. The window ends become parameters, and dropping half the list becomes a call on a narrower window.

def binary_search(arr, s_val, start, end):
    """Assumes arr is sorted ascending, start and end are indices.
    Returns the index of s_val between start and end, or -1."""
    if start > end:
        return -1
    mid = (start + end) // 2
    if arr[mid] == s_val:
        return mid
    elif arr[mid] > s_val:
        return binary_search(arr, s_val, start, mid - 1)
    else:
        return binary_search(arr, s_val, mid + 1, end)

ids = [102, 118, 125, 137, 140, 156, 171, 188, 190]
print('index of 125:', binary_search(ids, 125, 0, len(ids) - 1))
print('index of 999:', binary_search(ids, 999, 0, len(ids) - 1))

Sample Run:

index of 125: 2
index of 999: -1

How many comparisons for the 20000 codes in the hook

The till program at the top of the page held 20000 sorted codes and spent 79994 comparisons on four lookups. Work out what bisection search would spend, from the halving count rather than from a library.

# How many times can 20000 be halved before only one item is left?
size = 20000
halvings = 0
while size > 1:
    size = size // 2
    halvings += 1
print('halvings:', halvings)
print('2 to that power:', 2 ** halvings)

Sample Run:

halvings: 14
2 to that power: 16384

And the same four lookups done by bisection search, counted the same way the hook counted its own.

# Same list, same four codes, but each lookup throws away half the list.
codes = list(range(0, 40000, 2))
wanted = [39998, 39996, 39994, 39992]
comparisons = 0
for w in wanted:
    first = 0
    last = len(codes) - 1
    while first <= last:
        mid = (first + last) // 2
        comparisons += 1
        if codes[mid] == w:
            break
        elif codes[mid] > w:
            last = mid - 1
        else:
            first = mid + 1
print('comparisons for the same 4 lookups:', comparisons)

Sample Run:

comparisons for the same 4 lookups: 56

bubble_sort with the already sorted flag, and the passes it actually makes

Write bubble sort the way the lecture writes it, with a flag that stops the outer loop early when a pass makes no swaps, and print the list after every pass so the outer loop's work is visible.

def bubble_sort(data):
    """Prints the list after every pass."""
    issorted = False
    j = 0
    while j < len(data) - 1 and not issorted:
        issorted = True
        for k in range(len(data) - j - 1):
            if data[k] > data[k + 1]:
                issorted = False
                temp = data[k]
                data[k] = data[k + 1]
                data[k + 1] = temp
        print('after pass', j + 1, data)
        j = j + 1

marks = [55, 90, 40, 72, 61]
bubble_sort(marks)

Sample Run:

after pass 1 [55, 40, 72, 61, 90]
after pass 2 [40, 55, 61, 72, 90]
after pass 3 [40, 55, 61, 72, 90]

And the point of the flag: the number of passes on a list that is already sorted against a list that is in reverse order.

def bubble_sort(data):
    """Counts the passes it actually makes."""
    issorted = False
    j = 0
    while j < len(data) - 1 and not issorted:
        issorted = True
        for k in range(len(data) - j - 1):
            if data[k] > data[k + 1]:
                issorted = False
                temp = data[k]
                data[k] = data[k + 1]
                data[k + 1] = temp
        j = j + 1
    return j

print('passes on a sorted list: ', bubble_sort([40, 55, 61, 72, 90]))
print('passes on a shuffled one:', bubble_sort([90, 72, 61, 55, 40]))

Sample Run:

passes on a sorted list:  1
passes on a shuffled one: 4

selection_sort, and why the lecture's version swaps more than it needs to

Write selection sort the way the lecture writes it: walk the unsorted tail and swap whenever you meet something smaller than the item at the front of that tail, printing the list each time a position is settled.

def selection_sort(L):
    """Prints the list every time the front of the unsorted part is fixed."""
    suffix_start = 0
    while suffix_start != len(L):
        for i in range(suffix_start, len(L)):
            if L[i] < L[suffix_start]:
                L[suffix_start], L[i] = L[i], L[suffix_start]
        print('position', suffix_start, 'settled:', L)
        suffix_start += 1

marks = [55, 90, 40, 72, 61]
selection_sort(marks)

Sample Run:

position 0 settled: [40, 90, 55, 72, 61]
position 1 settled: [40, 55, 90, 72, 61]
position 2 settled: [40, 55, 61, 90, 72]
position 3 settled: [40, 55, 61, 72, 90]
position 4 settled: [40, 55, 61, 72, 90]

The lecture's version swaps on every smaller item it meets. The textbook description says find the smallest, then swap once. Both sort; count the swaps.

def selection_sort_swaps(L):
    """The course version: swaps whenever it meets a smaller item.
    Returns how many swaps it did."""
    swaps = 0
    suffix_start = 0
    while suffix_start != len(L):
        for i in range(suffix_start, len(L)):
            if L[i] < L[suffix_start]:
                L[suffix_start], L[i] = L[i], L[suffix_start]
                swaps += 1
        suffix_start += 1
    return swaps

def find_min_then_swap(L):
    """Finds the smallest item first and swaps once per position.
    Returns how many swaps it did."""
    swaps = 0
    for start in range(len(L)):
        smallest = start
        for i in range(start + 1, len(L)):
            if L[i] < L[smallest]:
                smallest = i
        if smallest != start:
            L[start], L[smallest] = L[smallest], L[start]
            swaps += 1
    return swaps

a = [5, 4, 3, 2, 1]
b = [5, 4, 3, 2, 1]
print('course version swaps:  ', selection_sort_swaps(a), a)
print('find min then swap:    ', find_min_then_swap(b), b)

Sample Run:

course version swaps:   10 [1, 2, 3, 4, 5]
find min then swap:     2 [1, 2, 3, 4, 5]

merge of [40, 61, 90] and [55, 72] into one sorted list

Write the merge step on its own, before any recursion. Two sorted lists go in, one sorted list comes out, and neither input is changed. The comparison is passed in as a function so that the same merge can be used for ascending and descending order.

def merge(left, right, compare):
    """Assumes left and right are sorted lists and compare(a, b) is True when
    a belongs before b. Returns a NEW sorted list with every item of both."""
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

def before(a, b):
    """Returns True when a belongs before b in ascending order."""
    return a < b

left = [40, 61, 90]
right = [55, 72]
print(merge(left, right, before))
print('left is untouched: ', left)
print('right is untouched:', right)

Sample Run:

[40, 55, 61, 72, 90]
left is untouched:  [40, 61, 90]
right is untouched: [55, 72]

merge_sort around that merge, with the comparison as a default parameter

Now the recursion. Two lines do the splitting and one line does the merging. The comparison has a default value so that the usual call takes one argument, and a caller who wants the other order can pass a different comparison.

def merge(left, right, compare):
    """Assumes left and right are sorted. Returns a new sorted list."""
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if compare(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

def merge_sort(L, compare=lambda x, y: x < y):
    """Assumes L is a list. Returns a NEW sorted list; L is not changed."""
    if len(L) < 2:
        return L[:]
    middle = len(L) // 2
    left = merge_sort(L[:middle], compare)
    right = merge_sort(L[middle:], compare)
    return merge(left, right, compare)

marks = [55, 90, 40, 72, 61, 18]
result = merge_sort(marks)
print('sorted copy: ', result)
print('original:    ', marks)
print('descending:  ', merge_sort(marks, lambda x, y: x > y))

Sample Run:

sorted copy:  [18, 40, 55, 61, 72, 90]
original:     [55, 90, 40, 72, 61, 18]
descending:   [90, 72, 61, 55, 40, 18]

The same function with the splits and merges printed, which is the picture above in text form.

def merge(left, right):
    """Assumes left and right are sorted ascending. Returns a new sorted list."""
    result = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    while i < len(left):
        result.append(left[i])
        i += 1
    while j < len(right):
        result.append(right[j])
        j += 1
    return result

def merge_sort(L, depth):
    """Prints the split and the merge at every depth."""
    if len(L) < 2:
        print('  ' * depth + 'base ' + str(L))
        return L[:]
    middle = len(L) // 2
    print('  ' * depth + 'split ' + str(L))
    left = merge_sort(L[:middle], depth + 1)
    right = merge_sort(L[middle:], depth + 1)
    merged = merge(left, right)
    print('  ' * depth + 'merge ' + str(left) + ' and ' + str(right)
          + ' into ' + str(merged))
    return merged

merge_sort([55, 90, 40, 72], 0)

Sample Run:

split [55, 90, 40, 72]
  split [55, 90]
    base [55]
    base [90]
  merge [55] and [90] into [55, 90]
  split [40, 72]
    base [40]
    base [72]
  merge [40] and [72] into [40, 72]
merge [55, 90] and [40, 72] into [40, 55, 72, 90]

Finding the break even lookup count for a 20000 item list

A program holds 20000 records and will look up k of them. Find the smallest k for which sorting first is cheaper, using the halving count and a loop rather than algebra.

# Where does paying for the sort start to pay off?
n = 20000
halvings = 0
size = n
while size > 1:
    size = size // 2
    halvings += 1
lookups = 1
while n * lookups <= n * halvings + (halvings + 1) * lookups:
    lookups += 1
print('halvings:', halvings)
print('sorting pays off from lookup number', lookups)

Sample Run:

halvings: 14
sorting pays off from lookup number 15

sort, sorted, sorting your own objects, and the lookup that needs no search

Three questions a lab answer has to get right. First, which of the two built in sorts copies.

marks = [55, 90, 40, 72, 61]
copy = sorted(marks)
print('sorted() gives back a list:', copy)
print('the original is untouched: ', marks)

answer = marks.sort()
print('sort() gives back:         ', answer)
print('but the original is now:   ', marks)

Sample Run:

sorted() gives back a list: [40, 55, 61, 72, 90]
the original is untouched:  [55, 90, 40, 72, 61]
sort() gives back:          None
but the original is now:    [40, 55, 61, 72, 90]

Second, a list of objects. The sort code does not change at all; the only new thing is __lt__ in the class, which decides what the less than sign means and therefore what sorted means.

class Track:
    """A song with a title and a length in seconds."""

    def __init__(self, title, seconds):
        self.__title = title
        self.__seconds = seconds

    def get_title(self):
        """Returns the title."""
        return self.__title

    def get_seconds(self):
        """Returns the length in seconds."""
        return self.__seconds

    def __lt__(self, other):
        """A track is less than another if it is shorter. Ties go by title."""
        if self.__seconds == other.get_seconds():
            return self.__title < other.get_title()
        return self.__seconds < other.get_seconds()

    def __repr__(self):
        """Returns the title and the length."""
        return self.__title + '(' + str(self.__seconds) + ')'

playlist = [Track('Oda', 210), Track('Bir', 185), Track('Cam', 210),
            Track('Ada', 240)]
playlist.sort()
print(playlist)

Sample Run:

[Bir(185), Cam(210), Oda(210), Ada(240)]

Third, the case where no search is needed. A dictionary answers a lookup without walking anything, which is why sorting is sometimes the wrong question.

def list_looks(names, wanted):
    """Returns how many items a walk of the list examines before it answers."""
    looks = 0
    for i in range(len(names)):
        looks += 1
        if names[i] == wanted:
            return looks
    return looks

names = []
for i in range(1000):
    names.append('id' + str(i))

lookup = {}
for i in range(1000):
    lookup['id' + str(i)] = i

print('list walk for the last name:', list_looks(names, 'id999'))
print('list walk for a missing name:', list_looks(names, 'id9999'))
print('dictionary answer:', 'id999' in lookup, lookup['id999'])
print('dictionary answer for missing:', 'id9999' in lookup)

Sample Run:

list walk for the last name: 1000
list walk for a missing name: 1000
dictionary answer: True 999
dictionary answer for missing: False