Gabor Simko

An implementation of heap-sort is available for try at http://ideone.com/3tZslM. The output of the program is the following:

Success time: 0.43 memory: 7200 signal:0

Sorting       10 elements in       28 swaps
Sorting      100 elements in      576 swaps
Sorting     1000 elements in     9071 swaps
Sorting    10000 elements in   124213 swaps
Sorting   100000 elements in  1574718 swaps
Sorting  1000000 elements in 19044820 swaps

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)