QuickSort in Action - And Then There was One
(Page 4 of 6 )
The algorithm (implementation) has to continue. The left element now is O; the right element is still O. The left element is compared with the right element; and since they are the same, no swapping takes place. Since there is only one element, i should not be incremented and j should not also be decrementing. This results in the following:
We now exchange the left element, O, with the element of the position for j, which is still O. So O is exchanged with itself. The new value for the index variable k is now 2, the final position for O in the main list. The sub-list can now be written as:
(O2)
Now, note that there is no sub-list at all; no left and no right sub-list. My computer implementation is such that the computer will always move to sort the sub-list on the left of the found pivot. If there is no sub-list on the left, it goes to sort the immediate right sub-list. But if there is no immediate right sub-list, which is our current situation, it sorts the right sub-list that it did not sort before the present level of sorting. So it has to sort the following sub-list:
[T Y U R W Q]
This happens to be the first right sub-list we had. The algorithm (implementation) is repeated for this sub-list: the left and right elements are compared and exchanged if necessary. The pivot is obtained. Two sub-lists are developed; the left sub-list is sorted first.
Note that the series of steps keep repeating themselves. In the process of sorting, the left sub-list is sorted first before the right sub-list. This process continues until the sorting is complete.
Note that the algorithm (implementation) keeps calling itself (repeating) as you go down the sorting process. This is called recursion. That is, the sorting function has to keep calling itself.
Next: Code for Quicksort >>
More JavaScript Articles
More By Chrysanthus Forcha
/ 3 
