My QuickSort is only semi-working... if you can help T.I.A., if not that's ok too

[oLLie]

import java.lang.*;

/** the class which does the sorting */
public class Sort {
/** temporary variables used in sorting procedues */
long startTime, endTime;
static int pivotValue, left, right, firstRun, secondRun, thirdRun, avgRun;
int qSortCutOff = 0;
int tempValue = 1000000;
boolean useMedOfThree = false;
static Comparable pivot, temp;
//double temp;
Double[] tempArray;
Double[] miniArray, smallArray, mediumArray, largeArray, superArray;
public static final int KID_SIZED = 50;
public static final int SMALL = 100;
public static final int MEDIUM = 500;
public static final int LARGE = 10000;
public static final int SUPER_SIZED = 500000;

/** the method main calls to begin the different sorts */
void timedSort() {
quickSort( miniArray, 0, miniArray.length - 1);
for (int j = 0; j < miniArray.length; j++)
System.out.println( miniArray[j]);

}

/** the simplest implementation of the quickSort algorithm */
static void quickSort( Comparable[] A, int leftBound, int rightBound ) {
if ( leftBound < rightBound ) {
int left = leftBound;
int right = rightBound - 1;
if ( left == right ) {
if (A

.compareTo(A

) > 0 ){
temp = A

;
A

= A

;
A

= temp;
}
return;
}
pivotValue = (int)Math.ceil( ( rightBound - leftBound ) * Math.random()) + left;
//System.out.println(pivotValue);
temp = A[pivotValue];
//System.out.println(rightBound);
A[pivotValue] = A[rightBound];
A[rightBound] = temp;
pivot = A[rightBound];

while ( left <= right ) {
while( left <= right && (A

.compareTo(pivot) <= 0)) {
left++;
//System.out.println("Incrementing left: " + left );
}
while( right >= left && (A

.compareTo(pivot) >= 0))
right--;
if (left < right) {
temp = A

;
A

= A

;
A

= temp;
}
}
temp = A

;
A

= A[rightBound];
A[rightBound] = temp;

quickSort(A, leftBound, left - 1);
quickSort(A, left + 1, rightBound);
}
}

/** the implementation of the insertionSort algorithm */
static void insertionSort( Comparable A[], int leftBound, int rightBound ) {

}

/** defines the point at which insertionSort will be used to sort */
void setInsertionSortThreshhold( int threshhold ) {
qSortCutOff = threshhold;
}

/** defines whether to use the median of three method of choosing a pivot or not */
void setMedianOfThree( boolean flag ) {
useMedOfThree = flag;
}

/** creates randomized arrays of various sizes */
void makeArrays() {
miniArray = new Double[KID_SIZED];
for( int j = 0; j < miniArray.length; j++ )
miniArray[j] = new Double( Math.ceil( tempValue * Math.random() ) );
smallArray = new Double[SMALL];
for( int j = 0; j < smallArray.length; j++ )
smallArray[j] = new Double( Math.ceil( tempValue * Math.random() ) );
mediumArray = new Double[MEDIUM];
for( int j = 0; j < mediumArray.length; j++ )
mediumArray[j] = new Double( Math.ceil( tempValue * Math.random() ) );
largeArray = new Double[LARGE];
for( int j = 0; j < largeArray.length; j++ )
largeArray[j] = new Double( Math.ceil( tempValue * Math.random() ) );
superArray = new Double[SUPER_SIZED];
for( int j = 0; j < superArray.length; j++ )
superArray[j] = new Double( Math.ceil( tempValue * Math.random() ) );
}

/** launches the sorting program */
public static void main( String[] args ) {
Sort sortQuick = new Sort();
sortQuick.makeArrays();
sortQuick.timedSort();
//System.out.println(sortQuick.miniArray[KID_SIZED-1].toString());
}
}​

 

[oLLie]

That's the straight source... I know it's really ugly... and I dunno why some of it is italicized...
anyway if anyone can tell me why it sorts it semi-correctly, thanks!

 

[stndn]

not really a help to quick sort, but it's italized because you have [ i ] in your code
for example, this line:
System.out.println( miniArray [ i ]);

that is the code for italizing the test under coldfusion
there's not much you can do about it, except if you want to take the time to change variable i to j or sth ...

anyways, maybe you can give your sample input/output to tell us how it is "semi sorted"?

-952-

 

[bo_bear]

I'm sorry that I really don't want to read your code, it's just too messy (the way it's formatted on here), but I have one suggestion for you. I think QuickSort is best to be done using Recursion. The code will probably be less than 20 lines if you use recursion.

 

[oLLie]

*Edit* Wow, I'm a platinum member!
bo_bear, it is recursive .
stndn, thanks for your offer to help, here's some sample output I bolded what is wrong:
18144.0
2525.0
19832.0
23723.0
31836.0
37197.0
55828.0
108703.0
86806.0
113136.0
121408.0
173255.0
212820.0
236912.0
263784.0
292061.0
312817.0
356975.0
370531.0
419695.0
452675.0
471477.0
506731.0
506994.0
512677.0
548793.0
556387.0
626364.0
636106.0
649700.0
651445.0
658356.0
661848.0
672104.0
692986.0
707400.0
713905.0
711893.0
725956.0
752813.0
762011.0
781821.0
783440.0
831544.0
846299.0
849919.0
885672.0
895196.0
917758.0
928507.0

 

[m0ti]

couple of things,

first off I don't understand why you return when leftbound < rightbound (or maybe I'm just having problems reading the non-pretty printed code?) this is in the starting bit of code. I also don't understand why you put right = rightbound - 1, since you want to handle the whole array (when you pass it the paramaters you already took away 1, take a look at the recursive calls, and the original call to the function).

second:

you don't select pivot values to be swapped from the left side... that's a mistake!

replace

while ( left <= right ) {
while( left <= right && (A

.compareTo(pivot) <= 0)) {​

left++;
//System.out.println("Incrementing left: " + left );
}
while( right >= left && (A

.compareTo(pivot) >= 0))
right--;
if (left < right) {
temp = A

;
A

= A

;
A

= temp;
}
}

with

while ( left <= right ) {
while( left <= right && (A

.compareTo(pivot) < 0)) {​

left++;
//System.out.println("Incrementing left: " + left );
}
while( right >= left && (A

.compareTo(pivot) >= 0))
right--;
if (left < right) {
temp = A

;
A

= A

;
A

= temp;
}
}

That's because after you do all the lines of code, you want everything to the right of left to be >= pivot. Then you can recusively work your way down (otherwise, you may be leaving the pivot on both sides of the left).

Hope this helps​

 

[oLLie]

Thanks for the suggestions m0ti,
I tried making the change you suggested but the sorted output is still incorrect.


<< first off I don't understand why you return when leftbound < rightbound (or maybe I'm just having problems reading the non-pretty printed code?) this is in the starting bit of code. I also don't understand why you put right = rightbound - 1 >>


The return you are talking about refers to the if (left == right) statement. Being inside that if statement means I am looking at a subarray of 2 elements, so of course I don't want to continue quicksorting after I swap them. I was under the impression that right = rightBound-1 is correct because each time we choose a pivot, we move it to the far right; therefore, we don't want to have the next call to quickSort include the pivot (at the right) as one of the choices for the "next" pivot. I'm pretty sure I've tried right = rightBound which doesn't help except to give me some array out of Bounds exceptions but I'll try again anyways. Thanks again,

Ollie

*EDIT* Ah, I stand corrected. m0ti, thank you very much for pointing out the problem (right = rightBound-1 should have been right = rightBound as you implied). THANKS! Oddly, I left that <= the way it was... and it works.

 

[m0ti]

You're very welcome.

And actually, I was wrong about the pivot thing. While it does make more sense that everything on the right side of left should be >= pivot, it doesn't matter, since both sides (left and right), get sorted. On the left side pivot will be the largest value, and on the right it will be the smallest, so they will wind up properly sorted.

Glad I could help.



oh, btw, you also don't have to do an import on java.lang.*; it's done automatically.