$ mkdir ~/cs170/labs/lab23 $ cd ~/cs170/labs/lab23
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 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:
quickSort
is very simple: It calls partition, then
recursively calls quickSort
on the left and right halves
of the list.
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]