Your task will be to write, document, and debug several variants of the quicksort algorithm, and do timing tests comparing the algorithms. You will also do the timing tests on the c-library routing qsort, and (for short arrays) on insertion sort.

Start by writing an insertion sort routine:

    void insert_sort(int *A, unsigned int length)

Get your insertion sort and timing framework done before you start work on quicksort.

Implement a sort using the library qsort() routine. All you need for this is a comparison function. Time the qsort routine sorting small arrays (n=0 to 50, again) and large ones (n=1024, 2048, ..., 2^20)

Write your quicksort routines to do in-place sorting in ascending order. The quicksort routine should look something like

	
void quicksort(int *A, unsigned int length)
{
    int num_in_first;
    switch(length)
    {    case 0: return;
    	 case 1: return;
    }
    num_in_first = partition(A,length);
    quicksort(A, num_in_first);
    quicksort(A+num_in_first, length-num_in_first); 
}

You will have to write your own partition function. There are many different variants on partition that you can find in various textbooks. For now, you may pick any of them, as long as your pivot choice is sensible (say the middle element of the array, not the first element).

Time your quicksort routine for small arrays (sort the same random arrays that you sorted with insertion sort---it is probably easiest to make two copies of the large random array and sort one with insertion sort, one with quicksort). Plot the insertion sort and quicksort data on the same graph. Play around with gnuplot until you find a good way to compare the two visually. For example, I found it useful to make the x-axis be the length of the array to sort, and the y-axis be the ratio of the microseconds/call.

Try improving your quicksort by adding the following code to the base case:

    if (length < INSERT_FASTER_IF_SHORTER) 
    {   insert_sort(A,length);
        return;
    }

To turn in

Bonus points

• You can also try to make improvements in your quicksort by adding more cases to the switch statement, instead of using insert_sort. For example, you could treat length 2 as a special case:

  	
      switch(length)
      {    case 0: return;
      	 case 1: return;
  	 case 2: if (A[0]>A[1]) swap(A[0],A[1]);
  	 	return;
      }
  

  (Note: the "swap" is pseudo-code---you need to figure out the right way to do it.)
• Figure out the length-3 special case and try out quicksort with that special case (and no insertion sort).
• Try different variants of the partition algorithm.
• Try different pivot selection schemes with a single partition method.
• Do a timing experiment and plot for quicksort on already sorted data. (This is easily done by sorting the random array once before you hand it to the timing routine.)

SoE home

Questions about page content should be directed to