quicksort
From: Andy (andyfaeglasgow_at_yahoo.co.uk)
Date: 02/06/04
 Next message: Abraham Khalil: "AccessControlException  ActiveX Bridge"
 Previous message: Victor Zhang: "Java program hang,how to do problem determination"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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, p1);
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;
}
 Next message: Abraham Khalil: "AccessControlException  ActiveX Bridge"
 Previous message: Victor Zhang: "Java program hang,how to do problem determination"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
