quicksort

From: Andy (andyfaeglasgow_at_yahoo.co.uk)
Date: 02/06/04


Date: 6 Feb 2004 03:06:57 -0800

Hi all,

I'm trying to understand quicksort better comparing comparison counts
between quicksort and selection sort etc. I understand that for
n=100, there should be about 200 comparisons when sorting a random
array, but when the array is sorted, there should be about 5000.
However, this is not coming out in the results. In the code below,
comps[2] counts comparisons for a random array and counts[3] counts
those for an identical array that has already been sorted. I suspect
they must be in the wrong place because when I run the program,
comps[2] is always about 200 and comps[3] is always a little under
500. I would be grateful for any help.

(p.s. I know that you can just use the library methods in java but I'm
trying to learn programming).

public void quickSort(int [] randomNums, int left, int right)
   {
      comps[2]++;
      comps[3]++;
      if(left<right)
      {
         int p=partition(randomNums, left, right);
         quickSort(randomNums, left, p-1);
         quickSort(randomNums, p+1, right);
      }
   }
   
   private int partition(int [] randomNums, int left, int right)
   {
      comps[2]++;
      comps[3]++;
      int pivot=randomNums[left];
      int p=left;
      for(int i=left+1; i<=right; i++)
      {
         if(randomNums[i]<pivot)
         {
            randomNums[p]=randomNums[i];
            randomNums[i]=randomNums[p+1];
            randomNums[p+1]=pivot;
            p++;
         }
      }
      return p;
   }