2.1 Partitioning
The partitioning pseudocode is in listing 1.
1define sub partition
2 by reference a :
array 3 by value b :
integer // index of first element 4 by value e :
integer // index of last element 5 by value p :
integer 6 return type :
integer 7 local v : valuetype
8 local s :
integer 9 swap(
a[
e],
a[
p])
10 s←
b 11 v←a[
e]
12 while b<e do 13 if a[
b]
≤v then 14 swap(
a[
s],
a[
b])
15 s←s+1
16 end if 17 b←
b+1
18 end while 19 swap(
a[
s],
a[
e])
20 return s 21end define sub
This subalgorithm arranges the array so that:
- let v = a[p], both a and p are supplied as parameters
- after the algorithm completes, we have a b′ such that ∀i ∈ [b…b′] : a[i] ≤ v. In other words, everything to the
right of the index b′ are less than or equal to v.
- after the algorithm completes, we have a e′ such that ∀i ∈ [e′…e] : a[i] ≥ v.
- the original element a[p] will be a[e′].
In general, the algorithm scans from both ends to the inside until it finds an element that is “on the wrong side”. As soon
as a “wrong side” element is found, it is swapped with the next element from the other side, then scanning is resume from
the other side.