Quicksort algorithm without data type

Question

Most implementations of quicksort deal with sorting an array of integers. Thus, in a language with fixed data types, such as Pascal, one is required to modify the algorithm in order to sort other arrays, such as arrays of strings.

This is of course an easy task, requiring only minor modifications, besides implementing the order relation on the set of values our array is suppose to take. However it would be desirable to have a one-size-fits-all implementation.

My question is thus:

Question: Is it possible to write a "Quicksort Pascal Unit" which could be used to sort any array, be it of integers, strings or whatever?

The main difficulty one needs to address is that the unit will not have access to the data type of the matrix entries.

Answer 1

Asking a question often sets out a mental process that quickly leads to the answer, and here is one I just found and with which I am very happy.

The main point is to realize that the quicksort algorithm only needs to know the type of the matrix entries in order to:

• compare, and
• swap

them. Thus, if you provide alternative means for these tasks to be performed, quicksort will be happy enough.

In order to do this one declares a "function type" orderRel which takes two integers (thought to be the indices of the matrix entries to be compared) and a "procedure type" copierProc (also taking two indices, and meant to copy one matrix entry into another. See code below).

The quicksort unit is then implemented exclusively in terms of these subroutines, while the calling program is left with the task of implementing the orderRel and copierProc in full view of the data type, which it obviously knows. These two subroutines are then passed to quicksort as parameters.

Here is the full implementation of the quicksort unit and you will find a complete testing program below. Both were tested in "Free Pascal Compiler version 3.0.4+dfsg-18ubuntu2 [2018/08/29] for x86_64".

{$R+}

unit Quicksort;

interface

type
  orderRel = function(i, j: longint): boolean;                (* Order relation for sorting *)
  copierProc = procedure(i, j: longint);                      (* Used to copy matrix entry i to entry j *)

procedure qsort(n: longint; less: orderRel; cp: copierProc);  (* Quicksort takes two functions as arguments *)

implementation

procedure qsort(n: longint; less: orderRel; cp: copierProc);

  var left, rght: longint;

  procedure qsort1(a, b: longint);
  begin
  cp((a+b) div 2, n+1); (* Position n+1 of the matrix used as pivot *)
  left:= a; rght:= b;
  while left <= rght do begin
    while less(left, n+1) do inc(left);
    while less(n+1, rght) do dec(rght);
    if left <= rght then begin
      cp(left, n+2); cp(rght, left); cp(n+2, rght); (* Position n+2 used as auxiliar variable for swapping *)
      inc(left); dec(rght);
      end;
    end;
  if left < b then qsort1(left, b);
  if a < rght then qsort1(a, rght);
  end;

begin
qsort1(1,n);
end;

end.

Here is the test program:

program Test; (* For testing unit quicksort *)

uses quicksort;

const
  N = 9;

(* Matrices to be sorted.  One of integers, the other of strings *)

var
  int_arr:  array[1..N+2] of integer; (* Quicksort needs two extra working slots, hence N+2 *)
  st_arr:   array[1..N+2] of string;

(* Next two subroutines to be fed to Quicksort when sorting integer matrices *)

function int_comparisson (i, j: longint): boolean;
begin
int_comparisson:= int_arr[i] < int_arr[j];
end;

procedure int_copy(i, j: longint);
begin
int_arr[j]:= int_arr[i];
end;

(* Next two subroutines to be fed to Quicksort when sorting matrices of strings *)

function st_comparisson(i, j: longint): boolean;
begin
st_comparisson:= st_arr[i] < st_arr[j];
end;

procedure st_copy(i, j: longint);
begin
st_arr[j]:= st_arr[i];
end;

var
  i: integer;

begin

(* Initialize integer matrix *)
for i:= 1 to N do int_arr[i]:= random(100);

qsort(N, @int_comparisson, @int_copy); (* Quicksort takes two functions as arguments *)

for i:= 1 to N do write(int_arr[i]:5);
writeln;

(* Initialize matrix of strings *)
st_arr[1]:= 'the';
st_arr[2]:= 'quick';
st_arr[3]:= 'brown';
st_arr[4]:= 'fox';
st_arr[5]:= 'jumps';
st_arr[6]:= 'over';
st_arr[7]:= 'the';
st_arr[8]:= 'lazy';
st_arr[9]:= 'dog';

qsort(N, @st_comparisson, @st_copy);

for i:= 1 to N do write(st_arr[i], ' '); writeln;

end.

PS: Besides comparing and swaping, quicksort actually also needs to store a pivot, which obviously has to have the same type of the other matrix entries. Rather than providing a extra variable to play the role of the pivot, which would inevitably require the matrix type to be revealed, the solution is to allow quicksort to acess one unused matrix entry, say entry n+1. One more entry, namely n+2, is then used as the auxiliary variable for swaping.