QuickSort in Action - Swapping Elements

(Page 2 of 6 )

When the index variables cross, they will be identifying elements, that is, the i^th variable will be identifying the next element that is greater that the left element, or it will be identifying the last element if no element was found greater than the left element. Meanwhile, the j^th variable will be identifying the next element that is less than the left element or it will be identifying the first (left) element if no element was less than the left element. The situation when our variables cross, is as follows:

P	W	E	I	T	Y	U	R	O	Q
			j	i

I	O	E	P	T	Y	U	R	W	Q
			j	i

Look at the first of the two tables above carefully. Note that if we swap the present pair and continue to increment i, decrement j, and swap, we shall be reversing our process. We have to stop here.

Actually we can use either the left or the right element as the pivot. Well, we shall use the left element as I said above. It can be shown that the position for the index variable, j, at the moment, is the final (sorted) position for the left element, P. So we swap the left element and the element at position j. Doing this with our array gives us the pivot, P, at its final position. The situation is as follows:

[I O E] (P³) [T Y U R W Q] --------result 1

We have the pivot at position 3, the left sub-list and the right sub-list. The index variable k that we mention above takes its first value of 3. We have to repeat the same process for the left sub-list and right sub-list. Let us start with the left sub-list.

Next: Tackling a Sub-list >>
 

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!