Thread: Help me, java quicksort!

Hello, I got a problem that I just can't solve.. The program is supposed to sort the random int-array with a "quickSort". But I dont get it to work, I do get a list of 20 int's and they're almost sorted. But it's almost always a few int's on the wrong place. What have I done wrong? Would really appreciate help! :)
Sorry if it looks messy.

import java.util.Random;
 
public class quickSorterARN {
 
	public static void main (String[] args) {
		Random rand = new Random();
		int a[] = new int[20];
		for (int i = 0; i < a.length; ++i) {
			a[i] = rand.nextInt(100);
		}
		quickSorter(a, 0, a.length - 1);
		for (int i = 0; i < a.length; ++i) {
			System.out.println(a[i]);
		}
	}
 
	static void quickSorter(int[] data, int first, int last) {
		int top = first;
		int bot = last;
 
		int midValue = data[(top+bot)/2];
		while (top < bot) {
			for (; data[top] < midValue; ++top)
				;
			for (; data[bot] > midValue; --bot)
				;
 
			if (top <= bot) {
				int temp = data[top];
				data[top] = data[bot];
				data[bot] = temp;
				++top;
				--bot;
			}
		}
		if (top < last && bot > first) {
			quickSorter(data, first, bot);
			quickSorter(data, top, last);
 
		}
	}
}

Originally Posted by Joeyeyey

... problem...

I don't understand this at all:

 
        if (top < last && bot > first) {
            quickSorter(data, first, bot);
            quickSorter(data, top, last);
        }

I'm not too nuts about your choice of names of variables, but it seems to me that if top is less than last, you need to call the function recursively to sort that part, regardless of the other part.

Similarly, if first is less than bot, you need to sort that part, regardless of the other part, don't you?

Are you working from pseudo-code? What is your reference?


Cheers!

Z

Okay, will try that. Thanks!

--- Update ---

Originally Posted by Zaphod_b

I don't understand this at all:

 
        if (top < last && bot > first) {
            quickSorter(data, first, bot);
            quickSorter(data, top, last);
        }

I'm not too nuts about your choice of names of variables, but it seems to me that if top is less than last, you need to call the function recursively to sort that part, regardless of the other part.

Similarly, if first is less than bot, you need to sort that part, regardless of the other part, don't you?

Are you working from pseudo-code? What is your reference?


Cheers!

Z

Well, I have tried this if this is what you mean:

if (top < last)
        quickSorter(data, first, bot);
if (bot > first)
	quickSorter(data, top, last);

But it didn't work either :/

Im just learning Java on my own at home, this is just a practicequestion in the book.

--- Update ---

Hmm, well. You were right, I changed it from "top < last && bot > first" to "top < last || bot > first".
But in the book they used "&&", in exactly the same situation. But can you please explain to me as if I were 5 years old. Why this didnt work with "&&"?
Thanks alot for the help both of you!

Originally Posted by Norm

As Zaphod_b asked above, do you have an algorithm for what you are trying to do?
Add the algorithm as comments in the code and try to write code to follow it.

It's just a simple question in the book, Im supposed to implement quickSort instead of bubbleSort. (I learned earlier in the book how to implement bubbleSort.) There is no algorithm.

Originally Posted by Joeyeyey

Well, I have tried this...

if (top < last)
        quickSorter(data, first, bot);
if (bot > first)
	quickSorter(data, top, last);

But it didn't work
...

But that didn't do what I hinted at.

I hate to repeat myself, but

Originally Posted by Zaphod_b (emphasis added)

if top is less than last, you need to call the function recursively to sort that part.

if first is less than bot, you need to sort that part.

Bottom line: I wouldn't have made my suggestion unless I had tested it.

Originally Posted by Joeyeyey

But in the book they used "&&", in exactly the same situation.

I asked what reference you were using. I meant, what reference for quicksort. What is the name of the book or other source of your idea for quicksort? Are you saying that the book had an example of quicksort that is exactly like your code and that it used && in code or pseudocode for quicksort the way you did? (I'm not sure what you mean by "exactly the same situation.")

Originally Posted by Joeyeyey

I changed it from "top < last && bot > first" to "top < last || bot > first"

Well, that's not entirely unrelated to what I had in mind, but it doesn't demonstrate (much) understanding of the problem. I am glad you asked for more information.

Originally Posted by Joeyeyey

You were right

I'm not always "right" but I do test my suggestions before posting.

Originally Posted by Joeyeyey

...explain...Why this didnt work with "&&"?

Well, let's see...

The problem is that I can't explain why 2*3 is not equal to 5 but 2+3 is equal to 5 in the limited space and bandwidth of this forum and with my space-and-bandwidth-limited brain. I have to say that, in general, it's not always easy to explain why doing the wrong thing gives the wrong answer. Maybe you can explain to me why you think && would work here.

Anyhow, here is the short form of an implementation rationale...

The way I see it (in vague generalities) is that the whole point of quicksort is, at each stage, it splits the array into two partitions with certain properties. Certain conditions can cause recursive calls to create smaller and smaller sub-partitions until everything is sorted.


If the first partition needed further sorting but the second didn't, using the && operator between the conditions would fail and no further sorting would be done. Furthermore (as if a furthermore were really needed), if the second part required sorting but the first part didn't, using the && operator would fail, and no more sorting would be done.

The fact that your original program sometimes "leaves a few ints in the wrong place" indicates that the result depends on the order of the values in the randomly populated array. Sometimes, it "just happens" that it gets sorted, where with a different ordering it gets "almost" sorted. That means that sometimes it quits too soon rather than doing further recursion.

On the other hand, using the || operator would result in the both parts being sorted if either one (or both) needed to be sorted. (So it would "work.")

Code following my suggestion a little more closely might look something like the following, which would sort a sub-partition only if it needed to be sorted. (Naive implementations of quicksort tend to do a lot of extra work on partitions that are already sorted.)

IF top is less than last THEN
    Call quickSorter on the partition that has top and last
END IF
 
IF bot is greater than first THEN
    Call quickSorter on the partition that has first and bot
END IF

Cheers!

Z