The quick sort is one of the fastest all-purpose sort. There are other sorts that are faster given specific situations, like an almost sorted array, or an array with lots of repeated elements. But for general sorting of typical arrays, the quick sort is hard to beat. Also hard to beat is the following YouTube instructional video; just ignore the C++ code for now; in fact you should be ignoring all code for now and focusing on the algorithms themselves.
If the quicksort algorithm could be summarized in a few sentences it would be this: randomly pick an element, which you'll call the "pivot", and compare each of the other elements in the array with it to see if they are less than or greater than your chosen "pivot". Put all of the ones that are less than the pivot to the left of it, and all that are greater than it to the right of it. By doing so, the pivot will be in the correct position. Now take each of the sides, and do the same thing. Repeat this, breaking the array down into increasingly smaller sub-arrays until the full array is sorted.
- As you are doing the algorithm in your head, or with a bunch of cards on the table, here's the way you approach it, step-by-step:
- From one side, and then the other:
- Look at each card and ask if it's in the right relative position; i.e. when dealing with the cards to the left of the pivot if it's less than the pivot, and then when dealing with the cards to the right of the pivot if it's greater than the pivot. If in the right place keep moving.
- But the other thing is that in your moving of the selector toward the pivot, you may get right up to the pivot, or indeed start with the pivot; at the pivot you must stop also.
- And so then you swap (when you've stopped, both from the left and from the right.).
- Make sure at the start of each partition step you start with the cards you left off with.
- Remember that you are finished each partition step when both selectors are pointing to the pivot.
So in summary, you will: Move in from sides until you find something that is not on the correct side of the pivot.
So say to yourself pointing to the cards etc.:
Besides the "quickness" of the quicksort, there is one other important reason to look at the Quicksort in particular: it is a recursive method. A recursive method is any method which within itself calls another/other instance(s) of itself. You'll commonly see it defined as a method which calls itself, but this is neither technically true nor possible. What a recursive method does is calls another/other instances(s) of itself. At this point it's good to recognize that methods take up memory just like attributes do. So it is entirely possible for multiple copies of the same method to be in memory at the same time - they will be in memory as long as they are not finished. And since when a particular method calls another instance of "itself", it is not complete, then those different instances of the method do indeed exist at the same time.
More on this later as we get into recursion a bit deeper, just do keep in mind as you get used to the way that the quicksort works, that it is calling other instances of itself right after it puts each particular pivot into the correct position, up to the point where all elements are put in the correct position.
You can always recognize a recursive method by noting calls to other instances of itself within itself, as with this incomplete example of the quicksort version we will use:
public void quickSort(int start, int finish, int[] arr)......
......
......
......
if(.......){
quickSort(start, right, arr);
}if(......){
quickSort(left, finish, arr);
} }
Original flash file: _Flash/QuickSort-JSR.swf