QuickSort in Action - Tackling a Sub-list

(Page 3 of 6 )

We compare the left and right elements of the sub-list and then swap if necessary. The situation is as follows:

I	O	E
i		j

E	O	I
i		j

The left element, E, will be the pivot for the sub-list. We now increment i and decrement j under the same conditions as we did above. We end up with the following situation:

E	O	I
j	i

O is the first element for the variable index i that is higher than E. There is no element for the index variable j that is lower than E, so j ends at the position of E, the first position. We now exchange the left element, E, with the element of the position for j, which is still E. So E is exchanged with itself. The new value for the index variable k is now 0, which is the final position for E in the main list. The sub-list can now be written as:

(E⁰) [O I]

There is only one sub-list now, the right sub-list; there is no left sub-list. Whenever the computer (sorting program) arrives at the situation where there is no left sub-list, it starts sorting the immediate right sub-list, which in our case is [O I].

There are only two elements in the sub-list. We compare the left and right elements of the sub-list and then swap if necessary. The situation is as follows:

O	I
i	j

I	O
i	j

The left element, I, is the pivot for the sub-list. We now increment i and decrement j under the same conditions as we did above. We end up with the following:

I	O
j	i

O is the first element for the variable index i that is higher than I. There is no element for the index variable j that is lower than I, so j ends at the position of I. We now exchange the left element, I, with the element of the position for j, which is still I. So I is exchanged with itself. The new value for the index variable k is now 1, the position for I in the main list. The sub-list can now be written as:

(I¹) [O]

Again, there is only one sub-list, the right sub-list; there is no left sub-list. Remember, whenever the computer (sorting program) arrives at the situation where there is no left sub-list, it starts sorting the immediate right sub-list, which in our case is [O]. There is only one element in this sub-list.

Next: And Then There was One >>
 

More JavaScript Articles
More By Chrysanthus Forcha

Comments On: QuickSort in Action

· Thanks for stopping by to read my article. If you have any comments, questions, or...   >>> Post your comment now!