a) Selection sort
[6, 5, 4, 3, 7, 1, 2] [1, 5, 4, 3, 7, 6, 2] [1, 2, 4, 3, 7, 6, 5] [1, 2, 3, 4, 7, 6, 5] [1, 2, 3, 4, 7, 6, 5] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7]
b) Insertion sort
[1, 5, 4, 3, 7, 6, 2] [1, 2, 4, 3, 7, 6, 5] [1, 2, 3, 4, 7, 6, 5] [1, 2, 3, 4, 7, 6, 5] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7] [1, 2, 3, 4, 5, 6, 7]
a) The list is traversed, pairs of elements are compared, and smaller elements are swapped into the lower position.
b)
For each index i from the right end of the list to the left
for each index j from i down to 1
if the pair of items at indices j and j - 1 are out of order
swap them
c)
def bubble_sort_2(L):
"""Reorder the values in L from smallest to largest."""
for i in range(0, len(L)):
for j in range(len(L) - 1, i, -1):
if L[j] < L[j - 1]:
L[j], L[j - 1] = L[j - 1], L[j]
d)
import nose
import bubble_sort
def test_empty():
'''Test bubble_sort_2 on an empty list.'''
L = []
bubble_sort.bubble_sort_2(L)
assert L == []
def test_one():
'''Test bubble_sort_2 on an list of length one.'''
L = [1]
bubble_sort.bubble_sort_2(L)
assert L == [1]
def test_sorted_two():
'''Test bubble_sort_2 on a sorted list of length two.'''
L = [1, 2]
bubble_sort.bubble_sort_2(L)
assert L == [1, 2]
def test_unsorted_two():
'''Test bubble_sort_2 on an unsorted list of length two.'''
L = [2, 1]
bubble_sort.bubble_sort_2(L)
assert L == [1, 2]
def test_unsorted_many():
'''Test bubble_sort_2 on an unsorted list of several items.'''
L = [2, 1, 6, 3, 1]
bubble_sort.bubble_sort_2(L)
assert L == [1, 1, 2, 3, 6]
if __name__ == '__main__':
nose.runmodule()
The timing program on pg 222 actually does compare our
sorting functions with Python's built-in list.sort, so
please replace the entire question with the following:
How many comparisons and copies will selection sort and insertion sort do if they are given a list of length N that is already in sorted order? How many operations of each kind will they perform if the list is in reverse order (i.e., highest to lowest)? What if all of the values in the input list are the same?
This question a deep discussion of loop invariants that didn't make it into the final book, so please replace it with the following:
The slowsort algorithm works as follows:
while not is_sorted(L):
L = randomize(L) # reorder the elements of L at random
What is the expected running time of this algorithm for a list of
length N if the elements of the list are unique (i.e., if no element
appears more than once)? Why does it matter whether the elements are
unique or not?