Lab 7: F2020; CS145

sorting_lab.py

def swap(xs, i, j):
    """
    Proj. 5:
    Given the list xs, swap elements i and j.
    """
    tmp = xs[i]
    xs[i] = xs[j]
    xs[j] = tmp
    
swap_ex = [1,2,3,4]
swap(swap_ex, 0, 2)
assert(swap_ex == [3,2,1,4])
    
def find_minimum_position(xs):
    """
    Practice Exam:
    Given the list "xs", find the position of the minimum element.
    """
    N = len(xs)
    # assume the minimum is the first element:
    min_val = xs[0]
    min_idx = 0
    # loop over the rest of the elements:
    for i in range(1, N):
        # if the current is smaller than our best minimum so far; ditch it
        if xs[i] < min_val:
            min_idx = i
            min_val = xs[i]
    # here's the minimum location!
    return min_idx

min_ex = [4,3,2,1,2,3]
assert(find_minimum_position(min_ex) == 3)
assert(min_ex[find_minimum_position(min_ex)] == 1)

def swap_min_to_front(xs):
    """
    Given a list, xs, find the minimum position,
    and swap it to the first element of the list!
    """
    TODO
    
min_ex = [4,3,2,1,2,3]
swap_min_to_front(min_ex)
assert(min_ex == [1,3,2,4,2,3])

def selection_sort(xs):
    """
    Given a list, xs, swap the minimum to the front.
    Then, look at the list after that point, e.g., xs[1:]
      ...and swap the minimum to the front again.
    Repeat until you have no more elements left.
    """
    TODO
    
sort_me = [7,6,5,4,3,3,2,1]
selection_sort(sort_me)
assert(sort_me == [1,2,3,3,4,5,6,7])