The Quick Sort


(C) Samuel L. Marateck, 1999

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=23, the logarithm of 8 to the base 2 is 3. This is written as log28. 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 first is such that when it's in its proper position in the array there are approximately as many numbers below as above it. For, the number of elements, n equal to 8, this means that there would be 4 numbers below first and 4 above it (of course then there would be no room for first ; however, we can assume that as n becomes large, the approximation that half of the numbers would be below first and half above it improves). Again, let's assume as the sort procedes, each of the two four-number groups would be split in two two-number groups. Since the minimum number of elements needed for a recursive call is 2, the recursive calls stops when there are two elements in the sublist. We can express this diagramatically

					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 * log28. The number of levels (here, 3) in the diagram indicates the number of times n (here, 8) should be multiplied.

In general, if the number of elements in the original array is n = 2m, then the number of levels in the diagram is m and therefore the number of comparisons is n * m. However, the value of log2(2m) is m. This allows us to write the number of comparisons in terms of one variable, n:

                 n log2(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 n2