Lab 7: F2020; CS145; Modified from Lab W.

sorting_lab_xyz.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!
    """
    pass
    
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_sorted(xs):
    """
    Given a list, "xs", repeatedly remove the minimum element
    and add it to a new output list. You can stop when there are
    no more elements in the original list.
    
    To remove the minimum element:
     1. find the position of it.
     2. call ``xs.pop(index)`` to remove an element at index
    
    """
    pass

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