Quicksort

There is a second way we can apply the idea of divide and conquer to the problem of sorting, the so-called quicksort algorithm [AHU1974].

Suppose we have to sort a set of integers S. The idea is to choose X, an arbitrary element of S, and to divide S into three disjoint sets S₁, S₂, and S₃, such that S₁ contains integers that are less than X, S₂ contains integers equal to X, and S₃ contains integers that are greater that X. Then, by sorting S₁, S₂, and S₃, we get three ordered sequences Q₁, Q₂, and Q₃ (the sorting of Q2 is trivial, because all elements of Q₂ are equal to X). Then we can concatenate Q₁, Q₂, and Q₃ into the new sequence Q₁ Q₂ Q₃, which gives us the solution to the original problem.

Now we can define the function QSort, which sorts an integer sequence according to the above method. The auxiliary function Split is used for partitioning the input sequence into three subsequences.

$func QSort  eS = eQ;
$func Split  sX eS = (eS1)(eS2)(eS3);
$func SplitAux  sX (eS1)(eS2)(eS3) eS = (eS1)(eS2)(eS3);

QSort  eS =
  {
  eS :
    = ;
  eS  : t
    = eS;
  eS : sX e
    = <Split sX eS> :: (eS1)(eS2)(eS3),
        <QSort eS1> eS2 <QSort eS3>;
  };

Split  sX eS =
   <SplitAux sX ()()() eS>;

SplitAux  sX (eS1)(eS2)(eS3) eS =
  eS :
  {
  =
    (eS1)(eS2)(eS3);
  sY eRest =
    {
    <Lt (sY)(sX)>
      = <SplitAux sX (eS1 sY)(eS2)(eS3) eRest>;
    <Gt (sY)(sX)>
      = <SplitAux sX (eS1)(eS2)(eS3 sY) eRest>;
      = <SplitAux sX (eS1)(eS2 sY)(eS3) eRest>;
    };
  };