Jump to content
  • Advertisement
Sign in to follow this  
TheRealDeal

[java] Quicksorting issue

This topic is 3602 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 < 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);
}

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
Advertisement
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 <<"\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);
}
}



'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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!