CS 115 Lab 11, Part A: Find the minimum element of a list

[Back to lab instructions]

Overview

We are going to write our own sorting function using an algorithm called selection sort.

In selection sort, for a list of length N, we make (N-1) passes over the list.

On the first pass, we find the minimum element and swap it with the element at position 0. On the second pass, we find the second-smallest element and swap it with the element in position 1, and so on.

For a visual summary of selection sort, see http://www.algolist.net/Algorithms/Sorting/Selection_sort.

Getting Started

1. Create a new file called lab11a.py. Copy the definitions of the functions readfile and print_list from your Lab 10 code into your new file.
2. Based on your Lab 10 code, define a main function that does the following:
   • Asks the user for the name of the input file
   • Calls readfile to read the file contents into a list of lines
   • Calls print_list to print the resulting list
3. Test your code using the following sample input:
   

   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

In Lab 11, instead of calling Python's sort() function, you will write code to sort the list yourself using two well-known algorithms.

Finding the Minimum Element

Overview

A key part of selection sort is finding the minimum element of the list. For lists of strings of the same case, the minimum element is the one that comes first alphabetically.

In this part of the lab, you'll write a function to find the index of the minimum element of your list of cities.

Here is an overview of this function:

• The name of the function should be find_index_of_min.
• The function will take one parameter: a list of strings.
• The function will return an integer: the numeric index of the minimum element of the list. (Don't worry about lists with duplicate elements.)

For example, the function call

find_index_of_min(['BBB', 'AAA', 'CCC'])

should return

1

which is the index of the minimum element, 'AAA'.

Instructions

1. Add the following empty function definition to your code:

   def find_index_of_min(L):
       """
       Parameter: a list L
       Returns: the index of the minimum element of the list 
           (returns None if the list is empty)
       """
       pass

2. If you feel ready to write this function on your own, go ahead! Write the function, skip the next step, and go straight to the test cases.
3. To write this function, follow these steps:
   • Begin by immediately returning None if the list L is empty.
   • You'll need a variable -- essentially an accumulator variable -- to keep track of the index of the minimum element you've seen so far. Decide on the appropriate datatype, and initialize this variable to an appropriate value.
   • Write a loop to look at the elements of L:
     • Each iteration, compare an element of L with the minimum value you've seen so far.
     • If the current element of L is smaller than the minimum element you've seen so far, update your accumulator variable.
     • Remember that this variable should hold a numeric value!
   • After you have seen all of the elements of L, return the value of the variable holding the index of the minimum element.
4. Add the following lines of code to the end of main():

       print(find_index_of_min([]))
       print(find_index_of_min([3, 2, 1, 0]))
       print(find_index_of_min(['A', 'Z', 'Y', 'B']))
       print(find_index_of_min(['B', 'A', 'Z', 'Y']))

5. Run your program, and supply any valid filename when prompted. When the last 4 lines of output match your answers to Question 2 in the pre-lab, remove these 4 lines of code.
6. Be sure you are NOT using Python's built-in index function anywhere in your code! It is less efficient than the code you are writing, and it will actually mess you up in subsequent parts of this lab.

Restricting the search

Overview

Next, you will modify find_index_of_min() to find the index of the minimum element starting at an index you specify. For example, the call

find_index_of_min(['B', 'C', 'Z', 'D', 'E'], 2)

would return 3 because you told it to start at index 2, and so it ignores the first two elements of the list.

Instructions

1. Modify the def line for find_index_of_min to take an additional parameter called start_index.
2. Modify the first if-statement in find_index_of_min to return None if the list does not have enough elements to start at start_index.
3. Modify your code inside the definition so that it does not consider any elements before start_index. In particular, look for places in your code where you assumed you were starting at index 0, and change those to start_index.
4. Test your code by adding the following 4 lines to main():

       print(find_index_of_min([], 0))
       print(find_index_of_min([3, 2, 1, 0], 3))
       print(find_index_of_min([3, 2, 1, 0], 4))
       print(find_index_of_min(['A', 'Z', 'Y', 'B'], 1))
       print(find_index_of_min(['B', 'Z', 'A', 'Y'], 2))

   Answer Question 1 in your writeup, and then remove these 5 lines of code.
5. Update the docstring for find_index_of_min to reflect your changes.
6. Continue to Part B.