JamCoders

 💾 Download
In [ ]:
%config InteractiveShell.ast_node_interactivity="none"
def f(globals, locals):
    import base64
    code="ZGVmIG1ha2VfcHJpbnRfbG9jYWxzKCk6IAogICAgIyBJbiBhIGZ1bmN0aW9uIHRvIHByZXZlbnQgbG9jYWxzIGFuZCBpbXBvcnRzIGZyb20gbGVha2luZy4KICAgIGdsb2JhbCBtYWtlX3ByaW50X2xvY2FscwogICAgZGVsIG1ha2VfcHJpbnRfbG9jYWxzICAjIE9ubHkgcnVuIHRoaXMgZnVuY3Rpb24gb25jZS4KCiAgICBpbXBvcnQgSVB5dGhvbgogICAgaW1wb3J0IGFzdAogICAgaW1wb3J0IGluc3BlY3QKCiAgICBjbGFzcyBWaXNpdG9yKGFzdC5Ob2RlVmlzaXRvcik6CiAgICAgICAgZGVmIF9faW5pdF9fKHNlbGYpOgogICAgICAgICAgICBzZWxmLnZhcmlhYmxlcyA9IHNldCgpCiAgICAgICAgZGVmIHZpc2l0X05hbWUoc2VsZiwgbmFtZSk6CiAgICAgICAgICAgIHNlbGYudmFyaWFibGVzLmFkZChuYW1lLmlkKQogICAgICAgICMgVE9ETzogUG9zc2libHkgZGV0ZWN0IHdoZXRoZXIgdmFyaWFibGVzIGFyZSBhc3NpZ25lZCB0by4KCiAgICBBTExPV19UWVBFUyA9IFtpbnQsIGZsb2F0LCBzdHIsIGJvb2wsIGxpc3QsIGRpY3QsIHR1cGxlLCByYW5nZV0KICAgIGRlZiBmaWx0ZXJfdmFyaWFibGVzKHZhcmlhYmxlcywgbG9jYWxzKToKICAgICAgICBmb3IgdiBpbiB2YXJpYWJsZXM6CiAgICAgICAgICAgIGlmIHYgaW4gbG9jYWxzIGFuZCB0eXBlKGxvY2Fsc1t2XSkgaW4gQUxMT1dfVFlQRVM6CiAgICAgICAgICAgICAgICB5aWVsZCB2CiAgCiAgICAjIFVuZm9ydHVuYXRlbHksIHRoZXJlIGRvZXNuJ3Qgc2VlbSB0byBiZSBhIHN1cHBvcnRlZCB3YXkgb2YgZ2V0dGluZwogICAgIyB0aGUgY3VycmVudCBjZWxsJ3MgY29kZSB2aWEgdGhlIHB1YmxpYyBJUHl0aG9uIEFQSXMuIEhvd2V2ZXIsIGJlY2F1c2UKICAgICMgd2UgYXJlIGdldHRpbmcgY2FsbGVkIGZyb20gSVB5dGhvbiBpdHNlbGYgYW5kIHdlIGFyZSBhbHJlYWR5IGluc3BlY3RpbmcKICAgICMgdGhlIHN0YWNrdHJhY2UsIHdlIG1pZ2h0IGFzIHdlbGwganVzdCBwZWVrIGludG8gaXRzIGZyYW1lLi4uCiAgICBpZiBJUHl0aG9uLl9fdmVyc2lvbl9fID09ICI1LjUuMCI6CiAgICAgICAgIyBjb2xhYgogICAgICAgIGRlZiBnZXRfYXN0KGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGFzdC5Nb2R1bGUoZnJhbWUuZl9iYWNrLmZfYmFjay5mX2xvY2Fsc1sibm9kZWxpc3QiXSkKICAgICAgICBkZWYgZmluZF9sb2NhbHMoZnJhbWUpOgogICAgICAgICAgICByZXR1cm4gZnJhbWUuZl9sb2NhbHMKICAgICAgICBkZWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfYmFjay5mX2NvZGUuY29fZmlsZW5hbWUuZW5kc3dpdGgoIklQeXRob24vY29yZS9pbnRlcmFjdGl2ZXNoZWxsLnB5IikKCiAgICBlbGlmIElQeXRob24uX192ZXJzaW9uX18gPT0gIjguNC4wIjoKICAgICAgICAjIGxhYiBjb21wdXRlcnMKICAgICAgICBkZWYgZ2V0X2FzdChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBhc3QuTW9kdWxlKGZyYW1lLmZfYmFjay5mX2JhY2suZl9sb2NhbHNbIm5vZGVsaXN0Il0pCiAgICAgICAgZGVmIGZpbmRfbG9jYWxzKGZyYW1lKToKICAgICAgICAgICAgcmV0dXJuIGZyYW1lLmZfbG9jYWxzCiAgICAgICAgZGVmIGF0X3RvcF9sZXZlbChmcmFtZSk6CiAgICAgICAgICAgIHJldHVybiBmcmFtZS5mX2JhY2suZl9jb2RlLmNvX2ZpbGVuYW1lLmVuZHN3aXRoKCJJUHl0aG9uL2NvcmUvaW50ZXJhY3RpdmVzaGVsbC5weSIpCiAgICBlbHNlOgogICAgICAgIHByaW50KGYicHJpbnRfbG9jYWxzKCkgbm90IHN1cHBvcnRlZCBvbiBJUHl0aG9uIHZlcnNpb24ge0lQeXRob24uX192ZXJzaW9uX199IikKCiAgICBkZWYgZ2V0X2NlbGxfbmFtZXMoZnJhbWUpOgogICAgICAgIHRyZWUgPSBnZXRfYXN0KGZyYW1lKQogICAgICAgIHZpc2l0b3IgPSBWaXNpdG9yKCkKICAgICAgICB2aXNpdG9yLnZpc2l0KHRyZWUpCiAgICAgICAgcmV0dXJuIGZpbHRlcl92YXJpYWJsZXModmlzaXRvci52YXJpYWJsZXMsIGZyYW1lLmZfbG9jYWxzKQoKICAgIGRlZiBmaW5kX3doaWNoKGZyYW1lKToKICAgICAgICAjIEZyYW1lIGlzIHRoZSBmcmFtZSB3aG9zZSBsb2NhbHMgd2UgYXJlIGludGVyZXN0ZWQgaW4gcHJpbnRpbmcuCiAgICAgICAgaWYgYXRfdG9wX2xldmVsKGZyYW1lKToKICAgICAgICAgICAgIyBUaGUgcGFyZW50IGZyYW1lIG9mIHRoZSBpbnRlcmVzdGVkIGZyYW1lIGlzIGEgbW9kdWxlLCBtb3N0IGxpa2VseQogICAgICAgICAgICAjICJpbnRlcmFjdGl2ZXNoZWxsIi4gVGhpcyBtZWFucyB3ZSBhcmUgaW4gdGhlIGdsb2JhbCBzY29wZSwgc2luY2UKICAgICAgICAgICAgIyBvbmx5IHRoZSBnbG9iYWwgc2NvcGUgc2hvdWxkIGJlIGRpcmVjdGx5IHJ1biBieSB0aGUgaW50ZXJhY3RpdmUgc2hlbGwuCiAgICAgICAgICAgIHJldHVybiBzZXQoZ2V0X2NlbGxfbmFtZXMoZnJhbWUpKQogICAgICAgICMgVGhlIHBhcmVudCBmcmFtZSBpcyBub3QgYSBtb2R1bGUsIHNvIHdlIGFyZSBpbiBhIGxvY2FsIHNjb3BlLgogICAgICAgIHJldHVybiBzZXQoZnJhbWUuZl9sb2NhbHMpCgogICAgZGVmIHByaW50X2xvY2Fscygqd2hpY2gsIHR5cGVzPUZhbHNlKToKICAgICAgICAiIiJQcmludCB0aGUgbG9jYWwgdmFyaWFibGVzIGluIHRoZSBjYWxsZXIncyBmcmFtZS4iIiIKICAgICAgICBpbXBvcnQgaW5zcGVjdAogICAgICAgICMgY3VycmVudGZyYW1lKCkgZnJhbWUgaXMgcHJpbnRfbG9jYWxzLiBXZSB3YW50IHRoZSBjYWxsZXIncyBmcmFtZQogICAgICAgIGZyYW1lID0gaW5zcGVjdC5jdXJyZW50ZnJhbWUoKS5mX2JhY2sKICAgICAgICBsb2NhbHMgPSBmaW5kX2xvY2FscyhmcmFtZSkKICAgICAgICB3aGljaCA9IHNldCh3aGljaCkgaWYgd2hpY2ggZWxzZSBmaW5kX3doaWNoKGZyYW1lKQogICAgICAgIGxsID0ge2s6IHYgZm9yIGssIHYgaW4gbG9jYWxzLml0ZW1zKCkgaWYgayBpbiB3aGljaH0KICAgICAgICBpZiBub3QgbGw6CiAgICAgICAgICAgIHByaW50KCJwcmludF9sb2NhbHM6IG5vIGxvY2FscyIpCiAgICAgICAgICAgIHJldHVybgogICAgICAgIGlmIHR5cGVzOgogICAgICAgICAgICBwcmludCgiXG4iLmpvaW4oZiJ7a306IHt0eXBlKHYpLl9fbmFtZV9ffSDihpAge3Z9IiBmb3IgaywgdiBpbiBsbC5pdGVtcygpKSkKICAgICAgICBlbHNlOgogICAgICAgICAgICBwcmludCgiOyAiLmpvaW4oZiJ7a30g4oaQIHtyZXByKHYpfSIgZm9yIGssIHYgaW4gbGwuaXRlbXMoKSkpCgogICAgcmV0dXJuIHByaW50X2xvY2FscwoKcHJpbnRfbG9jYWxzID0gbWFrZV9wcmludF9sb2NhbHMoKQ=="
    exec(base64.b64decode(code), globals, locals)
f(globals(), locals())
del f

def check(fn, *input, expected):
    result = fn(*input)
    if expected != result:
        print(
            f"{fn.__name__}({', '.join(input)}) should be {expected}, not {result}.")
    else:
        print(f"Test case passed!")

Week 3, Day 2

Warm up :

Let's dance with merge sort! https://www.youtube.com/watch?v=dENca26N6V4
One more for quicksort! https://www.youtube.com/watch?v=3San3uKKHgg

Question 1

We are going to learn about how Merge Sort works. But first, we are going to figure out how to merge sorted lists of short, fixed sizes, of 4 and 32.

Python3 has a built in sorting function that we can use for parts of this exercise.

1.1 Help the lecturer

Let's say we have two sections of a class. The two sections each contain 16 students. The students are sorted in an alphabetical order based on their names. The lecturer wants to make a grade roster of the entire class. The lecturer wants to retain the alphabetical ordering of the students' names.

1.1.1 Sort 2

Let's take it slower and start with sort2.

In [ ]:
# sort2 is a function
sort2 = sorted


def sort4(L):
    """Sorts the list L, which has length 4.
    
    1. Partitions L into two equal halves.
    2. Calls the function sort2.
    3. Merges the sorted together.

    Arguments:
        L (List[int]): A (potentially unsorted) list of size 4.

    Returns: (List[int]) A sorted list of length 4.

    Effects: None.
    """
    L_first_sorted = sort2(L[0:2]) # call sort2 on first half
    L_last_sorted = sort2(L[2:4]) # call sort2 on second half
    #
    # do something to return a sorted list
    #
In [ ]:
L = [5, 2, 1, 6]
check(sort4, L, expected = [1, 2, 5, 6])

M = [4, 3, 2, 1]
check(sort4, M, expected = [1, 2, 3, 4])

1.1.2 Sort 32

Write a function sort32 that sorts a list of 32 elements. The function should make two recursive calls to a provided function sort16

In [ ]:
sort16 = sorted


def sort32(L):
    """Sorts the list L, which has length 32.
    
    1. Partitions L into two equal halves.
    2. Calls the function sort16.
    3. Merges the sorted lists together.

    Arguments:
        L (List[int]): A (potentially unsorted) list of size 32.

    Returns: (List[int]) A sorted list of length 32.

    Effects: None.
    """
    L_first_sorted = sort16(L[0:16])
    L_last_sorted = sort16(L[16:32])
    #
    # do something to return a sorted list
    #
In [ ]:
# TEST_CASE
L = [32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18,
        17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

check(sort32, L, expected = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,
                  18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32])

1.2 Merge Sort Function

Write a function merge_sort that will sort a list of any size. The function should make two recursive calls to itself

Algorithm Merge Sort: Input L.

  1. We partition the list into two equal halves and sort them by calling the sorting function recursively until we reach the base case where len(L) == 1.

  2. We create a new sorted list by merging the two now sorted halves together and return it.

For example : for step 2, if we have L1 = [1, 2, 4] and L2 = [3, 5, 7], we compare 1 from L1 and 3 from L2. 1 is greater, so we add it to the sorted list we are building. Then, we compare 2 from L1 and 3 from L2. 2 is greater, so we add that to the sorted list. Then, we compare 4 from L1 and 3 from L2. 3 is greater, so we add 3 to the sorted list. Then, we compare 4 from L1 and 5 from L2. 4 is greater, so we add it to the sorted list. Now there is no element left in L1, so we add all the remaining elements in L2 to the end of the sorted list.

In [ ]:
def merge_lists (L1, L2) :
    """Merges two lists L1 and L2 using the step 2 above.
    Arguments: L1 (list), L2 (list)
    Returns: (list)
    """
    # Merge the two sorted lists : make sure to not leave any element

    # Returns the merged list
In [ ]:
L1 = [1, 4, 5] 
L2 = [2, 3, 6]
check(merge_lists, L1, L2, expected = [1, 2, 3, 4, 5, 6])

M1 = [1, 2, 4]
M2 = [3, 5, 7]
check(merge_lists, M1, M2, expected = [1, 2, 3, 4, 5, 7])

N1 = [4, 5]
N2 = [1, 2, 3]
check(merge_lists, N1, N2, expected = [1, 2, 3, 4, 5])
In [ ]:
def merge_sort(L):
    """Sorts the list L of any size using the merge sort algorithm.
    Arguments: L (list)
    Returns: (list)
    """
    
    # Base case
    
    # Partition the list into two halves and call the function recursively
 
    # Return the result of merging the two lists, which are now sorted : call the merge_lists function here
In [ ]:
L = [23, 10, 5, 1, 4]
check(merge_sort, L, expected = [1, 4, 5, 10, 23])

M = [4, 3, 2, 1]
check(merge_sort, M, expected = [1, 2, 3, 4])

N = [-4, 3, 14, 15]
check(merge_sort, N, expected = [-4, 3, 14, 15])

Question 2 : Quicksort

Check out this interesting diagram which shows how quicksort divides up an example array:

We are going to try this process ourselves by hand, and then later implement a function which performs quicksort.

When in doubt, try drawing a picture like this with your array.

image.png

2.1 Sort by Hand

We are going to quicksort by hand, step by step, the following list of numbers [10, 15, 1, 2, 6, 12, 5, 7].

  1. The first step in quicksort is to pick a pivot element, for example 7.
  2. Then, put all elements less than 7 on the left of 7.
  3. Then, put all elements greater than 7 on the right of 7.

Note: the array doesn't have to be completely sorted, but 7 must end up with only items smaller to the left of it.

In [ ]:
# Items smaller than 7:


# Items larger than 7:


# All items together, with 7 in-between:

Let's pivot again!

Next, we are going to consider each half of our new array, and run merge sort on each half. We are going to divide our arrays again by picking a new pivot for each half.

For the smaller side, we can use the number 5.

For the greater side, we will use the number 10.

Smaller side:

First, write the half of the array that you found earlier, with items less than 7.

Now, divide this array based on the new pivot 5

In [ ]:

Greater side:

First, write the half of the array you found earlier, with the items greater than 7.

Now, divide this array based on the new pivot 10

In [ ]:

Continuing the process...

What happens next, as this process continues? Try to execute the rest of quicksort by hand. When in doubt, try drawing on paper.

This is a useful video which illustrates quicksort:

In [ ]:

2.2 Quicksort Function

Using quicksort, sort the following list of numbers. Try to write your own quicksort function based on the algorithm given in the lecture (below)

Algorithm Quicksort: Input L of length n.

  1. Pick random j in [0,...,n-1]

  2. Let pivot=L[j] and reorder L so that locations L[0],..,L[i-1] are smaller than pivot and locations L[i],...,L[n-1] are at least as large as pivot.

  3. Recursively sort L[0],...,L[i-1] and L[i+1],...,L[n-1]

In [ ]:
import random
L = [66, 25, 600, 570, 700, 145, 909, 501, 1000, 10000]

Write a helper function called partition, which will arrange the list elements in L on the correct side of an integer pivot called pivot.

The inputs to our function are:

  1. L the list
  2. pivot, the pivot element to compare values to
  3. beg the
In [ ]:
def partition(L, pivot, beg, end):
    """.
    Arguments: L (list), x (integer), beg (integer), end (integer)
    Returns: (tuple)
    """

    # move all the elements in L that are less than the pivot to the left of pivot and all the rest to the right of pivot

    # return a tuple that represents indices one less than and one greater than the index of the pivot in the list
    return (i, j)
In [ ]:
L = [3, 1, 8, 6, 2, 1, 4]
x1 = 6
beg1 = 0
end1 = len(L) - 1
check(partition, L, x1, beg1, end1, expected = (4, 6))

M = [2, 5, 4, 1]
x2 = 4
beg2 = 0
end2 = len(M) - 1
check(partition, M, x2, beg2, end2, expected = (1, 3))
In [ ]:
def quicksort(L, beg=0, end=None):
    """Sorts the list L using the quicksort algorithm.
    Arguments: L (list)
    Returns: (list)
    """
    # base case

    # select a pivot randomly

    # run the partition on that pivot
In [ ]:
check(quicksort, L, expected = ['Arsenal', 'Chelsea', 'Crystal Palace', 'Leicester', 'Liverpool', 'Man City', 'Man United', 'Southampton', 'Tottenham'])
# for other inputs 
M = [23, 10, 5, 1, 4]
check(quicksort, M, expected = [1, 4, 5, 10, 23])

N = [4, 3, 2, 1]
check(quicksort, N, expected = [1, 2, 3, 4])

O = [-4, 3, 14, 15]
check(quicksort, O, expected = [-4, 3, 14, 15])

Challenge

Using your quicksort algorithm, sort the following list of football teams based on their points.

In [ ]:
L = [["Man United", 10],
     ["Leicester", 3],
     ["Chelsea", 6],
     ["Tottenham", 5],
     ["Arsenal", 7],
     ["Liverpool", 9],
     ["Southampton", 1],
     ["Man City", 10],
     ["Crystal Palace", 9]]

# write your code here