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 assertEqual(want, got):
if want == got:
print("Test case passed.")
return
print()
print("--------- Test case failed. ---------")
print(f"Want: {repr(want)} (type: {type(want).__name__})")
print(f"Got: {repr(got)} (type: {type(got).__name__})")
print("-------------------------------------")
print()
```

**Insertion sort** is a simple sorting algorithm. The general idea is to move all elements from the given list into a new list, while keeping the new list sorted. This is the pseudocode for a given list `lst`

.

- Create a new empty list
`new_lst`

- For each element
`x`

in`lst`

, add`x`

to`new_lst`

-- while keeping`new_lst`

sorted. More specifically, insert`x`

immediately before the first element in`new_lst`

that is larger than`x`

.

For example if you want to sort the list,

`L = [8, 5, 7, 1, 9, 3]`

using insertion sort, it would look like this

`L = [ 8, 5, 7, 1, 9, 3]; new_list = []`

`L = [ 5, 7, 1, 9, 3]; new_list = [8]`

`L = [ 7, 1, 9, 3]; new_list = [5, 8]`

since 5 is less than 8, we inserted it before 8.

`L = [ 1, 9, 3]; new_list = [5, 7, 8]`

since 7 is greater than 5 but less than 8, we inserted it between 5 and 8.

`L = [ 9, 3]; new_list = [1, 5, 7, 8]`

`L = [ 3]; new_list = [1, 5, 7, 8, 9]`

`L = [ ]; new_list = [1, 3, 5, 7, 8, 9]`

The key challenge in implementing insertion sort is inserting elements from the original list `lst`

int `new_lst`

**while keeping new_lst sorted**; we'll need to manipulate

`new_lst`

using list slicing to insert each element into the correct position.So first, let's go back and recall list slicing and concatanating. If you're given the list `L = [1, 2, 4]`

and you want to insert the element `3`

into the list such that `L`

remains sorted, you can do

`L = L[0:2] + [3] + L[2:]`

to get`L = [1,2,3,4]`

.

Why? Because `L[0:2] = [1,2]`

and `L[2:] = [4]`

. Therefore,
`L[0:2] + [3] + L[2:]`

is the same thing as `[1, 2] + [3] + [4]`

.

Below, you are asked to insert `7`

, `13`

, `17`

, and `23`

in to the correct position in `L`

(after all insertions, `L`

should be sorted).

In [ ]:

```
L = [2, 5, 11, 15, 16, 19, 21]
```

In [ ]:

```
#Write your solution here. Insert 7, 13, 17 and 23.
```

In [ ]:

```
# TEST_CASE
expected = [2, 5, 11, 15, 16, 19, 21, 7, 13, 17, 23]
print(L == expected)
```

When we use `insertion sort`

, we need to find the list of elements that are less than the element we are trying to insert so we can insert the element right after the elements that are less than it and add the rest of the elements after we add the new element. (Similar to what we did in 1.1) Get all the elements that are less than the numbers we are trying to insert, add the number and add the rest of elements.

Try to write a function `less(L, k)`

that takes a sorted list `L`

and returns a list of all the elements of `L`

that are less than `k`

.

For example, given a list `[1, 4, 7, 9, 10]`

and `k = 8`

, the function would return the list `[1, 4, 7]`

.

In [ ]:

```
def less(L, k):
"""Returns a list of elements from L that are less than k.
Arguments:
L (list of ints)
k (int): An integer
Returns: (sorted list of ints)
Effects: None.
"""
#Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [1, 4, 7, 9, 10, 13, 15]
k = 12
assertEqual(less(L, k), [1, 4, 7, 9, 10])
k = 0
assertEqual(less(L, k), [])
k = 16
assertEqual(less(L, k), [1, 4, 7, 9, 10, 13, 15])
```

Now let's write a function that is similar to the one we wrote in 1.3 but here instead of returning the list of elements that are less than k, let's return the index of the largest element that is less than k.

If we have a list, `L = [1,2,5,7,9,13]`

and `k = 10`

, the largest element that is less than `10`

from the list `L`

is `9`

, and the function should return the index of `9`

that is `4`

.

If all the elements in `L`

are greater than `k`

, the function should return `-1`

.

Now, write a function `find_position(L, k)`

that finds the position of the greatest item in `L`

that is less that `k`

:

For example :

`find_position([1, 2, 4, 5], 3)`

should return`1`

because`2`

is the greatest item less than`3`

and is in position`1`

.

`find_position([9, 10, 11, 13, 14], 12)`

should return`2`

.

In [ ]:

```
def find_position(L, k):
"""Returns the index of the greatest number that is less than k.
Arguments:
L (sorted list of ints)
k (int)
Returns: (int)
Effects: None.
"""
# Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [1, 2, 4, 5]
k = 3
assertEqual(find_position,(L,k), 1)
L = [9, 10, 11, 13, 14]
k = 12
assertEqual(find_position(L, k), 2)
L = [9, 10, 11, 13, 14]
k = 8
assertEqual(find_position(L, k), -1)
L = [9, 10, 11, 13, 14]
k = 15
assertEqual(find_position(L, k), 4)
```

Using `find_position(L, k)`

, write a function `insert(L, k)`

that inserts `k`

into a sorted list `L`

. (Hint: what does find_position return?)

As input the function takes `k`

, the element to insert and `L`

, the sorted list to insert `k`

into.

For example:

```
insert([4,6,8,9], 5)
- Needs to find the position of the largest element that is less than 5(find_position)
- Then insert 5 next to the largest element that is less than 5(which is 4)
- Therefore the output should look like [4,5,6,8,9]
insert([2,5,6,9,10,34], 8)(Think about the output of this one)
```

In [ ]:

```
def insert(L, k):
"""Inserts k at the right position in L where L remains sorted.
Arguments:
L (sorted list of ints)
k (int)
Returns: (sorted list of ints)
Effects: Updates the List L.
"""
#Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [4, 6, 8, 9]
k = 5
assertEqual(insert([4, 6, 8, 9], 5), [4, 5, 6, 8, 9])
L = [2, 5, 6, 9, 10, 34]
k = 35
assertEqual(insert(L, k), [2, 5, 6, 9, 10, 34, 35])
L = [2, 5, 6, 9, 10, 34]
k = 1
assertEqual(insert(L, k), [1, 2, 5, 6, 9, 10, 34])
```

WATCH THIS VIDEO (CLICK ME)

Here is the pseudo-code for insertion sort:

- Create an empty list,
`new_lst`

- Then add the first element from
`L`

to`new_lst`

- Then add the rest of the elements to
`new_lst`

at the right location(Hint: Use`insert(L, k)`

)

Write a function `insertion_sort(L)`

that takes a list `L`

and inserts elements of `L`

in a new list using `insert(L, k)`

.

Here is how the function should work :

`L = [ 8, 5, 7, 1, 9, 3]`

and `new_list = [] `

`L = [ 5, 7, 1, 9, 3]`

and `new_list = [8] `

`L = [ 7, 1, 9, 3]`

and `new_list = [5, 8] `

`L = [ 1, 9, 3]`

and `new_list = [5, 7, 8] `

`L = [ 9, 3]`

and `new_list = [1, 5, 7, 8] `

`L = [ 3]`

and `new_list = [1, 5, 7, 8, 9] `

`L = [ ]`

and `new_list = [1, 3, 5, 7, 8, 9] `

In [ ]:

```
def insertion_sort(L):
"""Sorts L using insertion sort algorithm(watch video).
Arguments: L (list of ints)
Returns: (list of ints)
Effects: Sorts the list
"""
#Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [1, 4, 5, 3, 2, 7, 0]
assertEqual(insertion_sort(L), [0, 1, 2, 3, 4, 5, 7])
L = [1, 4, 5, 3, 2, 0, 7]
assertEqual(insertion_sort(L), [0, 1, 2, 3, 4, 5, 7])
L = [5, 6, 11, 12, 13]
assertEqual(insertion_sort(L), [5, 6, 11, 12, 13])
L = [12, 11, 13, 5, 6]
assertEqual(insertion_sort(L), [5, 6, 11, 12, 13])
```

**Selection Sort** works by finding the minimun element from the list `L`

and swaping it with the first element.

- Find the smallest element from the list
- Swap it with the element at
`index 0`

- Find the second smallest element and swap it with the element at
`index 1`

. - Repeat until list is sorted.

For example,

`L = [8, 5, 7, 1, 9, 3]`

`L = [1, 5, 7, 8, 9, 3]`

#Swapped 8 and 1

`L = [1, 3, 7, 8, 9, 5]`

#Swapped 5 and 3

`L = [1, 3, 5, 8, 9, 7]`

#Swapped 7 and 5

`L = [1, 3, 5, 7, 9, 8]`

#Swapped 8 and 7

`L = [1, 3, 5, 7, 8, 9]`

#Swapped 8 and 9

Write a function `min_index(L)`

that takes a list `L`

and returns the position of the smallest integer in `L`

. Hint: you should use a `for`

loop!

For example, in the list `[66, 94, 71, 53]`

the result would be `3`

since the smallest integer is `53`

.

In [ ]:

```
def min_index(L):
"""Returns the index of the smallest element in L.
Arguments: L (list of ints)
Returns: (int)
Effects: None
"""
# Write your solution here
return
club_points_list = [66, 67, 71, 94, 95, 70, 53, 98, 96, 101, 88, 78]
print(min_index(club_points_list) == 6)
```

In [ ]:

```
# TEST_CASE
L = [2, 5, 98, 1, 0, 67]
assertEqual(min_index(L), 4)
M = [3, 6, 1, 0, 7, 9]
assertEqual(min_index(M), 3)
```

WATCH THIS VIDEO (CLICK ME)

Write a function, using a for loop, `selection_sort(L)`

that takes a list `L`

and sorts elements of `L`

using selection sort.

Hint use: the `min_index(L)`

function you defined above

Here is how the function should work :

`L = [8, 5, 7, 1, 9, 3]`

`L = [1, 5, 7, 8, 9, 3]`

`L = [1, 3, 7, 8, 9, 5]`

`L = [1, 3, 5, 8, 9, 7]`

`L = [1, 3, 5, 7, 9, 8]`

`L = [1, 3, 5, 7, 8, 9]`

Your code should work like this:

- Find the index of the smallest element from the list
- Swap it with the
`0th`

element - Then find the smallest element from the same list but without the first element (because it is the smallest and we want it right there)

In [ ]:

```
def selection_sort(L):
"""Sorts L using selection sort algorithm (watch video).
Arguments:
L (list of ints)
Returns: (list of ints)
Effects: Sorts the list
"""
#Write Your Code Here
return
```

In [ ]:

```
# TEST_CASE
L = [1, 54, 6, 7, 90, 0, 20]
expected = [0, 1, 6, 7, 20, 54, 90]
assertEqual(selection_sort(L), expected)
L = [2, 5, 3, 0, 91, 73, 56, 2, 93, 10, 10]
expected = [0, 2, 2, 3, 5, 10, 10, 56, 73, 91, 93]
assertEqual(selection_sort(L), expected)
L = [9, 5, 4, 9]
expected = [4, 5, 9, 9]
assertEqual(selection_sort(L), expected)
```

Write the same function but using recursion. (`selection_sort_rec(L)`

).

Hint: you should use the function `min_index(L)`

from 2.1.

For example, if you have an array `[1, 3, 0, 2, 9]`

the output of the recursive sort function should be `[0, 1, 2, 3, 9]`

In [ ]:

```
def selection_sort_rec(L):
"""Sorts L using selection sort algorithm(watch video).
Arguments:
L (list of ints)
Returns: (sorted list of ints)
Effects: Sorts the list
"""
#Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [1, 54, 6, 7, 90, 0, 20]
expected = [0, 1, 6, 7, 20, 54, 90]
assertEqual(selection_sort_rec(L), expected)
L = [2, 5, 3, 0, 91, 73, 56, 2, 93, 10, 10]
expected = [0, 2, 2, 3, 5, 10, 10, 56, 73, 91, 93]
assertEqual(selection_sort_rec(L), expected)
L = [9, 5, 4, 9]
expected = [4, 5, 9, 9]
assertEqual(selection_sort_rec(L), expected)
```

The **median** element of a list `L`

is the element whose value is "right in the middle" of the list; that is, it is smaller or equal to half of the elements in `L`

.

For example,

The median of `[1, 2, 4, 5, 6]`

is `4`

.

The median of `[7, 5, 4, 1, 3, 2, 4, 9, 9, 7]`

is `5`

.

Write a function `median(L)`

that takes a list `L`

and returns the median of the list `L`

.
Hint : The list `L`

is not sorted. You need to use your sort function from 1.1 (`recursive_sort`

)

In [ ]:

```
def median(L):
"""Find the median in list L.
Arguments: L (list of ints)
Returns: (int)
Effects: None
"""
#Write your solution here
return
print(median(club_points_list) == 88)
print(median([1, 2, 3]) == 2)
print(median([1]) == 1)
print(median([5, 4, 1, 4, 3]) == 4)
```

In [ ]:

```
#TEST_CASE
L=[7, 5, 4, 1, 3, 2, 4, 9, 9, 7]
assertEqual(median(L), 5)
M=[4, 6, 78, 90, 12, 43, 9]
assertEqual(median(M), 12)
```

We want to sort a list of points (x, y) in a plane. For example `L = [[2, 3], [4, 5], [6, 3], [4, 0]]`

.

We define the order of the points as `[a, b] < [c, d]`

if `a+b < c+d`

. In other words, a point is smaller than an other point if the sum of the coordinates is smaller. (`[2,3] > [3,0]`

, because `2+3 > 3+0`

)

So according to this ordering, the list `[[4, 0], [2, 3], [6, 3], [4, 5]]`

is a sorted one.

Modify the function `min_index(L)`

from 2.1 so that `recursive_sort`

from 2.3 works for sorting points.

In [ ]:

```
def sort_points(L):
"""Sorts L.
Arguments:
L (list): A list that contains points([x, y] coordinates).
Returns: (list) the sorted list.
Effects: Sorts the list
"""
#Write your solution here
return
```

In [ ]:

```
# TEST_CASE
L = [[2, 3], [4, 5], [6, 3], [4, 0]]
expected = [[4, 0], [2, 3], [6, 3], [4, 5]]
assertEqual(sort_points(L), expected)
L = [[0, 3], [3, 0], [2, 1], [1, 2]]
expected = [[0, 3], [3, 0], [2, 1], [1, 2]]
assertEqual(sort_points(L), expected)
```