CMPT
225 Lab - Quicksort
You are to use the Quicksort algorithm to sort
arrays of integers and to test the efficiency of the algorithm with two different
types of organization.
QuickSort
Algorithm
The implementations of the Quicksort,
partition and swap algorithms are provided in the file linked at the end of
this document. There is also a calling function (qs) that call the recursive
quicksort function. You should carefully review these functions before moving
on to the next section. The Quicksort function returns the number of
comparisons it made so that you can compare the number of comparisons on arrays
with different organizations.
Testing
Write a main function to sort arrays of
different organizations and size and print the number of comparisons returned
by the sort. I would like you to sort the following arrays.
Random arrays of size 10, 100, 1000, 10,000,
100000 and 1000000
Reverse arrays of size 10, 100 and 1000 (anything
much bigger than this will result in a stack overflow)
You can use two for loops to run your tests,
thought the increment statement will not be adding one to the loop control
variable (for a change).
Arrays can be generated by the getRandomArray
and getReversedArray included in the .cpp file.
Program
You can find the program file
here: cmpt225sort_lab.cpp.
John Edgar (johnwill@sfu.ca)