Exercise 3 of Chapter 15.9 (List Exercises) provides pseudocode for an implementation of Quicksort.
Swap To Partition.
while ls < hs:
If a[ls].key ≤ a[middle].key: increment ls by 1. Move the low boundary of the partitioning.
If a[ls].key > a[middle].key: swap the values a[ls] and a[middle].
If a[hs].key ≥ a[middle].key: decrement hs by 1. Move the high boundary of the partitioning.
If a[hs].key < a[middle].key: swap the values a[hs] and a[middle].
I'm not sure whether the swap cases are supposed to be mutually exclusive from the increment statements (elif) or independent statements that might both be executed.
Either way, I'm not sure this pseudocode gives the correct result for the following sequence:
[1, 2, 10, 11, 12, 13, 3, 14, 15, 16, 17, 4, 5]
Since both 1 and 2 (assuming both if statements are executed) are < 3, 3 remains at the middle position after dealing with ls. Since 5 >= 3, it remains at the end position and gets sorted with the [middle+1, hi] partition rather than the [lo, middle] partition where it belongs.
Is there something I'm missing?