Conference of Applied Mathematics
University of Central Oklahoma
Spring 1991
Variations on Put First
Bill McDaniel
Department of Computer Science
Central State University
Edmond, Ok
This paper presents several variations of the partition procedure used in
the sorting algorithm known as Quicksort.
The basic algorithm was originally published as two routines: a partition
part and a recursive part. This paper follows Hoare's style by also dividing
the algorithm into two parts
C.A.R. Hoare's version of the QuickSort, shown below , and originally
published in 1961 [Hoar 61], was in a non-structured form and reflects the
accepted programming style of the time.
procedure quicksort (a,m,n);
value m,n; array a; integer m,n;
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
procedure partition (a,m,n,i,j);
value m,n;
array a;
integer m,n,i,j;
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 goto down;
i := n;
down: for j := j step -1 until m do
if a[j] < x then goto change;
j := m;
change: if i < j then begin exchange (a[i], a[j]); i := i + 1; j := j - 1; goto 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 exchange
A structured version, with slight variations written in Pascal, of Hoare's
basic algorithm is shown below. Hoare's original loops, which use GoTo
statements, have been replaced with WHILE statements.
program seequick;
{ Quick Sort using Hoare's version of put first }
const
n = 2000;
opt = 1;
procedure Put_First(first,last : integer; var pos : integer);
var
p,l,r : integer;
begin
l := first;
r := last;
p := l;
swap(l,random(last-first+1)+first);
while l < r do
begin
while (l < r) and (ar[p] <= ar[r]) do dec(r);
swap(ar[p],ar[r]);
p := r;
while (l < r) and (ar[p] >= ar[l]) do inc(l);
swap(ar[p],ar[l]);
p := l;
end;
pos := p;
end;
procedure quick_sort(first,last : integer);
var
pos : integer;
begin
Put_First(first,last,pos);
if pos-first > opt then quick_sort(first,pos-1);
if last-pos > opt then quick_sort(pos+1,last)
end;
begin
generate_the_numbers;
quick_sort(1,n);
end.
The area of interest, and the subject of this paper, is the partitioning
routine named 'Put_First'.
For the original version (of Put_FIrst), Hoare chose an item (at random),
and used that item as a pivot for the rest of the items in the list. The
partitioning algorithm (which is referred to as Put_First, in this paper)
would place all the numbers less than the pivot to the left of the pivot and
all of the numbers greater than the pivot to the right of the pivot. This
method of placement of the pivot would accomplish two goals: 1) the pivot
would then be in it's final position so that it would never have to be moved
again and 2) the numbers would be divided into two disjoint groups. Partition
was designed as an 'in place' sort. Except for a few temporary variables,
no additional storage was needed for the sort.
In order to 'see' exactly how the partition algorithm works, the following
assertion notation will be used.
ar[first..l-1] <= pivot
ar[l..r] = ??
ar[r+1..Last] >= pivot
This means that all of the numbers from ar[first] to ar[l-1] are less than
or equal to the pivot, all of the numbers from ar[r+1] to ar[last] are greater
than or equal to the pivot. The status of the numbers from ar[l] to
ar[r] has not yet been determined. Since l is being incremented and r is
decremented, eventually the group l..r will consist of just one item (the
pivot) and the partitioning part will be finished.
The following version of the QuickSort is a variant of a version published by
Sedgewick [Sedg 78]. This algorithm minimizes the number of swaps by
scanning in from the left then scanning in from the right THEN swapping
the two numbers found to be out of position. This is the fastest version
known. The assertion, at the slug(þ), for this version is:
ar[low..i] <= pivot
ar[i+1..j-1] = ??
ar[j..high] >= pivot
procedure Put_First(low, high : integer; var pos : integer);
var
i, j : integer;
pivot : integer;
begin
i := low;
j := high;
pivot := ar[low];
repeat
while (i < j) and (ar[i] <= pivot) do i := i + 1;
while (i < j) and (ar[j] >= pivot) do j := j - 1;
if i < j then swap_items(i,j)
þ
until i >= j;
swap_items(i,low);
pos := i
end;
RollDown version of Put First
The following version of PutFirst uses a FOR loop to roll the largest values
to the bottom of the list. This algorithm was first suggested by Nico
Lomuto (of Alsys, Inc.) and referenced in Communications of the ACM [Bent 84].
The assertion, at the slug, is as follows:
pivot = ar[first]
ar[first+1..LastLow] < pivot
ar[LastLow+1..i] >= pivot
ar[i+1..last] = ??
procedure Put_First(first,last : integer; var pos : integer);
var
pivot : integer;
LastLow : integer;
begin
swap(ar[first],ar[random(last-first+1)+first]);
pivot := ar[first];
LastLow := first;
for i := first + 1 to last do
if ar[i].ch < pivot then
begin
LastLow := lastLow + 1;
swap(ar[LastLow],ar[i])
þ
end;
swap(ar[LastLow],ar[first]);
pos := LastLow;
end;
Move to Bottom version of Put First
This version compares the i'th number with the i'th + 1 number. The i'th + 1
number is either less then the i'th number or it is greater than the i'th
number. If it is less than then swap the two numbers. (This will ensure
that all of the numbers above the i'th number are less than then i'th
number.) If the i'th+1 number is greater than the i'th number then swap
the i'th+1 number with the last'th number, then decrement last. This will
ensure that all of the numbers greater than the i'th number are sent to the
bottom of the list, and all of the numbers greater than the i'th
number are below last-1.
The assertions (at the slug) are:
ar[left..i-1] <= pivot
ar[i] is the pivot
ar[i+1..last] = ??
ar[last+1..right] > pivot
procedure Put_First (left,right : integer; var pos : integer);
var
i, last : integer;
ch2 : keyboard_keys;
begin
swap(ar[left],ar[random(right-left+1)+left]);
i := left;
last := right;
while i < last do
begin
if ar[i] > ar[i+1] then
begin
swap(ar[i],ar[i+1]);
i := i + 1
end
else
begin
swap(ar[i+1],ar[last]);
last := last - 1
end
þ
end;
pos := last;
end;
Rotate version of Put First
This version compares the pivot with the bottom'th value. If the pivot
is less than the bottom'th value, then decrement bottom, else perform
Rotate_Left(bottom,pivot+1,pivot). The assertions, at the slug, are:
ar[left..pivot-1] <= pivot
ar[pivot] is the pivot
ar[pivot+1..bottom] = ??
ar[bottom+1..right] > pivot
procedure Put_First (left,right : integer; var pos : integer);
var
pivot, bottom : integer;
value : char;
begin
pivot := left;
bottom := right;
while pivot < bottom do
begin
if ar[pivot] > ar[bottom] then
begin
Rotate_Left(bottom,pivot+1,pivot);
pivot := pivot + 1;
end
else
bottom := bottom - 1
þ
end;
pos := pivot
end;
The code for Rotate_Left appears below.
procedure Rotate_Left(a,b,c : integer);
var
t : integer;
begin
t := ar[a];
ar[a] := ar[b];
ar[b] := ar[c];
ar[c] := t
end;
Put First using Doubly Linked Lists
One can apply a QuickSort to a group of items stored in a Doubly Linked List
without having to make drastic changes to the algorithm. In this case the
list is circular. Given the following declarations ...
type
node_ptr = ^ node;
node =
record
ll : node_ptr;
info : integer;
rl : node_ptr
end;
var
ch : char;
i : integer;
p,head,tail : node_ptr;
... the insertion routine into a Circular Doubly Linked List is given
below. Each new item is placed onto the tail end of the list.
procedure insert (var head,tail : node_ptr; p : node_ptr);
{ insert a node onto the tail of the list }
begin
if head = nil then { empty list }
begin
head := p;
tail := p;
p^.rl := p;
p^.ll := p
end
else
begin { non-empty list, insert onto tail }
tail^.rl := p;
p^.ll := tail;
tail := p;
tail^.rl := head
end
end;
The Put_First routine for a Doubly Linked List is quite similar to the
original structured version given earlier in this paper. Rather than
increment (or decrement) an array index, one would move a pointer to the
contents of the the right_link (or left_link, respectively).
procedure Put_First(head,tail : node_ptr; var pos : node_ptr);
var
p,cl,cr : node_ptr;
begin
cl := head;
cr := tail;
p := head;
while cl <> cr do
begin
while (cl <> cr) and (p^.info <= cr^.info) do cr := cr^.ll;
swap(p^.info,cr^.info);
p := cr;
while (cl <> cr) and (p^.info >= cl^.info) do cl := cl^.rl;
swap(p^.info,cl^.info);
p := cl;
end;
pos := cl;
end;
The QuickSort procedure passes pointers instead of array indeces.
procedure quick_sort(head,tail : node_ptr);
var
pos : node_ptr;
begin
Put_First(head,tail,pos);
if pos <> head then quick_sort (head,pos^.ll);
if pos <> tail then quick_sort (pos^.rl,tail);
end;
For completeness, the main program has also been included.
begin
head := nil;
tail := nil;
{ generate n random numbers, put into nodes, insert the nodes into the dll }
for i := 1 to n do
begin
new(p);
with p^ do info := trunc(random*30000);
insert (head,tail,p);
end;
{ traverse once, printing the numbers }
p := head;
repeat
write(p^.info:8);
p := p^.rl
until p = head;
writeln;
{ sort the numbers }
quick_sort(head,tail);
{ traverse, printing the numbers in order }
p := head;
repeat
write(p^.info:8);
p := p^.rl
until p = head;
writeln;
end.
QuickSort in C
Since the C language is gaining predominance in the computing arena, we
have included the C code for the classic version of the Quicksort.
A complete C program using the structured equivalent is shown below.
/* Version 1 of Hoare's Quicksort in C */
#include
#include
#define TRUE 1
#define FALSE 0
#define n 2500
#define opt 1
/* declarations */
void swap(int a, int b), bubble (int num), quick (int start, int end);
int Put_First (int left, int right);
int ar[n];
void main()
{ int i;
clrscr();
for (i=0; i< n; i++) ar[i] = rand()%2000;
/*printf("The numbers before the sort\n");
for (i=0; i< n; i++) printf("%5d ",ar[i]); */
printf("%c",7);
quick(0,n-1);
bubble(n-1);
printf("%c",7);
printf("\n The numbers after the sort\n");
for (i=0; i< n; i++) printf("%5d ",ar[i]);
getch();
}
void quick (int start, int end)
{
int pos;
pos = Put_First(start,end);
if (pos-start > opt) quick(start,pos-1);
if (end - pos > opt) quick(pos+1, end );
}
int Put_First (int l, int r)
{ int p;
p = l;
while (l < r)
{
while ( l < r && ar[p] <= ar[r] ) r--;
if (l < r) swap(p,r);
p = r;
while ( l < r && ar[l] <= ar[p] ) l++;
if (l < r) swap(l,p);
p = l;
}
return p;
}
void swap(int a, int b)
{
int c;
c = ar[a];
ar[a] = ar[b];
ar[b] = c;
}
void bubble (int num)
{
int swaps, i;
swaps = TRUE;
while (swaps)
{
swaps = FALSE;
for (i=0; i < num; i++)
if (ar[i] > ar[i+1])
{
swap(i,i+1);
swaps = TRUE;
}
}
}
Moissant (Mois 91) pointed out that the position variable (p) of the pivot
(within the routine Put_First) can be removed without any loss in logical
integrity. Rather than swap ar[p] with ar[l] (and moving p) and swapping
ar[p] with ar[r] (and moving p), one can just swap ar[l] with ar[r] (and
forget p). The resulting algorithm is shown below.
/* Version 2 */
int Put_First (int l, int r)
{
while (l < r)
{
while ( l < r && ar[l] <= ar[r] ) r--; /* 1 */
if (l < r) swap(l,r); /* 2 */
while ( l < r && ar[l] <= ar[r] ) l++; /* 3 */
if (l < r) swap(l,r); /* 4 */
}
return l;
}
The previous change made the next step obvious. With the introduction of a
flip-flop boolean variable, statements marked 1 and 2 can be combined with
statements 3 and 4, giving the following function.
/* Version 3 */
int Put_First (int l, int r)
{
int f=TRUE;
while (l < r)
{
while ( l < r && ar[l] <= ar[r] ) f ? r-- : l++;
if (l < r) swap(l,r);
f = !f;
}
return l;
}
Agreeably, the logic (of the above function) is subtle. The variable 'f'
is a logical flip-flop. Every other cycle through the outer loop the boolean
variable 'f' is TRUE, and the alternate times FALSE. When 'f' is TRUE the
statements read ...
while ( l < r && ar[l] <= ar[r] ) r--
if (l < r) swap(l,r);
f = FALSE;
... and when f is FALSE the statements read ...
while ( l < r && ar[l] <= ar[r] ) l++;
if (l < r) swap(l,r);
f = TRUE;
.... Taken together the statements are equivalent to the code shown in
Version 2.
In the programming language C, the comma operator allows one to combine
statements (beadlike) into 1 expression. Using this operator one can remove
a statement from the body of a loop and place the statement WITH the while
condition. Also, in C, the comma operator causes the expressions (or
statements) to be evaluated left to right. Since 'l < r' is the LAST
expression evaluated, the result of THAT compare will be used to control the
loop. Also note that since the statement 'f=!f' appears in the condition
part, it will be performed BEFORE the body of the loop, therefore f is
initially set to FALSE (rather than TRUE as in the previous example).
/* Version 4 */
int Put_First (int l, int r)
{
int f= FALSE;
while (f=!f,l < r)
{
while ( l < r && ar[l] <= ar[r] ) f ? r-- : l++;
if (l < r) swap(l,r);
}
return l;
}
The exit conditions for the innermost loop are:
l = r
or
ar[l] > ar[r]
and in either case a swap would be permitted. If the latter condition is
TRUE the swap is required, and if the former condition is TRUE then the swap
is unnecessary but innocuous; therefore, the prefixing 'if' can be removed
with some loss of speed. (When l = r, some numbers will be swapped with
themselves).
/* Version 5 */
int Put_First (int l, int r)
{
int f= FALSE;
while (f=!f,l < r)
{
while ( l < r && ar[l] <= ar[r] ) f ? r-- : l++;
swap(l,r);
}
return l;
}
The outermost while loop can be replaced with a FOR loop, with the
initialization of f moving to the initialization part of the FOR statement
and the invocation of SWAP moving into the increment part of the FOR
statement.
/* Version 6 */
int Put_First (int l, int r)
{ int f;
for (f=FALSE ; f=!f,l < r ; swap(l,r))
while ( l < r && ar[l] <= ar[r] ) f?r--:l++;
return l;
}
Version 6 of Put_First is typical C code, succinct but effective.
This paper has demonstrated that the partitioning algorithm of the Quicksort
has many variations. Having the different versions available is advantageous,
especially to a student of Data Structures. With different algorithms
available one can see a pattern emerge and achieve a more fundamental
understanding of available partitioning methods.
References
[Bent 84] Bentley, Jon L. Programming Pearls. Communications of the ACM.
Vol 27, No 4. April 1984. pp. 287-291.
[Hoar 61] Hoare, C. A. R. (July, 1961). Algorithm 63, Partition;
Algorithm 64, Quicksort; Communications of the ACM, Vol 4, p. 321.
[Kern 76] Kernighan & Plauger. Software Tools. Addison-Wesley. 1976.
[Kern 81] Kernighan & Plauger. Software Tools in Pascal. Addison-Wesley.
1981.
[Mois 91] Moissant, Paul. Conversation. March 1991.
[Sedg 78] Sedgewick. Implementing Quicksort Programs. Communications of the
ACM. Vol 21, No 10. Oct 1978. pp. 847-857.