# 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;
}