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. Answer Question 2 in your writeup.
4. 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.
5. 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

6. 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

7. 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:
   • Call find_index_of_min to find the smallest element in the unsorted part of the list.
   • Swap that element with the first element in the unsorted part of the list.
   • Print the two elements that were swapped.
   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

8. Answer Question 3 in your writeup.
9. Run your program on cities.txt, and answer Question 4 in your writeup.
10. Continue to Part C.