As usual, create a directory to hold today's activities:
$ mkdir ~/cs170/labs/lab16 $ cd ~/cs170/labs/lab16
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.
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.cc, which you will store all of
the sorting algorithms you write this semester in. Create a function
called int * insertion_sort(int * a_list, int size), 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 lecture.
Make sure you test your function on several lists of various sizes, just to make sure that it works correctly.
int * my_list = new int[5];
for(int i = 0; i < 5; i++) {
my_list[i] = 5 - i;
}
int * my_sorted_list = insertion_sort(my_list, 5);
printList(my_list); #Prints [5, 4, 3, 2, 1]
printList(my_sorted_list); #Prints [1, 2, 3, 4, 5]
delete[] my_sorted_list;
int my_list2[5] = {4, 2, 1, 3, 5};
my_sorted_list = insertion_sort(my_list2, 5);
printList(my_list2); #Prints [4, 2, 1, 3, 5]
printList(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.
Another sorting algorithm is known as bubble sort. Bubble sort may seem slightly more inefficient compared to insertion sort. For each iteration of bubble sort, it swaps 2 adjacent elements in the list if they are not in the correct order. It essentially does this until the entire list is sorted.
In your sorting.py file, create a function
called int * bubble_sort(int * a_list, int size). This
function takes an array of integers,
and returns a sorted copy of a_list
using the bubble sort algorithm.
int * my_list = new int[5];
for(int i = 0; i < 5; i++) {
my_list[i] = 5 - i;
}
int * my_sorted_list = bubble_sort(my_list, 5);
printList(my_list); #Prints [5, 4, 3, 2, 1]
printList(my_sorted_list); #Prints [1, 2, 3, 4, 5]
delete[] my_sorted_list;
int my_list2[5] = {4, 2, 1, 3, 5};
my_sorted_list = bubble_sort(my_list2, 5);
printList(my_list2); #Prints [4, 2, 1, 3, 5]
printList(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 last location you should compare with.
Inside this for loop, you need another for loop which will iterate up to, but not including this last location to compare.
During each iteration of the inside for loop, you should compare two adjacent locations in the array. If they are out of order, swap them.
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 bubble 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.