As usual, create a directory to hold today's activities:
$ mkdir ~/cs170/labs/lab9 $ cd ~/cs170/labs/lab9
Today you are going to start learning some new and exciting Emacs commands! Well, maybe not new, and maybe not exciting. But they will be invaluable in the future.
C-x C-s
C-x C-f
C-x C-c
M-g M-g
M-;
In computer science, we tend to come across the same (or at least very similar) problems time and time again. Instead of coming up with a unique solution every time, we can apply a well-defined sequence of events, known as an algorithm, to the problem at hand.
There is usually more than one way to skin a cat, however. So for a given problem there might be multiple algorithms that result in the same solution. So at some point, we need to be able to compare these algorithms. That is what we are going to start with today.
As you saw in the textbook, insertion sort is a fairly straight forward algorithm that you are probably fairly familiar with. You've seen how the algorithm works, so now it is time to actually implement the algorithm.
Create a file called sorting.py, which you will store all of
the sorting algorithms you write this semester in. Create a function
called insertion_sort(a_list), which takes a list of
integers, and returns a copy of a_list in sorted order. You should
implement the insertion sort algorithm discussed in the textbook.
Make sure you test your function on several lists of various sizes, just to make sure that it works correctly.
my_list = [5, 4, 3, 2, 1] my_sorted_list = insertion_sort(my_list) print(my_list) #Prints [5, 4, 3, 2, 1] print(my_sorted_list) #Prints [1, 2, 3, 4, 5] my_list = [4, 2, 1, 3, 5] my_sorted_list = insertion_sort(my_list) print(my_list) #Prints [4, 2, 1, 3, 5] print(my_sorted_list) #Prints [1, 2, 3, 4, 5]
You will need to nest for loops for this code to work. Both of these should use indicies of the list, as opposed to iterating through the elements.
Your external for loop is going to identify not only the end of the sorted segment of the list, but also the item that you are currently trying to place into the sorted segment.
Your internal for loop will loop through the sorted segment, looking for where the item specified by the external for loop should go.
You will need to write some mechanism that will shift elements down in the list, without losing any information. The safest way to do this is to store the integer in the last position of the list, and work backwards copying from the back of the list to the front.
There is one thing about Python's list slicing syntax that we have not covered yet, since it does not have a lot of real uses. However, it is incredibly useful for shifting subsets of elements, so insertion sort is actually the perfect time to pick it up.
You can use list slicing to assign lists to a subset of a list. If you use the slicing syntax on the left side of the assignment operator, you place an entire list into some subset of the current list! So, instead of needing a loop for your copying, you can simply use the slicing syntax!
my_list = [5, 4, 3, 2, 1] shift_element = my_list[3] print(shift_element) #Prints 2 my_list[1:4] = my_list[0:3] print(my_list) #Prints [5, 5, 4, 3, 1] my_list[0] = shift_element print(my_list) #Prints[2, 5, 4, 3, 1]
Another sorting algorithm is known as selection sort. Both insertion sort and selection sort operate in the same manner. They both keep a sorted sub-list of elements. The key difference between the two is the contents of this sub-list. The insertion sort algorithm sorts the first n elements of the original list. Selection sort finds the smallest n elements of the entire list.
In your sorting.py file, create a function
called selection_sort(a_list). This function takes a
list of integers (or really anything that can be compared using the
comparison operators), and returns a sorted copy of a_list
using the selection sort algorithm.
The selection sort algorithm starts by finding the minimum element of the entire list. This minimum element is swapped with the element at the 0th index of the list. Then, the second smallest element is found, and swapped with the element at the 1st index of the list. This process continues for every location in the list.
my_list = [5, 4, 3, 2, 1] my_sorted_list = selection_sort(my_list) print(my_list) #Prints [5, 4, 3, 2, 1] print(my_sorted_list) #Prints [1, 2, 3, 4, 5] my_list = [4, 2, 1, 3, 5] my_sorted_list = selection_sort(my_list) print(my_list) #Prints [4, 2, 1, 3, 5] print(my_sorted_list) #Prints [1, 2, 3, 4, 5]
You will need a for loop that iterates through the indicies of a_list. This for loop is going to identify the location where you are placing the minimum element.
Inside this for loop, you need another for loop which will identify the minimum element of the list. This is the element you will be placing in the index identified by the first for loop.
After you have moved the minimum element to the 0th location of the list, you can find the 2nd smallest element by finding the minimum element of the now "unsorted" sub-list; The list of elements from index 1 to the end of the list. You can continute to do this process for every iteration.
You have now implemented two different sorting algorithms. However, you might have guessed that both of them have the same Big-Oh class. Let's think of another algorithm. Maybe it has a better Big-Oh class.
Based on the law of probability, if you shuffle a list enough you are bound to eventually get a sorted version of the list. This is the key notion behind bogo sort. In bogo sort, you simply randomly shuffle the list until you end up with the sorted copy.
Implement bogo sort the the same way you implemented selection and insertion sort. Make sure you adequately test your code. In the comments of your file, describe how you think bogo sort compares to selection and insertion sorts, based on their Big-Oh classes. You do not have to define the actual Big-Oh class of bogo, but it might be worth while to have an intuition for what it might be.
When you have finished, create a tar file of your lab9
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab9.tgz lab9/
To submit your activity, go to inquire.roanoke.edu. You should
see an available assignment called Lab Assignment 9.
Make sure you include a header listing the authors of the file.