QuickSort in Action

(Page 1 of 6 )

This is the second part of a two-part article that explains how to use Quicksort. It is a method of sorting a list of elements and putting them in the correct order. Please make sure you have read and understood the first article before you read this one.

Picking up where we left off in the previous article, we have to obtain a pivot and then put all elements that are less than the pivot on the left side and all elements that are greater than the pivot on the right side.

We start by comparing the left-most and right-most elements. If the left-most element is greater than the right-most element, then swap them. This gives the following:

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

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

For simplicity, we shall be calling the left-most element the left element, and the right-most element the right element.

The present left element will become the pivot for the list. We arrive here after the swapping phase. We then increase the value of i continuously until we come across an element that is greater than the left element. We reduce the value of j continuously until we come across an element that is less than the same left element; remember that the left element will become the pivot. The i^th and the j^th element so found are in the wrong positions, so we swap them. This gives rise to the following:

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

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

We continue to increase the value of i and decrease the value of j to find another pair of elements that are in the wrong positions, and then swap. This leads to:

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

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

We have to continue increasing the value of i, decreasing the value of j and swapping until the index variables reach the right (end) and left (start) elements. However, as soon as the index variables cross, it means we have finished swapping -- all the elements that should be on the left, and all the elements that should be on the right, are in their appropriate positions (or at least on their correct sides).

Next: Swapping Elements >>
 

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!