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

}

**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 ]