We’ve implemented both linear search and binary search in a small program that measures their performance (in terms of wall-clock time). We’ll share these files with you (timeSearch.py and timeBinarySearch.py), and we’ll run them to see how long searching takes as we vary the size of the input list.

We can also calculate how long we would expect algorithms of different efficiencies to take on different size problems:

Binary search only works on a sorted list. Last week, we used python’s built-in sort() method for lists to perform the sorting task. This works fine, but does not provide any insight into how a sorting algorithm works. This week, we’ll explore techniques for implementing our own sorting algorithm using the CS21 skills we already know.

Suppose you have an unsorted pile of exams, and you need to sort them alphabetically by name before you can enter them in a grading spreadsheet. For example, let’s say your exams are in this order:

Imagine these names are in a list, where "Tia" is at index 0, "Andy" is at index 1, etc.

When humans look at this problem, we may be able to look at multiple items at once and move large groups of items that are already in sorted order to the proper location. This concept is hard to express algorithmically in a computer language, so instead we focus on a simpler operation that swaps only two elements at a time.

The swap(lst, i, j) function will swap two items at positions i and j in a list lst. Once we have this small helper function working, we can use it to implement some sorting routines by comparing two elements at a time using Boolean relational operators, and calling swap() if the elements are out of order. For example:

In general, we will need to perform several swaps to sort an arbitrary list.

The key idea of selection sort is that it repeatedly selects the minimum item remaining in the unsorted portion of the list and then swaps it into its final sorted location.

Consider how selection sort would operate on following list:

When it begins, the entire list is unsorted. Therefore, the goal is to get the minimum item in the list into position 0. To do this it keeps track of the indexOfMin. It always starts this variable at the first index of the unsorted portion of the list, and updates it whenever it finds a smaller item. In this way, we can do a linear search to find the index of the smallest item in the unsorted portion of the list.

The indexOfMin starts at 0. Since 3 < 5, indexOfMin is updated to location 1. Since 8 is not < 3, indexOfMin is unchanged. Since 0 < 3, indexOfMin is updated to location 3. All other locations in the list will be checked to see if their contents are < 0. No further updates of indexOfMin are needed as 0 in position 3 is the smallest element/

After the entire unsorted portion of the list has been checked, one swap is done between locations indexOfMin and the location at the beginning of the unsorted portion. The current ordering in the list will become:

Let’s redraw this to make it clear where the division between the sorted and unsorted portions of the list occurs.

Next, selection sort will repeat the process described above to find the index of the minimum element in the usorted portion of the list, now starting at index 1. It will find that the indexOfMin is now 5, and it will swap the items at locations 1 and 5. Giving us this new list ordering:

Notice that the sorted portion of the list is growing by one more item each iteration through selection sort.

What would the list look like after the next iteration?

Selection sort can be implemented as a loop within a loop, where the inner loop is used to find indexOfMin, and each iteration of the outer loop identifies the smallest element in the unsorted portion of the list and swaps it into place.

How many steps does it take to run selection sort?

We need to first find the indexOfMin in a list of \(N\) elements. Finding the indexOfMin is a linear search, so it takes \(N\) steps. Then we need to find indexOfMin in the unsorted portion of the list — a list of \((N-1)\) elements. This takes \((N-1)\) steps. Finding the next minimum element takes \((N-2)\) steps, and so on.

The toal number of steps that selection sort takes is \(N + (N-1) + (N-2) + ... + 2 + 1\). The total sum is \(\frac{N^2+N}{2}\). Note that the highest order term is quadratic (\(\frac{N^2}{2}\)). We therefore say that selection sort is a quadratic time sort algorithm. Intuitively, when we double the size of the list we are sorting, selection sort will take \(2^2=4\) times as long to run. How does selection sort compare to linear search or binary search?

Another approach to sort a list is to scan over the list and just compare adjacent elements — elements at index i and i+1. If they are out of order, we will swap. But one scan over this list may not be enough. So we can perform multiple scans until the list is sorted. A list will be sorted when we perform zero swaps while scanning the list.

Like selection sort, bubble sort is implemented as a loop within a loop, where the amount of work can be described as the summation \(N + (N-1) + (N-2) + ... + 2 + 1\). The has the same quadratic runtime, so unfortunately, bubble sort does not improve on the worst case running time of selection sort. Note that in situations where the list is nearly sorted, bubble sort may not find many items out of order and only a few passes of the outer loop may be needed. In some cases, this may result in a faster sort.

Bubble sort and selection sort are both examples of quadratic sort algorithms. In the case of searching it we found that binary search was a considerable improvement over linear search, provided the list was already sorted. Sorting is computationally more time consuming than searching but we can sort once and perform many searches on a the sorted list.

A natural question to ask is if there are any sorting algorithms that are better than quadratic. The short answer is yes, and in fact, python’s built in sort() performs much better than either bubble sort or selection sort. We need a few more skills to explore these improved algorithms.