java programming help : quicksort?

Question

suppose we are attempting to sort the following array into increasing order:

{10,19,2,17,3,11,7}

if we use QUICKSORT, then what does the array contain after the 1st "partitioning" stage (assume that fence is chosen to be the 1st element of the array ie 10.)

ans is: {3,7,2,10,17,11,19}

WHY?

can anybody explain what is quicksort?

Answer 1

I'm not 100% sure I agree with that answer ({3,7,2...}), but regardless...

Quicksort is a sorting algorithm (collect them all!) which breaks the problem of sorting a set of values into one of sorting two small sets of values, a strategy known as "divide and conquer". It's also an "in place" sorting algorithm, meaning you can actually move values around in the set itself instead of having to work on copies.

In a quicksort, you pick a "partition" (I guess your teacher is calling it a "fence"). This can be any value in the set, and if your set is always nice & random like this you can just grab the first one instead of wasting time trying to find the median value or anything like that.

Ok, so in your example, your partition (fence) value is 10. So, loop through the set and break it into two lists: everything less than 10, and everything greater than or equal to 10. Now, you apply the same algorithm to the two lists. Pick a pivot value in the "less than" list and split it into everything smaller than that value and everything greater than it. Do the same to the "greater than" list. Keep narrowing down the sizes of these lists until you get to a list with a size of 1. When you exit all the recursive calls, you'll find that the values in the set were sorted.

It's called a "quicksort" because it's incredibly fast compared to other sorting algorithms. If written with threading in mind, the sorting tasks can even be split up among multiple CPUs if your system has more than one to make everything even faster.

Oh yeah, it's also ok to use a different sort algorithm after a while rather than recursively quicksorting these smaller & smaller lists. So in that case you'd partition maybe once or twice...maybe three or four times...and then do a shell sort or something on the really small sets rather than break them down further.

It might help to watch a quicksort in action. Check out the cool Java applet at this site (about halfway down):

http://www.wanginator.de/studium/applets/quicksort_en.html

You'll have to put the values in one by one, but once you're done keep clicking "next step" to see how the partitioning and sorting works.

Oh yeah, I don't see why {3,7,2} should be the order of the "less than" set after just the first step. Going left to right would give {2,3,7} and going right to left would give {7,3,2}. What weird method of traversing a set gives that kind of order?