static void quickSort(int[] a, int left, int right){
if (left >= right)
return;
int i = left;
int j = right;
int pivotValue = a[(left+right)/2];
while (i < j){
while (a < pivotValue)
i++;
while (pivotValue < a[j])
j--;
if (i <= j){
int temp = a;
a = a[j];
a[j] = temp;
i++;
j--;
}
}
quickSort(a, left, j);
quickSort(a, i, right);
}
[java] Quicksorting issue
Author
Alrighty well, I've been attempting to get this annoyingly simply quicksort to work in a program. I won't deny that this is a program for school, but I'm asking that absolutely no one give me the code that will make it work. A) I know its against the rules here, and B) I won't learn a single thing if I just copy/paste the code.
I have the method for quicksorting done correctly I'm pretty sure, this is what I have for the method:
The issue is that when I call it, I pass in the minimum and maximum numbers (left and right) and it runs fine. Only some of the time do two numbers swap, but when they do its done correctly. The issue is that it only runs once, so in the beginning of the method, if left is greater/equal to right, it exits the method and goes back to main and moves on.
I've tried various loops when I call the method so that if it returns early, it will go back into the method with the next two left and right values (left incremented, right decremented), but I must be doing something wrong because it never sorts.
I'm just looking for to be pointed in the right direction to get this little devil to work, but I do ask that no one types out the code and just says "Do that", I would rather hear an idea and try to implement it myself. Is a loop the right idea when I initially call the method so if it does get sent back right away, it will change values and go back in?
Any help is greatly appreciated!
JDDeal
[Edited by - TheRealDeal on December 7, 2008 4:11:21 PM]
Author
Thanks mate, yeah when I copied the code over originally all of the < and > signs turned into "alt;" so I changed em manually, accidentally put the wrong one there, but in the actual code in Eclipse it is correct (as above now).
I just ran it against
int main()
{
int list [] = {2,4,6,8,9,10,1,3,5};
quickSort(list,0,9);
for(int i = 0; i < 10; ++i)
{
std::cout << list <<"\n";
}
return 1;
}
and it seems to work so how about sharing the test case that produces incorrect results?
int main()
{
int list [] = {2,4,6,8,9,10,1,3,5};
quickSort(list,0,9);
for(int i = 0; i < 10; ++i)
{
std::cout << list <<"\n";
}
return 1;
}
and it seems to work so how about sharing the test case that produces incorrect results?
Quote:The issue is that when I call it, I pass in the minimum and maximum numbers (left and right)
What do you mean with that?
I am wondering if you really understand what you are doing.
public static void main(String[] args) { int[] a = {56, 74, 45, 3, 552}; quickSort(a, 0, 4); for(int i = 0; i < a.length ; i++) { System.out.println("a[" + i + "] = " + a); }}'left' and 'right' parameters are INDEXES, not values.
Remember that array indexes are zero-based in Java, from zero till array.length - 1
Edit: removed ugly < from source code
[Edited by - ppgamedev on December 8, 2008 11:41:27 AM]
Author
PPgamedev you steal the win on this one. I unfortunately didn't have time to check the site before I went to school (where I found the solution) and yes, I was under the false impression that those left and right values were the actual values, not the indexes >.< Sure made one heck of a difference in solving that problem.
Thank you so much for your help anyway mate!
JDDeal
Thank you so much for your help anyway mate!
JDDeal
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
