## Lecture 9- Sorting

As usual, create a directory to hold today's activities:

$mkdir ~/cs170/labs/lab9$ cd ~/cs170/labs/lab9

## Emacs Commands

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
Save current Buffer
C-x C-f
Open a new file
C-x C-c
Close Emacs
M-g M-g
Goto line
M-;
Comment out a region

## Comparing Algorithms and Sorting

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.

Lab Activity 1
Insertion Sort

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.

#### Details

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.

#### Example

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]


#### Hint

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

### Challenge

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]


Lab Activity 2
Selection Sort

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.

#### Details

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.

#### Example

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]


#### Hint

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

### Challenge

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.

#### Submission

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.