$ mkdir ~/cs170/labs/lab14 $ cd ~/cs170/labs/lab14
Your next assignment has been posted, and it is a personal favorite of mine. What I have learned over the past few years is that students have no idea what a complex number is, nor do they understand what to do with them. So today, before we start sorting, we are going to learn about complex numbers.
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.
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 lab14.tgz lab14/
To submit your activity, go to inquire.roanoke.edu. You should
see an available assignment called Lab Assignment 14.
Make sure you include a header listing the authors of the file.