2.2 Sorting algorithm
The sorting algorithm, using the partitioning algorithm, is rather simple. It is listed in listing 2.
1define sub quicksort
2 by reference a :
array 3 by value b :
integer 4 by value e :
integer 5 local p :
integer;
6 p← partition(
a,
b,
e,
e)
7 if b<
p−1
then 8 quicksort(
a,
b,
p−1)
9 end if 10 if e>p+1
then 11 quicksort(
a,
p+1,
e)
12 end if 13end define sub
Here is an analysis of the algorithm:
- line 6 partitions the array, and it returns the index of the partition element. Note that the partition element is
already at the correct position when partition returns.
- line 7 checks to see if there is any need to call recursively for the left hand side of the pivot. If at most one
element is to be sorted, then there is nothing to do.
- line 10 does the same thing as the previous point, but with the other side of the pivot.