$ mkdir ~/cs170/labs/lab16 $ cd ~/cs170/labs/lab16
I'm finally making good on my promise to make sure you guys get used to emacs by the end of the semester! Starting next Monday, we are going to have short emacs quizzes, where you will simply have to identify the keyboard shortcut for various emacs commands. Each week you will be given 5 random emacs commands from all of the commands we have covered in the semester. You simply need to choose the correct one.
This week, we will start with the most useful commands for efficient use of emacs: Managing Files.
You all have been asking "Is there a binary sort?" Well, the idea behind binary search finds its way into two different algorithms. These are Merge Sort and Quick Sort. They both approach the problem the same way as all of our other recursive functions: Break the problem into smaller portions, and build the overall solution from those smaller pieces.
Merge sort is probably the closest to a "binary" sort as you will get. Merge sort simply splits the list into two halves, and recursively calls Merge sort on both halves. Onces it gets the two sorted halves, it simply merges the two together to form a sorted list.
Copy your sorting.py file from lab13 into this directory:
$ cd ~/cs170/labs/lab16/ $ cp ../lab13/sorting.py .
Create a function called merge_sort(a_list, start, end), which
takes a list of integers, as well as two integers representing the
beginning and end of the portion of the list to be sorted.
This function will not return anything. It will simply re-order the
elements of a_list in place. The algorithm was described in Chapter 2 of the
textbook. The Pseudo code is in Section 2.3.1.
Once you have your function written, try to figure out the Big-Oh class of Merge Sort. Write your estimation in the comments of your file somewhere near your Merge Sort function.
>>> my_list = [5, 4, 3, 2, 1] >>> merge_return_value = merge_sort(my_list, 0, len(my_list)) >>> print(merge_return_value) None >>> print(my_list) [1, 2, 3, 4, 5]
You need to write a function called merge(a_list, start,
end). This function takes a list of comparable items,
and two integers start and end. It does not
return anything: It sorts the items in place in a_list
You will use start and end to denote the two halves of the list. The middle index of the list denotes the beginning of the second half of the list. All you need to do is to compare the elements at the beginning of each half of the list. If they are out of order, swap them and move on to the next elements.
One thing you need to be careful about in the merge procedure is that you could easily run out of items in one list before the other. You need to make sure you gracefully handle this situation.
Your merge_sort function should recursively
call merge sort on each half of the list, then merge the two
halves together.
Once again, there is a more "pythonic" way to accomplish this algorithm. You can easily use list slicing in order to split the list into two halves. Your merge procedure then takes two lists, and returns the merging of both of these lists.
Write a function called merge_sort_slice(a_list), which
performs merge sort using list slicing. This version of merge sort
should return a copy of a_list in sorted order. You will also need a new
merge_slice(list_1, list_2), which returns a new list
that represents the merging of list_1 and list_2.
When you have finished, create a tar file of your lab16
directory. To create a tar file, execute the following commands:
cd ~/cs170/labs tar czvf lab16.tgz lab16/
To submit your activity, go to inquire.roanoke.edu. You should
see an available assignment called Lab Assignment 16.
Make sure you include a header listing the authors of the file.