$ mkdir ~/cs170/labs/lab17 $ cd ~/cs170/labs/lab17
Recursion is probably still a little bit hazy in your minds. That's a little understandable, because it is quite a weird concept. But I think part of the issue is that you are still a little cloudy on how function calls really work, as far as the python interpreter is concerned. Let's cover functions, and how that relates to recursion today as we go over merge sort.
Quick sort earned its name by being an incredibly quick sorting algorithm. The idea is roughly the same as merge sort: Split the list into two halves and recursively call the same procedure. The difference is when the actual work of sorting is taking place.
In merge sort, the work is being done AFTER the list has been split up into its smaller pieces. In quick sort, the work is being done BEFORE the list is split up. The process of "sorting" is actually creating the two "halves" of the list. By finding the partition element's correct location in the list, you just have to worry about sorting the list before the partition element, and the list after the partition element.
In the file sorting.py file, create two
functions: quick_sort_copy(a_list)
and partition(a_list). Both of these
functions take a list of comparable
elements. quick_sort_copy(a_list)
should return a sorted copy of a_list, while partition should return
three values: The partition element, a list of all of the items that
are less than or equal to the partition element, and a list of all
of the items that are greater than the partition element.
partition uses the last element of the list as the
partition element. It iterates through the rest of the list,
appending items into either a left list, or a right list depending
on how it compares to the partition element.
We will arbitrarily say that all of the
elements equal to the partition element will go into the half of the
list less than the partition element.
quick_sort_copy is very simple: It calls partition, then
recursively calls quick_sort_copy on the left and right halves
of the list.
>>> my_list = [5, 4, 3, 2, 1] >>> partition_return = partition(my_list) >>> print(partition_return) (1, [], [5, 4, 3, 2] >>> quick_sort_return = quick_sort(my_list) >>> print(quick_sort_return) [1, 2, 3, 4, 5]
Your base case for quick sort is when the length of the list is one. A list of length one is already in sorted order.
Partition needs to create two lists, which I will call left and right. as you go through the elements of the incoming list, simply append to the correct list.
The above version of quick sort is pretty fast, but it uses a lot of extra memory. On Monday I made you write the in place version of Merge sort first. I think that caused too much confusion. However, I think it's still important for you to write the in place version of quick sort as well.
In the file sorting.py file, create two
functions: quick_sort(a_list, start, end)
and partition(a_list, start, end). Both of these
functions take a list of comparable elements and two integers in the
range [0, len(a_list)]. Neither of these functions should return a
list, they should simply modify the order of the elements in place.
Partition, however, should return the index of where it
placed the partition element.
partition uses the last element of the list as
the partition element. It iterates through the rest of the list,
performing a swap operation when it finds an item that is not in the
correct half of the list. We will
arbitrarily say that all of the elements equal to the partition
element will go into the half of the list less than the partition element.
quick_sort is very simple: It calls partition, then
recursively calls quick_sort on the left and right halves
of the list.
How does Quick Sort compare to Merge Sort?
>>> my_list = [5, 4, 3, 2, 1] >>> partition_return = partition(my_list, 0, len(my_list)) 0 >>> print(my_list) [1, 4, 3, 2, 5] >>> quick_sort_return = quick_sort(my_list, 0, len(my_list)) >>> print(my_list) [1, 2, 3, 4, 5] >>> print(quick_sort_return) None
Your base case for quick sort is when the length of the list is one. A list of length one is already in sorted order.
Notice that the end index for my examples above are non-inclusive: You specify the index that is one past the end of the sub list. I do this because it allows for easy specification of the range of your for loop for partition. However, the book doesn't do it this way. You may choose which one makes more sense for you.
Remember, the pseudo code in the text book is based off a 1's based index scheme for lists. You need to modify it slightly to work with a 0's based index.
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 lab17.tgz lab17/
To submit your activity, go to inquire.roanoke.edu. You should
see an available assignment called Lab Assignment 17.
Make sure you include a header listing the authors of the file.