The quick sort was devised by C. A. R. Hoare. It works as follows: It
places a number in its correct position in the list and then
recursively uses the same scheme for the group of numbers below the
correctly positioned number and then for the group above it. On the
average, the quick sort is the most efficient sort. Let's examine the
list 16 4 11 9 71 29 8 13 stored in the arrray `X` to see how
it works.

Call the first number (here, 16) `first`; the subscript 1,
`beginning`; and the subscript of the last element
`ending`. The procedure will use the heading:

PROCEDURE Quick(Beginning, Ending:integer; VAR X : Sorted);

We'll place `first` in a location such that the numbers to the
right of it are greater than it, and the numbers to the left of it
will be less than it. In other words, it will be in its correct
position in the list. Do this by going forward through the list until
you find a number (here, 71) greater than or equal to
`first`. Then go from the back of the list to the left until we
find a number (here, 13) that's less than or equal to
`first`. If the subscript (I) of the first number (71)
is less than the subscript (J) of the second number (13) as is the
case here, exchange the two numbers. The list is now
16 4 11 9 13 29 8 71.

Continue by preceding to the right from the position that 13 is in
until you find the next number (here, 29) greater than or equal to
`first`. Then go to the left from 71 until you find the next
number (here, 8) less than or equal to `first`. If the
subscript (I) of the first number (29) is less than that (J)
of the second number (8) as is the case here, exchange the two
numbers. The list is now
16 4 11 9 13 8 29 71.

At this point, the value of I is 6 and that of J is 7. `X[I]`
is 8 and `X[J]` is 29. Since `X[I] <= first`, increment
I to 7, and since `X[J] > first`, decrement J to 6. Now *I >
J*. This is called *cross over*. When cross over occurs,
exchange `X[J]` with `first`. In our case, exchange 16
with 8. The list is now
8 4 11 9 13 16 29 71
`first`, 16, is now in its proper position in the list.

We then have to apply this technique to the group of numbers to the
right of `first` and to the group to its left (this is the
recursion part), i., e., call `Quick(J + 1, Ending, X)` and
`Quick(Beginning, J - 1, X)`. These two groups are shown in
square brackets [8 4 11 9 13] 16 [29 71]. For the [29, 71] sublist,
cross over occurs immediately, and J becomes 1. So the switch is the
identity operation and nothing is changed. `Quick(J + 1, Ending,
X)` becomes `Quick(2, 2, X)` and `Quick(Beginning, J -
1, X)` becomes `Quick(1, 1, X)`. In both cases
`Quick` is sorting only one element. In order to have the
procedure return immediately, place `if I < J then` at the
beginning of the procedure.

At this point, the procedure `Quick` should be clear.

PROCEDURE Quick(Beginning, Ending:integer; VAR X : Sorted); VAR I, J, first:integer; BEGIN {I increases from the right of the array; J decreases from the left} I:= Beginning; J:= Ending; if I < J then begin {returns when thers's only 1 element in sub list} first:= X[I]; WHILE I < J DO BEGIN {stop at cross over} WHILE (X[I] <= first) AND (I < Ending) DO I:= I + 1; WHILE X[J] > first DO J:= J - 1; IF I < J THEN {at cross over, don't switch X[I] & X[J]} Switch(I, J); END {WHILE}; Switch(Beginning, J);{switch first and X[J] at cross over} Quick(Beginning, J - 1, X); Quick(J + 1, Ending, X) end

At the end of the program, the list will be sorted. Note that you
don't have to choose as `first` the first number in a group, it
can be for instance the middle number.

**ALGORITHMS WHOSE EFFICIENCY DEPENDS ON LOG(N)**

Let's first review what the term logarithm means. Logarithm is another
name for exponent. For instance in 8=2^{3}, the
logarithm of 8 to the base 2 is 3. This is written as
log_{2}8. Whenever an algorithm is structured
so that it continuosly splits the number of posibilities by one-half,
the number of comparisons will depend on the log to the base 2. We'll
start by analyzing the quick sort

**QUICK SORT**

Remember in the quick sort that
` first` is the element that will eventually be placed
in its proper position in the array. Let's examine the case in which
the value of

8 | ---------- | | 4 4 | | ------ ------ | | | | 2 2 2 2

Since the number of comparisons equals the number of items
in a group, the number of comparisons would be 8 + (4 + 4) + (2 + 2 +
2 + 2) or 24; but this is 8 * 3 or 8 * `log _{2}8`. The
number of levels (here, 3) in the diagram indicates the number of
times

In general, if the number of elements in the original array is
`n = 2 ^{m}`, then the number of levels in the diagram
is

n log_{2}(n)

It's interesting to note that the worst case occurs when the array is already sorted. To estimate the number of comparisons, let's first draw the same type of diagram we drew for in the previous estimate.

8 | ------- | | 1 7 | ----- | | 1 6 | ----- | | 1 5 etc.

Since the procedure is not called for one-element sublistd, the
number of comparisons is 8 + 7 + 6 + 5 + 4 + 3 + 2. This is our old
friend, the sum of the integers. So the worst case is
*n ^{2}*