Week 10: sorting

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

Monday

The video from today’s lecture (Monday, April 6, 2020):

And here are the annoucements:

  • Quiz 4 is live and due by the end of Friday (Apr 10)

  • Lab 8 is up and due Saturday (Apr 11)

  • I’m still behind on grading…​

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 indices):

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 handy shortcut:

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

sorting in place

We would like to be able to sort a given list in place, meaning we don’t want to create a whole extra second list.

This week we will write functions that, given a list, sort the list from low to high: mysort(L)

Remember, since lists are mutable, the above call to mysort(L) doesn’t need to return the list. The mysort function can just move items around in the list, and those changes will be seen back in main() after the function is done.

bubble sort

We spent 5 minutes thinking about how we would sort numbers in a list from low to high, and a lot of students came up with the idea to compare two adjacent numbers in the list (e.g., L[i] and L[i+1]). If those numbers are out of order, swap them, then move on to the next two numbers in the list.

Here is the code to do the above comparisons and swaps, assuming we already have a list L:

for i in range(len(L) - 1):         # for all indices (except last one)
    if L[i] > L[i+1]:               # if items are out of order
        L[i],L[i+1] = L[i+1],L[i]   # swap them

This is part of an algorithm called the bubble sort. The only thing that is missing is, we need to repeat the above for loop, over and over, until the whole list is sorted.

Here’s the full code for the bubble sort algorithm:

def bubbleSort(L):
    """given a list, sort from low to high"""
    done = False
    while not done:
        nswaps = 0
        for i in range(len(L) - 1):
            if L[i] > L[i+1]:
                L[i],L[i+1] = L[i+1],L[i]
                nswaps = nswaps + 1
        if nswaps == 0:
            done = True

Add this to your sorts.py file and test it to make sure it works.

Wednesday

The video from today’s lecture (Wed, April 8, 2020):

Today’s topics:

  • selection sort

  • analysis of selection and bubble sort

  • assert() statements

  • timing the sorts for N, 2N, and 4N data

selection sort

Here’s the selection sort algorithm: 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…​

And here’s the bubble sort from last time: 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)

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

Selection Sort Video

And here’s the code to add to sorts.py:

def selectionSort(L):
    """give a list, sort from low to high using selection sort"""
    # for each index
    for i in range(len(L)):
        # find smallest item from index to end
        index = i
        for j in range(i,len(L)):
            if L[j] < L[index]:
                index = j
        # swap smallest item to index
        L[index],L[i] = L[i],L[index]

analysis

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.

Because the loops are nested (one loop is inside the other), that means the inner loop gets run many times (however many times the outer loop runs).

For example, consider these nested loops, where the inner loop executes 3 times, and the outer loop executes 4 times:

>>> for i in [1,2,3,4]:
...    for j in ["A","B","C"]:
...       print(i,j)
...
1 A
1 B
1 C
2 A
2 B
2 C
3 A
3 B
3 C
4 A
4 B
4 C

Because the loops are nested, the total number of times the print(i,j) line is called is 12 (4*3).

Can you see that the bubble sort is also a quadratic (\$O(N^2)\$) sort?

If you look at the code from Monday, it’s easy to see the inner for loop depends directly on the length of the list. The outer while loop is a little harder to figure out.

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

Bubble Sort Video

If you watch the smallest number in the video, as it’s being sorted, you can see it only moves one spot to the left with each pass. That means, in the worst possible case, when the smallest number starts on the far right, it will take N passes for the smallest number to move all the way to the left, where it belongs.

That means, in the worst case, bubble sort’s while loop will execute N times, making the bubble sort a quadratic algorithm.

the assert statement

This is just an extra function that is handy to use when you are testing a function. An assert() call just takes an assertion (like x > 5) and tells you if it is True or not. It does this in a funny way, giving no ouput if the assertion is True, and giving and AssertionError is the assertion is False.

Here’s a quick example:

>>> x = 5
>>> assert(x>0)
>>> assert(x<100)
>>> assert(x==6)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError

The peculiar output (nothing if True, error if False) can be used in a test function: add a bunch of assert() statements for what you think should be True after your function runs, and if you don’t see any assertion errors, everything is working.

Here are some examples I added to our sorts.py file:

def main():
    L = [15,10,23,6,18,73,42]
    selectionSort(L)
    print(L)
    assert(L[0] == 6)
    assert(L[0] <= L[1])

    L = list('YACDZWXB')
    selectionSort(L)
    print(L)       # should be A B C D W X Y Z
    assert(L[0] == "A")
    assert(L[1] == "B")
    assert(L[7] == "Z")
    assert(L[0] <= L[1])

And here are what I am asserting should be True if my sorts are all working:

  • the first one says: if the sort worked, there should be a 6 as the first item in the list

  • the second one: if the sort worked, the first item should be less than or equal to the second item

  • for the letters: "A" should be at index 0

  • for the letters: "B" should be at index 1

  • for the letters: "Z" should be at index 7

  • for the letters: the first item should be less than or equal to the second item

If you run the sorts.py file now, and don’t see any assertion errors, then you know the assertions I made are all True, so my sorts are working!

This is just a nice way to test a function without having to visually look at output and see if things look correct (let the computer do the checking!).

timing the sorts

Even though we have analyzed the sorts, and know they are quadratic, it might be nice to actually time how long they take to run, and then compare the times vs the size of the lists being sorted.

Here’s the code in timing.py to do that:

from random import *
from time import *

# import our sort functions from sorts.py file
from sorts import *

def main():
    # ask user for N
    N = int(input("size of list? "))
    # create original list of length N, filled with random numbers
    ORIG = []
    for i in range(N):
        ORIG.append(randrange(-N,N))
    # make copy of list
    L = ORIG.copy()
    # get timestamp
    t1 = time()
    # sort list using one of our sorts
    selectionSort(L)
    # get another timestamp
    t2 = time()
    # print out total time it took to sort list
    print("selection sort time for N=%d:  %7.3f sec" % (N,t2-t1))

    # repeat for other sorts
    L = ORIG.copy()
    t1 = time()
    bubbleSort(L)
    t2 = time()
    print("   bubble sort time for N=%d:  %7.3f sec" % (N,t2-t1))

    L = ORIG.copy()
    t1 = time()
    L.sort()
    t2 = time()
    print("   python sort time for N=%d:  %7.3f sec" % (N,t2-t1))

main()

If you run the above for N=2000, N=4000, and N=8000, you should be able to tell the selection and bubble sorts are quadratic (their run times roughly quadruple each time you double the size of the list).

Friday

The video from today’s lecture (Friday, April 10, 2020):

Outline for today (also see FRIDAY file after running update21)

  • understand how insertion sort works (add insertion.py to sorts.py)

  • timing of our sorts (bubble, selection, insertion) vs L.sort()

  • comparing sorts: https://www.toptal.com/developers/sorting-algorithms

  • see sorts.examples for examples of our sorts

  • try the sorts.worksheet

  • idea of mergeSort(L)

  • also merge(L1,L2,L3) to merge already-sorted lists L1 and L2 into L3

  • next week: recursion

  • don’t forget quiz 4 due today, lab 8 due saturday

  • office hours for me today after class

  • ninja session tonight 7-9pm

insertion sort

Here’s the code for insertion sort:

def insertionSort(L):
    """sort L from low to high using insertion sort"""
    for i in range(1, len(L)):
        j = i
        while j>0 and L[j] < L[j-1]:
            L[j],L[j-1] = L[j-1],L[j]
            j = j - 1

The outer for loop just goes from index 1 to the end. The inner while loop is what does the inserting.

For each item in the list, assuming the items to the left of the current item 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.

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):

Insertion Sort Video

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.

a better way??

See this nice website for a quick animation and comparison of sorting algorithms: https://www.toptal.com/developers/sorting-algorithms

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.

the merging

Here’s a quick look at the merge step: assume we have two already-sorted lists, L1 and L2, and want to merge them into a third list L3. Can we write a merge(L1,L2,L3) function that will do that?

L1 = [1,2,5,7,34,60]   L2 = [3,4,5,6,8,10]   # both already sorted
L3 = [_,_,_,_,_,_,_,_,_,_,_,_]               # L3 has room for L1 and L2

For the above lists, we would just compare the leading numbers from L1 and L2, and whichever is smaller, store it in L3. So after the first 3 compares, they would look something like this (using an x to mark which items have been pulled from L1 and L2):

L1 = [x,x,5,7,34,60]   L2 = [x,4,5,6,8,10]
L3 = [1,2,3,_,_,_,_,_,_,_,_,_]

And the next step compares the 5 from L1 to the 4 from L2.

We’ll write this function next week. All I want you to see today is that the merge is a linear algorithm, since it directly depends on the size of the list.

the splitting

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]    # split using slicing
       L2 = L[half:]     # split using slicing
       # sort each list
       mergeSort(L1)
       mergeSort(L2)
       # merge them back into one sorted list
       merge(L1,L2,L)

Note that the splitting is just the same question we asked about binary search: how many times can we split the list in half before we end up with 1-item lists. And the answer is the same: log(N) times.

So we need to merge the lists back together log(N) times, and merging is a linear operation. That makes merge sort an NlogN algorithm (i.e., it is better than the quadratic sorts!).

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