Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 19
Scan from the left for a swap candidate. Element 8
is identified because it is greater than the pivot.
Now scan from the right to identify 2 as the
candidate from the right part. Swap 2 and
8 to get
[5, 3, 2, 4, 7, 1, 0, 9, 8, 10, 6, 11].
Elements 7 and 0 are
identified for the next swap. The result is
[5, 3, 2, 4, 0, 1, 7, 9, 8, 10, 6, 11].
The next search for a swap pair gives us 7 from
the left side and
1 from the right side.
Since the cursors have crossed, we simply swap right side candidate with the
pivot to get
[1, 3, 2, 4, 0] 5 [7, 9, 8, 10, 6, 11].