< Back

Lecture 23 - Quick Sort


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

$ mkdir ~/cs170/labs/lab23 
$ cd ~/cs170/labs/lab23 

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 sorting.cc file, create two functions: void quickSort(int * a_list, int start, int end) and int partition(int * a_list, int start, int end). Both of these functions take a list of integers, and the size of the array. The quickSort function should not return any value. Partition should return the position the partition element was swapped into.

partition uses the first element of the list as the partition element. We will follow the partition procedure described in the textbook:

  1. Create two "references" left and right. left should be initialized to start + 1, right should be initialized to end - 1
  2. While the element at the left position is less than the partition element, increment left.
  3. While the element at the right position is greater than than the partition element, decrement right.
  4. If right is greater than (or equal to!) left, swap the values in those positions and repeat. Otherwise, we are done.
  5. After the above process, right is a reference to the last element in the "left" half. It is also the position in the array that the partition element should be in. So swap the partition element and the element in the right position.
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.

quickSort is very simple: It calls partition, then recursively calls quickSort on the left and right halves of the list.

Example

  int myList[] = {5, 4, 3, 2, 1};
  partition_return = partition(myList, 0, 5);
  cout << (partition_return) << endl;          //4
  printList(myList);                           //[1, 4, 3, 2, 5]
  quickSort(myList, 0, 5);
  printList(myList);                           //[1, 2, 3, 4, 5]

In-Class Notes