Quicksort - Quicksort by Observation

(Page 4 of 5 )

Let us sort the list above by observation, before we see how to program it on the computer. 

The list is:

Q W E R T Y U I O P

Let us make R the pivot. We can equally make Q, whose rightful spot is position 4, the pivot. We simple have to choose something for the central position. So by choosing R and exchanging the positions of R and Y, we have:

Q W E Y T R⁵ U I O P

When any element obtains its rightful position, we shall indicate that with a superscript as in the case of R above.

We now have to see that all the elements to the left of R are less than R, and that all the elements to the right of R are greater than R, by exchanging pairs. The following pairs can be exchanged: W and P, and Y and O. Note that you can still exchange W and O, and Y and P. Exchanging W for P and Y for O, we have

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

We will indicate the sub-lists with square brackets, and the pivot with normal brackets. 

If you chose O as the pivot for the left sub-list and repeated the first and second steps in the algorithm, you would have something like this:

[I E] (O²) [P Q] ------------result IIa

If we do a similar thing to the right sub-list above we shall have something like:

[T] (U⁷) [Y W]

Now when a non-pivot element appears alone in a sub-list, we know that the element has arrived at its rightful position. So we have

[T⁶] (U⁷) [Y W] ------------result IIb

The state at which we have sorted the whole list by observation, so far, is

[I E] (O²) [P Q] (R⁵) [T⁶] (U⁷) [Y W] --------result III

Note that some elements have taken their final (rightful) positions. Any element that is a pivot, obtains its rightful position. Any element that is alone in a sub-list also obtains its rightful position.

You simply have to continue by repeating the first and second steps of the algorithm on the sub-lists. Let us consider the first sub-list, [I E] of result III.

There are only 2 elements here. Let us choose E as the pivot. Putting E in its rightful position by exchanging it with “I”, we have:

(E⁰) [I]

Now, the position number of E in the main list is zero; remember that array counting begins from zero. There is only one sub-list, the right sub-list. It has just one element, so the element has arrived at its proper position, which is position 1. The former sub-list is:

(E⁰) [I¹] --------------result IVa

You can carry out a similar analysis for the other sub-lists and come out with the complete sorted list of

(E⁰) [I¹] (P²) [Q³] (R⁵) [T⁶] (U⁷) [W⁸] (Y⁹) -----result V

Your brackets may not match my brackets, but the order should be the same.

Next: Computer Implementation >>
 

More JavaScript Articles
More By Chrysanthus Forcha

Comments On: Quicksort

· It is good to understand the operation of the Quicksort function. I did this in...   >>> Post your comment now!