Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 31
First move the largest element to the right end to get
[7 3 6 8 11 14 0 2 12 1 4 13 5 9 10 16]
Next partition using 7 as the pivot.
The result is
[2 3 6 5 4 1 0] 7 [12 14 11 13 8 9 10 16]
The element we seek is the k = 5 element
in the left segment. So we proceed to partition this segment using
2 as the pivot. The result is
[1 0] 2 [5 4 6 3]
The element we seek is now in the right segment and we
set k = 5 - 3 = 2.
We proceed to partition the right segment using
5 as the pivot. The result is
[3 4] 5 [6]
The element we seek is now in the left segment and
k remains
2.
We proceed to partition the left segment using
3 as the pivot. The result is
[] 3 [4]
The element we seek is now in the right segment and we
set k = 2 - 1 = 1.
Since the size of the right segment is
1, its sole element 4
is returned
as the answer.