Exercises
Walkthrough
For the walkthrough, we’ll write a function that takes two parameters: a sorted list and a new number. The function should return a new list that is the result of inserting the new number into the sorted list in the correct, sorted order.
def insert(sorted_list, num):
# read through list
# find list_num > num
# index of list_num
# x = get slice from start to index
# append num to slice x.append(num)
# add slice [index:] to prev slice x + sorted_list[index:]
# return new list
for idx in range(len(sorted_list)):
if sorted_list[idx] > num:
print("sorted list [idx]", sorted_list[idx])
new_list = sorted_list[:idx]
new_list.append(num)
return new_list + sorted_list[idx:]
sorted_list.append(num)
return sorted_list
print(insert([2,3], 1))
print(insert([1,3], 2))
print(insert([1,2], 3))
Bubble sort
One rite-of-passage in your programming life is to learn a bunch of canonical “sorting” algorithms: procedures for taking a jumbled list of numbers (or anything “sortable”), and putting all the numbers in order.
The simplest such algorithm is called Bubble Sort. The main idea of Bubble Sort is to swap any two successive elements in a list if they are not in order.
For example, the list [2, 1] would be sorted by swapping the 1 and 2 yielding [1, 2].
For a larger list, the swapping is done from front to back with each sequential pair.
Let’s sort the list [3, 5, 2]:
- We first take the 3, 5 pair and compare them. Since 3 < 5, we don’t do anything.
- Our list is still [3, 5, 2].
- The next pair is 5, 2. Since 5 > 2 we swap them in the list.
- Our list is now [3, 2, 5].
- Starting from the beginning again, we have the pair 3, 2, thus we swap again.
- Our list is now [2, 3, 5].
- At this point, the list is fully sorted, but we don’t know that until we actually check.
- So we start from the beginning yet again, but this time, we iterate over the entire list without ever having to perform any swaps. This is how we know the list is fully sorted.
# Sorts a list using bubble sort.
def bubble_sort(lst):
is_sorted = False
sorted_list = []
while is_sorted is False:
nswaps = 0
swap_idx = len(lst) - 1
idx = 0
while idx < len(lst) - 1:
if lst[idx] > lst[ idx + 1 ]:
lst[idx], lst[idx+1] = lst[idx+1], lst[idx]
nswaps = nswaps + 1
swap_idx = idx + 1
#print(idx, len(lst))
#print(lst)
idx += 1
sorted_list = lst[swap_idx:] + sorted_list
#print(sorted_list, "sorted")
lst = lst[:swap_idx]
#print(lst)
if nswaps == 0:
is_sorted = True
return lst + sorted_list
#print(lst)
from test import testEqual
testEqual(bubble_sort([0]), [0]) # Sorts a single element, returns same list
testEqual(bubble_sort([1, 2, 3, 4, 5]), [1, 2, 3, 4, 5]) # Sorted list is the same
testEqual(bubble_sort([5, 4, 3, 2, 1]), [1, 2, 3, 4, 5])
testEqual(bubble_sort([4, 5, 3, 1, 2]), [1, 2, 3, 4, 5])