Originally Posted by
Adak
I have no use whatsoever for Selection sort. Never liked it, and on my PC's, it was always the slowest sorter.
Really? My measurements disagree.
Using Athlon II X4 640 (with a stable time stamp counter), median cycle counts for test sorts for uniform random input were
Code:
# N ints, no padding, 100000 tests, +66 cycles overhead
# N Bubble Selection Insertion
4 59 41 116
6 149 167 284
8 321 335 459
12 804 750 882
16 1391 1224 1373
24 2901 2436 2522
32 4850 3969 3858
40 7253 5804 5358
48 10127 7923 7012
56 13493 10321 8799
64 17363 12996 10750
# N ints, 12 chars padding, 100000 tests, +66 cycles overhead
# N Bubble Selection Insertion
4 75 60 119
6 171 189 269
8 321 375 422
12 845 809 778
16 1514 1313 1203
24 3120 2588 2154
32 5092 4208 3282
40 7430 6182 4562
48 10145 8499 5959
56 13230 11160 7500
64 16847 14145 9160
# N ints, 124 chars padding, 100000 tests, +66 cycles overhead
# N Bubble Selection Insertion
4 240 167 224
6 573 352 488
8 1074 600 794
12 2624 1134 1593
16 4748 1748 2408
24 10862 3228 4733
32 18602 4925 7566
40 28238 7031 11066
48 40846 9410 15161
56 55593 12045 19851
64 71924 14864 25133
Here is the array element the above functions sort:
Code:
typedef int key_t;
struct data {
key_t key;
#ifdef PADDING
#if PADDING > 0
char padding[PADDING];
#endif
#endif
};
with PADDING defined at compile time as per comments in the above results. The actual sort functions were compiled optimized (gcc -W -Wall -O3 -fomit-frame-pointer) separately from other parts. The sort functions themselves, should you care to test, are:
Code:
/* Swap two data entries.
*/
static inline void data_swap(struct data *const data, const size_t dst, const size_t src)
{
if (dst != src) {
struct data temp;
temp = data[src];
data[src] = data[dst];
data[dst] = temp;
}
}
/* Insert src into dst, if src > dst.
*/
static inline void data_insert(struct data *const data, const size_t dst, const size_t src)
{
if (dst < src) {
struct data temp;
temp = data[src];
memmove(data + dst + 1, data + dst, (src - dst) * sizeof *data);
data[dst] = temp;
}
}
void no_sort(struct data *const data __attribute__((unused)), size_t const elements __attribute__((unused)))
{
return;
}
void bubble_sort(struct data *const data, size_t const elements)
{
size_t n = elements + 1;
while (n-- > 0) {
size_t i = 1;
while (i < n && data[i-1].key <= data[i].key)
i++;
if (i >= n)
return;
while (i < n) {
if (data[i-1].key > data[i].key)
data_swap(data, i-1, i);
i++;
}
}
}
void selection_sort(struct data *const data, size_t const elements)
{
size_t i = elements;
while (i-- > 1) {
size_t max_ref = i;
key_t max_key = data[i].key;
size_t k = i;
while (k-- > 0)
if (data[k].key > max_key) {
max_key = data[k].key;
max_ref = k;
}
data_swap(data, max_ref, i);
}
}
void insertion_sort(struct data *const data, size_t const elements)
{
size_t i;
for (i = 1; i < elements; i++) {
const key_t key_i = data[i].key;
if (data[0].key > key_i)
data_insert(data, 0, i);
else {
size_t k = i;
while (data[k - 1].key > key_i)
k--;
data_insert(data, k, i);
}
}
}
I did try to avoid cache effects -- each function sorted their own arrays, with identical new data generated for each before each timing iteration. As mentioned above, the median cycle counts were collected from hundred thousand iterations.
You could say that sorting small arrays of large structures (124 chars or 31 ints of payload per sort key) is silly, but I won't rule it out. That's where I said selection sort works well, and the data above seems to back me up on that.
My insertion sort routine could do with a bit more finesse, too. If the cutoff for quicksort is around the 32 element mark, as I've used, then selection sort does not look too bad. Remember that the idea is to use the least number of cycles overall, not pick the one that gives the minimum in some corner case. So you need to consider the relative differences, and the typical array size.
These results are not conclusive in any way, as only uniformly random source data was even tested: bubble sort and insertion sort would have much more of an advantage with nearly-sorted or even partially-sorted inputs. However, these are the basis for my earlier statements, and I definitely refuse to discard any of the sorting algorithms outright.
But I have not tested it on miniscule quantities of 5 or 12, or anything less than 50 integers.
It should be easy to fix for any interested person; just modify the
