# RUN THIS BLOCK OF CODE BEFORE RUNNING ANY CELLS
def check_test(actual, expected):
if expected != actual:
print(f"The expected value is {expected}, but the actual value is {actual}")
else:
print(f"Congratulations, the test case passed!")
In the main exercises we have been implementing selection sort both iteratively and recursively. (If you haven't finished the main exercises, finish them before moving on here!)
What is the time complexity of the selection sort algorithm in the best and worst cases? Explain your solution. Feel free to use your implementation from the main exercises, and try running it on different inputs to see whether it is faster on certain inputs.
Best case: your answer here in English
Worst case: your answer here in English
Ask a TA to check your answer!
In this exercise, you will implement the bubble sort algorithm.
Bubble Sort is a simple sorting algorithm that works by repeatedly stepping through the list, comparing each pair of adjacent items, and swapping them if they are in the wrong order. The pass through the list is repeated until no more swaps are needed.
Here's how the algorithm works:
Task: Implement a function called bubble_sort
that takes a list and returns the sorted list using the bubble sort algorithm. You should NOT use Python's built-in sorting functions or any libraries in your implementation.
Hint: You will need to use a nested loop to implement this algorithm. The outer loop will control the number of passes through the list. The inner loop will control the comparisons and swaps.
# Provide your solution here
def bubble_sort(lst):
# Your code here
# Please implement the algorithm **in-place**, i.e. do not create a new list
# but modify the input list `lst` directly, and return nothing.
pass
# Test cases
L = [3, 1, 0, -3, 2, 5]
expected = sorted(L)
bubble_sort(L) # in-place sorting
check_test(L, expected)
L = [-100, 9, -1, 3, 1, 0, -3, 2, 5, 5, 5, 5, 5, 1, 100, -100]
expected = sorted(L)
bubble_sort(L) # in-place sorting
check_test(L, expected)
L = [6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6]
expected = sorted(L)
bubble_sort(L) # in-place sorting
check_test(L, expected)
The expected value is [-3, 0, 1, 2, 3, 5], but the actual value is [3, 1, 0, -3, 2, 5] The expected value is [-100, -100, -3, -1, 0, 1, 1, 2, 3, 5, 5, 5, 5, 5, 9, 100], but the actual value is [-100, 9, -1, 3, 1, 0, -3, 2, 5, 5, 5, 5, 5, 1, 100, -100] The expected value is [-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6], but the actual value is [6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6]
What is the time complexity of the bubble sort algorithm in the best and worst cases? Please explain your answer.
Best case: your answer here in English
Worst case: your answer here in English
Ask a TA to check your answer!
Implement a Python function for insertion sort, but this time, it should sort the list in reverse order (descending).
def reverse_insertion_sort(lst):
# Your code here
# Please implement the algorithm **in-place**, i.e. do not create a new list
# but modify the input list `lst` directly, and return nothing.
# Hint: you may want to use the `insert` method of the list.
pass
# Test cases
L = [3, 1, 0, -3, 2, 5]
expected = list(reversed((sorted(L))))
reverse_insertion_sort(L) # in-place sorting
check_test(L, expected)
L = [-100, 9, -1, 3, 1, 0, -3, 2, 5, 5, 5, 5, 5, 1, 100, -100]
expected = list(reversed((sorted(L))))
reverse_insertion_sort(L) # in-place sorting
check_test(L, expected)
L = [1, 2, 3, 4, 5]
expected = list(reversed((sorted(L))))
reverse_insertion_sort(L) # in-place sorting
check_test(L, expected)
The expected value is [5, 3, 2, 1, 0, -3], but the actual value is [3, 1, 0, -3, 2, 5] The expected value is [100, 9, 5, 5, 5, 5, 5, 3, 2, 1, 1, 0, -1, -3, -100, -100], but the actual value is [-100, 9, -1, 3, 1, 0, -3, 2, 5, 5, 5, 5, 5, 1, 100, -100] The expected value is [5, 4, 3, 2, 1], but the actual value is [1, 2, 3, 4, 5]
Design a Python function for adaptive insertion sort. The function should take an already sorted list as input and efficiently handle newly added elements, keeping the list sorted in real-time.
The function should have the following signature:
def adaptive_insertion_sort(A, new_elem):
# Your code here
# Returns the sorted list (can be in-place so that A is sorted)
return A
# Test cases
L = [1, 2, 3, 4, 4, 10, 20]
new_L = adaptive_insertion_sort(L, 3)
check_test(actual=new_L, expected=[1, 2, 3, 3, 4, 4, 10, 20])
L = [1, 1, 5, 5, 100]
new_L = adaptive_insertion_sort(L, 500)
check_test(actual=new_L, expected=[1, 1, 5, 5, 100, 500])
L = [0, 10, 20, 40, 40]
new_L = adaptive_insertion_sort(L, 0)
check_test(actual=new_L, expected=[0, 0, 10, 20, 40, 40])
The expected value is [1, 2, 3, 3, 4, 4, 10, 20], but the actual value is [1, 2, 3, 4, 4, 10, 20] The expected value is [1, 1, 5, 5, 100, 500], but the actual value is [1, 1, 5, 5, 100] The expected value is [0, 0, 10, 20, 40, 40], but the actual value is [0, 10, 20, 40, 40]
Write a Python function that takes an unsorted list of positive integers as input and returns the number of comparisons and swaps performed during the insertion sort algorithm.
By the number of comparisons, we mean that you should count the number of times that the algorithm compares two elements of the list.
By the number of swaps, we mean that you should count the number of times that the algorithm swaps two elements of the list to do the insertion.
For exampele:
The input list is [10, 2, 8, 6, 7, 3]
.
2
. It is smaller than 10
, so we swap 2
and 10
. This is 1 comparison and 1 swap. The list becomes [2, 10, 8, 6, 7, 3]
.8
. It is smaller than 10
but greater than 2
, so we swap 8
and 10
. This is 2 comparisons (one with 10
and one with 2
) and 1 swap. The list becomes [2, 8, 10, 6, 7, 3]
.6
. It is smaller than 10
, and also smaller than 8
, but not 2
, so we swap 6
with both 10
and 8
. This is 3 comparisons (with 10
, 8
, and 2
) and 2 swaps. The list becomes [2, 6, 8, 10, 7, 3]
.7
. It is smaller than 10
, and smaller than 8
, but not 6
, so we swap 7
with both 10
and 8
. This is another 3 comparisons (with 10
, 8
, and 6
) and 2 swaps. The list becomes [2, 6, 7, 8, 10, 3]
.3
. It is smaller than all other numbers, so we swap 3
with 10
, 8
, 7
, and 6
. This is 5 comparisons (with 10
, 8
, 7
, 6
, and 2
) and 4 swaps. The list becomes [2, 3, 6, 7, 8, 10]
.In total, there is 14 comparisons and 10 swaps.
def count_comparisons(L):
"""Count the number of comparisons used by insertion sort to sort L.
Returns int, the number of comparisons used by insertion sort.
"""
return -1
def count_swaps(L):
"""Count the number of swaps used by insertion sort to sort L.
Returns int, the number of swaps used by insertion sort.
"""
return -1
# Test cases
L1 = [10, 2, 8, 6, 7, 3]
check_test(count_comparisons(L1), 14)
check_test(count_swaps(L1), 10)
L2 = [1, 2, 3, 4, 5] # already sorted
check_test(count_comparisons(L2), 4)
check_test(count_swaps(L2), 0)
L3 = [5, 4, 3, 2, 1] # reverse sorted
check_test(count_comparisons(L3), 10)
check_test(count_swaps(L3), 10)
L5 = [1] # single element
check_test(count_comparisons(L5), 0)
check_test(count_swaps(L5), 0)
The expected value is 14, but the actual value is -1 The expected value is 10, but the actual value is -1 The expected value is 4, but the actual value is -1 The expected value is 0, but the actual value is -1 The expected value is 10, but the actual value is -1 The expected value is 10, but the actual value is -1 The expected value is 0, but the actual value is -1 The expected value is 0, but the actual value is -1
Cocktail sort is a variation of bubble sort. The algorithm differs from bubble sort in that it sorts in both directions on each pass through the list.
Here's how the algorithm works:
Write a function called cocktail_sort
that takes a list of numbers as input and returns a new list that contains the same numbers, sorted in ascending order using cocktail sort.
def cocktail_sort(lst):
# Your code here
# Please implement the algorithm **in-place**, i.e. do not create a new list
# but modify the input list `lst` directly, and return nothing.
pass
lst1 = [4, 3, 2, 1]
cocktail_sort(lst1)
check_test(lst1, [1, 2, 3, 4])
lst2 = [5, -1, 6, 2, -3]
cocktail_sort(lst2)
check_test(lst2, [-3, -1, 2, 5, 6])
lst3 = [1, 2, 3, 4, 3]
cocktail_sort(lst3)
check_test(lst3, [1, 2, 3, 3, 4])
The expected value is [1, 2, 3, 4], but the actual value is [4, 3, 2, 1] The expected value is [-3, -1, 2, 5, 6], but the actual value is [5, -1, 6, 2, -3] The expected value is [1, 2, 3, 3, 4], but the actual value is [1, 2, 3, 4, 3]
What is the time complexity of the cocktail sort algorithm in the best and worst cases? Please explain your answer.
Best case: your answer here in English
Worst case: your answer here in English
Ask a TA to check your answer!
Reference: https://arxiv.org/pdf/2110.01111.pdf by Stanley P. Y. Fung
Consider the following "sorting algorithm" that does in-place sorting of a list of numbers:
def i_cant_believe_it_can_sort(lst):
n = len(lst)
for i in range(n):
for j in range(n):
if lst[i] < lst[j]:
# Swap two elements
lst[i], lst[j] = lst[j], lst[i]
This algorithm looks weird on multiple levels:
i
and j
can be 0)lst[i]
is smaller than lst[j]
??It just seems like we are incorrectly implementing Insertion Sort...
But it works! Check the following:
L = [3, 1, 0, -3, 2, 5]
expected = sorted(L)
i_cant_believe_it_can_sort(L)
check_test(L, expected)
L = [-1, 3, 1, 0, -3, 2, 5, 5, 5, 5, 5, 1, 100, -100]
expected = sorted(L)
i_cant_believe_it_can_sort(L)
check_test(L, expected)
L = [-100, 9, -1, 3, 1, 0, -3, 2, 5, 5, 5, 5, 5, 1, 100, -100]
expected = sorted(L)
i_cant_believe_it_can_sort(L)
check_test(L, expected)
L = [6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6]
expected = sorted(L)
i_cant_believe_it_can_sort(L)
check_test(L, expected)
Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed! Congratulations, the test case passed!
Read https://arxiv.org/pdf/2110.01111.pdf if you are curious.
# Your answer here: