Problem in Quick Sort

+2 pratt 15 · January 15, 2015
I was trying to implement quick sort based on the algorithm of partition but there is some mistake in my code. It will be very helpful if someone rectify it,



class Funk {

public void qs(int[] a,int l,int h){   //l->lower index  h->higher index
if(l<h){
int f=partition(a);     //get partition position
qs(a,l,f-1);
qs(a,f+1,h);
}

}
public int partition(int[] a) {
int i = -1, j = 0;
int x = (a.length) - 1;     //to fix last element at right position
while (j != x - 1) {
if (a[x] < a[j]) {    //last element less than a[j]
j++;
} else if (a[x] >= a[j])  //last element greater than a[j]
                              {  
i++;          //increment i & then swap
swap(i, j, a);
j++;           //increment j
}
}
swap(i + 1, x, a);          //finally put last element at right place
return (i+1);              //return correct position

}

public void swap(int x, int y, int[] a) {
int temp = a[y];
a[y] = a[x];
a[x] = temp;
}

public void display(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(" "+ a);
}

}
}

public class MyClass {
public static void main(String args[]) {
int[] b = { 6, 14, 1, 2, 46, 17, 32, 15 };
Funk obj = new Funk();
obj.qs(b,0,b.length-1);
obj.display(b);

}

}

 

Post a Reply

Replies

Oldest  Newest  Rating
0 c student · January 16, 2015
problems might arise because of in/decrement errors.

can you post your output and/or be more specific about your mistake?
0 Kuroodo Ditory · January 16, 2015
We need:

Error/exception logs (found in the console) if any.

If no exceptions, then what kind of output were you expecting to get? What kind of output did you get instead?


Edit: I implemented the code myself.

You are getting a StackOverFlowError exception.

The error occurs here:

if (l < h) {
int f = partition(a); // get partition position
qs(a, l, f - 1);
qs(a, f + 1, h);
}

Basically the qs method keeps getting called over and over and over and over. Then every new call, it is called it keeps getting called over and over and over.

If a method calls another method , which calls another method, etc, you will have a stack overflow exception after a large amount of I guess you can say levels.

It pretty much looks like this http://cdn.studiodaily.com/wp-content/uploads/2014/03/630_divergent1.jpg



Other than that, here are some fixes to your code though.

in the display method:

The original code did not print out each element in the array. All you did was print out what I think is the reference value of the array.
You had a loop that printed out "[I@15db9742" 8 times. What you wanted to do was print out each element from the array. To get elements from any array you use the [].

So let's say we wanted to get the second element inside of the a array, we would do:

System.out.prin(a[1]); // 0 is 1st, 1 is 2nd, etc.


So I fixed your loop/display method (for some reason, the brackets [ ] didn't work, so I had to use words instead :P ).

public void display(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a bracket i endbracket + " ");
}

}

 Since the length of a is 8 because it has 8 elements, the loop would run 8 times (0-7). So if the current value of i is 5, then a would be the same as a[5].
Now the output is: 6 14 1 2 46 17 32 15 


Edit 2:
Java has a built in sorting method that uses the same algorithm I think.

Do this at the beginning of your code to see it work
int[] b = { 6, 14, 1, 2, 46, 17, 32, 15 };
Arrays.sort(b);
display(b);


This is the source code of the Arrays class http://www.docjar.com/html/api/java/util/Arrays.java.html

It calls another class that actually does the sorting. That class is called DualPivotQuicksort. Here is the source code of that class. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/DualPivotQuicksort.java


Now to put an end to your problem, look into this: http://stackoverflow.com/questions/3444382/quicksort-partition-algorithm
0 c student · January 16, 2015
your quick sort seems to be swapping elements with itself...  are you in/decrementing and swapping properly with the correct element?
  • 1

Java / Android Development

106,922 followers
About

Very popular language used to create desktop applications, website applets, and Android apps.

Links
Moderators
Bucky Roberts Administrator