This is an implementation of the quick-select algorithm in C++. The source code can be found and executed at http://ideone.com/I8rRVd. Below are the comparison of two strategies for selecting the pivot point.
First, when the last element of the sub-array is the pivot point (in parenthesis the #calls for the select function):
Success time: 2.51 memory: 42360 signal:0
#swaps for finding median of 1 elements: 0 (1) #swaps for finding median of 10 elements: 5 (2) #swaps for finding median of 100 elements: 161 (7) #swaps for finding median of 1000 elements: 1724 (8) #swaps for finding median of 10000 elements: 12006 (11) #swaps for finding median of 100000 elements: 219843 (18) #swaps for finding median of 1000000 elements: 1450364 (31) #swaps for finding median of 10000000 elements: 25450797 (24)
Second, when the median of median algorithm is used for selecting the pivot point:
Success time: 2.68 memory: 42360 signal:0
#swaps for finding median of 1 elements: 0 (1) #swaps for finding median of 10 elements: 16 (3) #swaps for finding median of 100 elements: 436 (23) #swaps for finding median of 1000 elements: 5182 (142) #swaps for finding median of 10000 elements: 53527 (581) #swaps for finding median of 100000 elements: 549237 (2708) #swaps for finding median of 1000000 elements: 5631455 (11244) #swaps for finding median of 10000000 elements: 55046982 (47626)