QuickSort help
// Exercise 16.10: QuickSort.java
// Class that creates an integer array filled with random
// values and can sort that array using the quicksort algorithm
// Your Name Here
publicclass QuickSort
{
privateint[] data;// array of values
// create array of given size and fill with random integers
public QuickSort(int[] newData )
{
data = newData;// create array
}// end QuickSort constructor
// call recursive method quicksortHelper
publicvoid sort()
{
quicksortHelper( 0, data.length - 1 );
}// end method sort
// recursive method to sort array using quicksort
privatevoid quicksortHelper(int left,int right )
{
int middle = (left + right) / 2;
swap(data[middle], right);
for(int i = 0; i < data.length - 1; i++){
if(data[i] > right){
swap(data[middle], data[i]);
data[left] = left + 1;
}
swap(data[right], data[left]);
}
}// end method quicksortHelper
// helper method to swap values in two elements
privatevoid swap(int first,int second )
{
int temporary = data[ first ];// store first in temporary
data[ first ] = data[ second ];// replace first with second
data[ second ] = temporary;// put temporary in second
}// end method swap
// method to output values in array
public String toString ()
{
StringBuffer temporary =new StringBuffer();
// iterate through array
for (int element : data )
temporary.append( element +" " );
temporary.append("\n" );// add endline character
return temporary.toString();
}// end method toString
publicstaticvoid main (String[] args){
}
}// end class QuickSort
ok, this is the quicksort stuff that i wrote but I'm starting to doubt this will work so can anyone please please please tell me how i can check to see if it's running correctly using main method (i dont know what to write in there >_<) or tell me this works... if not, how to fix it... thx a lot
public class QuickSort {
private static long comparisons = 0;
private static long exchanges= 0;
/***********************************************************************
* Quicksort code from Sedgewick 7.1, 7.2.
***********************************************************************/
public static void quicksort(double[] a) {
shuffle(a);// to guard against worst-case
quicksort(a, 0, a.length - 1);
}
public static void quicksort(double[] a, int left, int right) {
if (right <= left) return;
int i = partition(a, left, right);
quicksort(a, left, i-1);
quicksort(a, i+1, right);
}
private static int partition(double[] a, int left, int right) {
int i = left - 1;
int j = right;
while (true) {
while (less(a[++i], a[right]))// find item on left to swap
;// a[right] acts as sentinel
while (less(a[right], a[--j]))// find item on right to swap
if (j == left) break;// don't go out-of-bounds
if (i >= j) break;// check if pointers cross
exch(a, i, j); // swap two elements into place
}
exch(a, i, right); // swap with partition element
return i;
}
// is x < y ?
private static boolean less(double x, double y) {
comparisons++;
return (x < y);
}
// exchange a[i] and a[j]
private static void exch(double[] a, int i, int j) {
exchanges++;
double swap = a[i];
a[i] = a[j];
a[j] = swap;
}
// shuffle the array a
private static void shuffle(double[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int r = i + (int) (Math.random() * (N-i));// between i and N-1
exch(a, i, r);
}
}
// test client
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
// generate N random real numbers between 0 and 1
long start = System.currentTimeMillis();
double[] a = new double[N];
for (int i = 0; i < N; i++)
a[i] = Math.random();
long stop = System.currentTimeMillis();
double elapsed = (stop - start) / 1000.0;
System.out.println("Generating input: " + elapsed + " seconds");
// sort them
start = System.currentTimeMillis();
quicksort(a);
stop = System.currentTimeMillis();
elapsed = (stop - start) / 1000.0;
System.out.println("Quicksort:" + elapsed + " seconds");
// print statistics
System.out.println("Comparisons: " + comparisons);
System.out.println("Exchanges:" + exchanges);
}
}
is there a way to do this without changing any of the methods and keeping what i had... cause they were given and we were suppose to build it from there... as in all the methods
I can tell you that your quicksortHelper method is not even close to sorting and is indeed changing the values in the array.
For testing you could use:
public static void main(String[] args) {
int[] unsorted = new int[] {5,4,6,2,7,9,3};
QuickSort qs = new QuickSort(unsorted);
qs.sort();
System.out.println(qs); // should output 2 3 4 5 6 7 9
}
dwga at 2007-7-12 15:06:44 >
heh... can anyone help me to fix my quicksort helper... i followed the steps I was suppose to (well obviously not)... >.<
well, i guess here's a better version o fit, except it still doesn't work... private void quicksortHelper( int left, int right )
{
int pivot;
pivot = data[left];
while(left < right){
while((data[right] >= pivot) && (left < right))
right--;
if(left != right){
data[left] = data[right];
left++;
}
while((data[left] <= pivot) && (left < right))
left++;
if(left != right){
data[right] = data[left];
right--;
}
}
} // end method quicksortHelper
it returned: 3 4 2 2 7 9 6
i don't know what I did wrong anymore... >_<
http://en.wikipedia.org/wiki/Quicksort
Have you seen the algorithm for quicksort? Quicksort is a recursive method, do you know what a recursive method is? Your method is not recursive. Here is pseudocode version for quicksort.
private List quickSort(list) {
pick a pivot
loop over list {
if value is less than pivot
add to lessThanPivot
else if value is greater than pivot
add to greaterThanPivot
else
add to equalPivot
}
return merge quickSort(lessThanPivot) equalPivot quickSort(greaterThanPivot)
}
private void quicksortHelper(int left, int right)
{
int left1, right1, temp;
int pivot;
left1 = left;
right1 = right + 1;
pivot = data[left];
do{
do
left++;
while (left < data.length && data[left1].compareTo(pivot) < 0);
do
right--;
while (data[right1].compareTo(pivot) > 0);
if(left < right)
swap(left1, right1);
} while(left <= right);
temp = data[left];
data[left] = data[right1];
data[right1] = temp;
if (left < right1)
quicksortHelper(left, right1);
if (left1 < right)
quicksortHelper(left1, right);
}
now it's telling me that "int cannot be deferenced" and stuck again -.-
You are trying to call a method on an int, which is a primitive and does not have methods. data[left1].compareTo(pivot)
uhhh so i have to write out the entire compareTo() stuffs?*i'm not really usre how to do it... but ok*
Once again - Have you bothered to read the quicksort algorithm? because your code looks nothing like it.As for your immediate problem why are you bothering with compareTo to compare numbers when you already know how to use > or < or <= etc?
well i read it but I don't really understand it like where it says, loop it all. In terms of loop what under what conditions and such...
> http://en.wikipedia.org/wiki/Quicksort
>
> Have you seen the algorithm for quicksort? Quicksort
> is a recursive method, do you know what a recursive
> method is? Your method is not recursive. Here is
> pseudocode version for quicksort.
Uhhh flounder. I hate to point this out but you shouldn't have an equals bucket for quicksort. At least for the kind being taught in school. I also have used the equals bucket for my own quicksort but someone once told me that it's "harder to prove" or something. I don't really know what that means but I think the upshot is that for computer science purposes only two buckets should be used.
@OP Do what flounder's code says except you should put equals ones into either the less than or more than. Whichever you want... just as long as you are consistent.
> well i read it but I don't really understand it like
> where it says, loop it all. In terms of loop what
> under what conditions and such...
?
This is not overly promising.
Suggestion: Why don't you write a quicksort using a List of some sort first. That wil get you grounded in the algorithm, then you can get into the excitement of doing it place.
hmm ok, well i'll try to understand all this stuff again... thx for all the help
> Uhhh flounder. I hate to point this out but you
> shouldn't have an equals bucket for quicksort. At
> least for the kind being taught in school. I also
> have used the equals bucket for my own quicksort but
> someone once told me that it's "harder to prove" or
> something. I don't really know what that means but I
> think the upshot is that for computer science
> purposes only two buckets should be used.
Yeah, when I implemented a quicksort I only used lessthan and greatthan pivot but the pseudocode I wrote was derived from the algorithm on the wiki page. Thinking about it though, it does make sense. I mean if you have a list of numbers all the same value then there is no point in sorting them further.
