Week 10: sorting

Monday

This week is sorting. Like last week, there are multiple algorithms to consider and analyze.

four algorithms to compare

Assume we have a list of integers (or floats, or strings), and we want to sort them from smallest to largest. Here are the easiest three algorithms to code:

  • selection sort: find the smallest item in the list, swap it to position 0 in the list; now find (select) the second smallest item in the list, swap it to position 1, and so on…​

  • bubble sort: consider adjacent items in the list. If they are out of order, swap them. Do this for every adjacent pair in the list, moving from left to right. If you don’t make any swaps you are done. If you do make at least one swap, repeat the process (consider pairs all the way from left to right in the list)

  • insertion sort: for each item in the list, assuming the items to the left are already in order, insert the current item into the correct location. This one is harder to picture until it gets going — see the animation below.

Python also has a built-in sort method for lists:

>>> L = range(10)
>>> print(L)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> from random import *
>>> shuffle(L)
>>> print(L)
[3, 1, 7, 4, 5, 9, 0, 6, 2, 8]
>>> L.sort()
>>> print(L)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

How does L.sort() work, and is it a good sort to use?

How would you sort numbers in a list? If you had to write a function to sort a given list, how would you do it?

selection sort

Let’s start with selection sort. This is the selection sort algorithm:

  • given a list L

  • find the smallest number in the list, swap it to position 0

  • find the next smallest number in the list, swap it to position 1

  • find the next smallest number in the list, swap it to position 2

  • and so on…​.

It is called selection sort because each time you are selecting the smallest number from the remaining unsorted elements.

I assume you understand the "find the smallest number in a list" part, but here it is:

 ios = 0               # index of smallest item (so far)
 for i in range(len(L)):
   if L[i] < L[ios]:
     ios = i           # found a smaller item, so save position

 # after the for loop, ios should be the index of the
 # smallest item in the list
 print("smallest item is ", L[ios])

The selection sort uses the above code, but not just for position 0. A second outer for loop is needed to run the above code for all values from 0 to the last index of the list.

Here is a video of the selection sort algorithm (click to play):

See if you can add selectionSort() to our sorts.py file of sorts.

swapping two items in a list

In most languages, to swap two items in a list, you would do this (assuming i and j are valid indecies):

tmp = L[i]     # save ith value to temporary location
L[i] = L[j]    # copy jth value to ith position
L[j] = tmp     # copy from tmp to jth position

Since this is a common operation, python provides a shortcut:

L[j],L[i] = L[i],L[j]

testing

Make sure you add a testing section to sorts.py. Here is a small example to test selectionSort(..):

def main():
    N = 100
    L = range(N)
    shuffle(L)
    selectionSort(L)
    for i in range(len(L) - 1):
        assert(L[i] <= L[i+1])

if __name__ == "__main__":
    main()

analysis and timing

Can you see that the selection sort is a quadratic (\$O(N^2)\$) sort? It’s got nested loops, and each loop depends directly on the length of the list we are trying to sort.

Here’s a simple program to actually time how long a sort takes, given an initially-random list:

from random import *
from time import time
from sorts import *

def main():
  for N in [1000,2000,4000,8000]:
    L = []
    for i in range(N):
        L.append(randrange(1,101))
    t1 = time()
    selectionSort(L)
    t2 = time()
    print("%d %7.3f" % (N,t2-t1))

main()

And here’s one run of the above program:

$ python3 timing.py
1000   0.025
2000   0.095
4000   0.364
8000   1.459

You can easily see, as we double the size of the list, the time for the sort is clearly more than twice as long.

Wednesday

bubble sort

This is the bubble sort algorithm:

  • given a list L

  • for every item in the list, compare to the item just to the right, swap if needed

  • keep doing the above until you go from one end of the list to the other and don’t make any swaps!

Here’s a video of the bubble sort algorithm (click to play):

See if you can add bubbleSort() to our sorts.py file. Include some test code at the bottom of sorts.py to make sure your bubbleSort() function is working properly.

insertion sort

This is the insertion sort algorithm:

  • assume item at index 0 is already "sorted"

  • starting with item at index 1, check all items to the left and swap positions if needed

  • do the same for item at index 2, where now items at index 0 and 1 should be in order

  • do the same for item at index 3, where now items at index 0, 1, and 2 are in order …​and so on

Notice that, for each index, all items to the left are in order, and you are inserting the next item into the correct spot.

Here is a video of the insertion sort algorithm (click to play):

See if you can add insertionSort() to our sorts.py file. Include some test code at the bottom of sorts.py!

analysis of sorting algorithms

Each of the sorting algorithms we considered (selection, bubble, and insertion sort) has nested loops, where each loop’s length depends on the size on the list being sorted (N). This means the number of steps required for each sort, or the runtime, depends on the size of the list squared. These are called quadratic or N-squared sorts, because if the size of the list doubles, the number of steps quadruples. For example, if the runtime of the bubble sort was 10 seconds for a list of size N, it would take approximately 40 seconds to sort a list of size 2N.

Let’s see if we can show this by actually timing a few sorts. Here is the code we will use to time a particular sort:

    from time import time

    t1 = time()
    selectionSort(L)
    t2 = time()
    print("selection sort time: %8.4f" % (t2-t1))

If we do the above for lists of size N, 2N, and 4N, we should see the quadratic behavior.

$ python timesorts.py
N: 2000
selection sort time:   0.1416
  bubble  sort time:   0.4503
insertion sort time:   0.2378
   python sort time:   0.0003
$ python timesorts.py
N: 4000
selection sort time:   0.5836
  bubble  sort time:   1.7433
insertion sort time:   0.9037
   python sort time:   0.0007
$ python timesorts.py
N: 8000
selection sort time:   2.2732
  bubble  sort time:   7.1467
insertion sort time:   4.2049
   python sort time:   0.0015

Notice three things:

  • the quadratic nature of the first three sorts

  • the built-in python sort appears to be much faster

  • the built-in python sort does not appear to be quadratic

How does the python L.sort() method work? Are there other, better sorting algorithms?

Friday

merge sort

Here is the basic merge sort algorithm:

  • if the list has two or more items in it, split it into two lists

  • sort each of the two split lists

  • merge the two sorted lists back together into one sorted list

The merge step is actually not that hard, given two sorted lists. If you know each list is already sorted, you can just compare the first item in each list, and take the smaller of the two.

A more interesting question is, how do we sort each of the split lists? Do we use selection sort, bubble sort, or some other sort?

Since we are talking about merge sort, can we use merge sort to sort each of the split lists? This is called recursion: we are writing a function (mergeSort()), and somewhere in that function we call that function (or a copy of that function) to help solve the problem. This may seem odd, but it is perfectly fine. If you think about stack diagrams, calling any function just puts another function frame on the stack. Assuming there is an end somewhere, it is perfectly fine for a function to call itself and put another copy on the stack.

So here is a version of the mergeSort() function, assuming we have a valid merge() function, which is not hard to write (we will write it next week):

def mergeSort(L):
    """use merge sort to sort L from low to high"""
    if len(L) > 1:
       # split into two lists
       half = len(L)/2
       L1 = L[0:half]
       L2 = L[half:]
       # sort each list
       mergeSort(L1)
       mergeSort(L2)
       # merge them back into one sorted list
       merge(L1,L2,L)

We will write this and test it next week, after we learn all about recursion…​