Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare in 1962 while working for the small British scientific computer manufacturer Elliott Brothers Ltd. [1, 2]. In his 1980 ACM Turing Award Lecture [3] he describes how a course on Algol 60, taken in early 1961 introduced him to the concept of recursive procedures. The presence of recursion in Algol 60 allowed Hoare to write Quicksort, a concept he had invented while trying to improve upon the Shellsort of Shell [4]. The entire algorithm was described in half a page, and comprised of two algorithms (written in Algol 60): Algorithm 63 which described the partition function, and Algorithm 64 which performed the actual Quicksort function. One of the greatest benefits of Algol 60 was the fact that it, unlike Fortran, allowed recursion.
Algorithm 64
procedure quicksort (A,M,N); value M,N;
array A; integer M,N;
comment Quicksort is a very fast and convenient method of
sorting an array in the random-access store of a computer. The
entire contents of the store may be sorted, since no extra space is
required. The average number of comparisons made is 2(M-N) ln (N-M),
and the average number of exchanges is one sixth this amount.
Suitable refinements of this method will be desirable for its
implementation on any actual computer;
begin integer I,J;
if M < N then begin partition(A,M,N,I,J);
quicksort(A,M,J);
quicksort(A,I,N);
end
end quicksort
Algorithm 63
The original Algol algorithm as published in Communications of the ACM, used a series of goto statements to facilitate the partitioning of the array into those items less than the pivot, and those items greater than the pivot.
procedure partition (A,M,N,I,J); value M,N;
array A; integer M,N,I,J;
comment I and J are output variables, and A is the array (with
subscript bounds M:N) which is operated upon by this procedure.
Partition takes the value X of a random element of the array A,
and rearranges the values of the elements of the array in such a
way that there exist integers I and J with the following properties:
M ≦ J < I ≦ N provided M < N
A[R] ≦ X for M ≦ R ≦ J
A[R] = X for J < R < I
A[R] ≧ X for I ≦ R ≦ N
The procedure uses an integer procedure random(M,N) which
chooses equiprobably a random integer F between M and N, and
also a procedure exchange, which exchanges the values of its two
parameters;
begin real X; integer F;
F := random(M,N); X := A[F];
I := M; J := N;
up: for I := I step 1 until N do
if X < A[I] then go to down;
I := N;
down: for J := J step -1 until M do
if A[J] < X then go to change;
J := M;
change: if I < J then begin exchange(A[I],A[J]);
I := I + 1; J := J - 1;
go to up
end
else if I < F then begin exchange(A[I],A[F]);
I := I + 1;
end
else if F < J then begin exchange(A[F],A[J]);
J := J - 1;
end;
end partition
Further reading
- Hoare, C.A.R., “Algorithm 64 Quicksort”, Communications of the ACM, 4(7), p.321 (1961)
- Hoare, C.A.R., “Algorithm 63 Partition”, Communications of the ACM, 4(7), p.321 (1961)
- Hoare, C.A.R., “The Emperor’s Old Clothes”, Communications of the ACM, 24(2), p.75-83 (1981)
- Shell, D.L., A high-speed sorting procedure”, Communications of the ACM, 2(7), pp.30-32 (1959)
The Craft of Coding 