Quicksort Algorithm

Algorithm QuickSort(p,q)
//Sorts the elements a[p],.......,a[q] which resides in the global
//array a[1:n] into ascending order; a[n+1] is considered
//to be defined and must be >= all the elements in a[1:n].
{
if(p < q) then //If there are more than one element.
{
//divide P into two subproblems.

j:=Partition(a,p,q+1);

//j is the position of the partioning elements
//Solving the subproblems.
QuickSort(p,j-1);
QuickSort(j+1,q);
//Thereis no needfor combining solutions.
}
}

Algorithm Partition(a,m,p)
//Within a[m],a[m+1],....,a[p-1] the element are rearranged in such a manner that
//if initially t=a[m], and p-1, a[k]<=t for m<=k=t
//for q < k < p. q is returned.Set a[p]=infinity.

{
v:=a[m];i:=m; j:=p;
repeat
{
repeat
i:=i+1;
until(a[i]>=v);

repeat
j:=j-1;
until(a[j]<=v);

if(i }until(i>=j);

a[m]:=a[j]; a[j]:=v; return j;
}

Algorithm Interchange(a,i,j)
//Exchange a[i] with a[j]
{
p:=a[i];
a[i]:=a[j];
a[j]:=p;
}