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