## Lecture 14 - Quick Sort

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

$mkdir ~/cs170/labs/lab14$ cd ~/cs170/labs/lab14


### Complex Numbers

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.

Lab Activity 1
Quick 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.

#### Details

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.

#### Example

>>> 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]


#### Hint

• 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 are joining your recursive calls, you need to append the partition element to the end of the left list. Then join the two lists together.

#### Submission

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.