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 S1,
S2, and S3, such that
S1 contains integers that are less than X,
S2 contains integers equal to X, and
S3 contains integers that are greater that X.
Then, by sorting S1, S2, and
S3, we get three ordered sequences
Q1, Q2, and
Q3 (the sorting of Q2 is trivial, because all
elements of Q2 are equal to X). Then we can
concatenate Q1, Q2, and
Q3 into the new sequence Q1 Q2
Q3, 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>;
};
};