|DÉÍÍÍÍÍÍÍÍÍÍÍ»ÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ
|Dº |5Brainware |DºÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ
|DÈÍÍÍÍÍÍÍÍÍÍͼÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ

^C^1QuickSort Demo
^Cby
^CJohn Sigle

^CThe Quickest Sort

   No single sorting method is universally best.  All algorithms have some 
kinds of data on which they perform poorly.  However, the Quicksort algorithm, 
created by C. A. R. Hoare, is considered to be the fastest general sorting 
method. 

   Quicksort is a good example of a recursive program.  A recursive program is 
one which calls itself.  If this seems circular, it is - in part.  In English 
we are taught not to define an entity in terms of itself.  Well, in 
programming it is acceptable (even elegant) to define a program partly in 
terms of itself, provided that there is an escape hatch, a part of the 
definition which is not recursive, which will eventually be applied to produce 
a specific result.

   A problem is a good candidate for a recursive solution if it can be broken 
down into subproblems and if some of these subproblems are of the exact same 
nature as the original problem but smaller in size.  This is the strategy of 
the Quicksort algorithm.

   Quicksort begins by selecting a value from the list to be sorted. This value 
will be called the "pivot" value.  It is not critical how this value is 
selected.  One approach is to select the item in the middle of the list.  The 
list will then be rearranged so that those values which are less than or equal 
to the pivot value are moved to one end of the list (the left end) and those 
values which are greater than or equal to the pivot are moved to the other 
end.  This is called partitioning the list into 2 partitions.  (Actually, 
depending on the data values involved, there may be a third partition in the 
middle consisting of value(s) equal to the pivot.  If this third partition 
develops, its value(s) are in their final resting place and do not move during 
the rest of the sorting process.)

   At this point we have made some progress.  All we need to do is sort each of 
the 2 partitions developed above.  What method shall we use????  You guessed 
it!!!!   Quicksort!!!!   Recursion!!!!

   What is the escape hatch?  It occurs when we get down to a partition so 
small that it contains only one value.  We simply quit, since a partition of 
one value is "sorted".

   The partitioning method is interesting and is what gives Quicksort its 
superior performance.  A scan is made from the beginning of the list forward, 
looking for a value that belongs in the other end, that is, a value which is 
greater than or equal to the pivot value.  When this is located a scan is made 
from the end of the list backward, looking for a value that belongs in the 
other end, that is, a value which is less than or equal to the pivot value.  
When this is located a swap is made of the two values located.  The scans are 
resumed from these locations and the process continues until the scans meet 
and cross.

   The secret of Quicksort's efficiency is that values can make large jumps 
toward their final positions as a result of very few comparisons.

   This disk contains sample Turbo Pascal code for a version of Quicksort 
(QUICK1.PAS) as well as an animated demonstration (QUICK1-D.CHN) of this 
program. This demo shows the PASCAL program as it executes as well as the data 
values being manipulated.  The demo can be run at varying speeds. It vividly 
shows the nature of this sorting method and relates it directly to a PASCAL 
program for performing the sort. 

   Try the demo QUICK1-D to see how it works.  You can control the speed by 
pressing a digit 0-9 (not the numeric keypad) at any time.  Nine is the 
highest speed while 1 is the lowest.  A speed of 0 puts you in single-step 
mode. In that mode you press the spacebar twice to execute a line of the 
program.  You can scroll the program display forward or backward at any time 
by means of the up or down arrows.  At the conclusion of the demo the total 
number of comparisons, swaps and assignments performed is reported.

   The advantage of Quicksort over other methods is not very dramatic with only 
20 values to sort.  If 1000 values are to be sorted the advantage is amazing.  
The explanation for this is that there is some fixed overhead work associated 
with each partitioning.  It takes large partitions for Quicksort to really get 
cranked up and show its stuff.

   This leads to one of the many variations of Quicksort which have been 
suggested.  It involves using a different (simpler) method, such as Insertion 
sort, to sort partitions which are smaller than some fixed size, say 10.

Happy sorting!!!!

   To run this program outside the BIG BLUE DISK menu, type ^1PASRUN QUICK1-D^0.