Sign in to follow this  

[java] Quicksorting issue

This topic is 3294 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:
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[i] < pivotValue)
                        i++;
		while (pivotValue < a[j])
                        j--;

		if (i <= j){
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j--;
		}
	}
	quickSort(a, left, j);
	quickSort(a, i, right);
}

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]

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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[i] <<"\n";
}
return 1;

}

and it seems to work so how about sharing the test case that produces incorrect results?

Share this post


Link to post
Share on other sites
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[i]);
}
}



'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 &lt; from source code

[Edited by - ppgamedev on December 8, 2008 11:41:27 AM]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

This topic is 3294 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this