Quicksort - The Quicksort Algorithm
(Page 3 of 5 )
We will consider the non-decreasing (ascending) case. These are the steps in the Quicksort algorithm:
Put an element which is supposed to be around the middle at its rightful position. In our list above, R should be in position 5 and not position 3. To do this step you have to exchange positions; since Y is in position 5 you have to exchange the positions of R and Y.
You now call the element (R), in its rightful position around the middle of the list, the Pivot. The pivot (element) has now been sorted and will not be touched again. You now consider the list to be composed of three sub-lists. The elements to the left of the pivot, form one sub-list; the pivot (only one element) forms another sub-list; the elements to the right of the pivot form the third sub-list.
If there is any element to the left of the pivot that is higher (alphabetically) than the pivot, there is bound to be another element to the right of the pivot that is smaller (we assume here that there are at least three elements in the main list – actually the algorithm works right down to a main list of one element). There may be more than one pair of such elements. Exchange all of them so that all the elements to the left of the pivot will be smaller than all the elements to the right of the pivot.
Repeat the above two steps for the left sub-list and the right sub-list.
When you do the above (third) step, you will have new sub-lists. Continue to repeat the first two steps until the whole list is completely arranged (sorted) in non-decreasing order.
Next: Quicksort by Observation >>
More JavaScript Articles
More By Chrysanthus Forcha
/ 3 
