CS 115 Lab 11, Part B: Selection Sort

[Back to lab instructions]


Setup

Make a new copy of your lab11a.py file. Name it lab11b.py.


Implement selection sort

  1. Add the following function definition for selection_sort:
    def selection_sort(L):
        '''
        Use the selection sort algorithm to sort a list.
        Parameter: unsorted list
        Sorts the original list that was passed to it -- doesn't return anything.
        '''
        pass
  2. Inside the definition of selection_sort, add a line of code that calls your find_index_of_min function to find the index of the minimum element in the entire list and saves it to a variable.
  3. Inside the definition of selection_sort, add a line of code that swaps the first element of the list with the minimum element of the list.
  4. At the end of main, add a call to selection_sort followed by a second call to print_list:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    
    The new list of cities is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Santa Rosa
  5. Inside the definition of selection_sort, add a line of code that prints the two elements that were swapped:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    Swapped elements 0 and 4 -- Santa Rosa and Healdsburg
    
    The new list of cities is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Santa Rosa
  6. Inside selection_sort, move your code into a loop that makes N-1 passes through the list instead of just one pass (where N is the number of elements). In each iteration, you should modify your code to do these three things: Sample output:
    Name of input file: cities-small.txt
    
    The original list of cities is:
    0: Santa Rosa
    1: Petaluma
    2: Rohnert Park
    3: Windsor
    4: Healdsburg
    Swapped elements 0 and 4 -- Santa Rosa and Healdsburg
    Swapped elements 1 and 1 -- Petaluma and Petaluma
    Swapped elements 2 and 2 -- Rohnert Park and Rohnert Park
    Swapped elements 3 and 4 -- Windsor and Santa Rosa
    
    The new list of cities is:
    0: Healdsburg
    1: Petaluma
    2: Rohnert Park
    3: Santa Rosa
    4: Windsor
  7. Answer Question 6 in your writeup.
  8. Run your program on cities.txt, and answer Question 7 in your writeup.
  9. Continue to Part C.