I found this paper, that describes an optimized version of selection sort, that is supposed to outperform the classic selection sort in general. On page 4, the pseudo code for this particular variant is described as follows:
k = 0
for i = n–1 to k
IndexOfLarge = IndexOfSmall = k
for j = k+1 to i
if (X[j] > X[IndexOfLarge])
IndexOfLarge = j
if (X[j] < X[IndexOfSmall])
IndexOfSmall = j
Large = X[IndexOfLarge]
Small = X[IndexOfSmall]
X[IndexOfLarge] = X[i]
X[IndexOfSmall] = X[k]
if (IndexOfLarge == k)
Temp = X[i]
X[i] = Large
X[IndexOfSmall] = Temp
Else
X[i] = Large
if (IndexOfSmall == i)
Temp = X[k]
X[k] = Small
X[IndexOfLarge] = Temp
Else
X[k] = Small
k = k+1
It's fairly easy to translate that into C:
#include "selectionsort.h"
void selectionsort(int *array, size_t num) {
int *x = array;
for(int i = num-1, k = 0; i > k; --i, ++k) {
int i_small = k;
int i_large = k;
for(int j = k+1; j <= i; ++j) {
if(x[j] > x[i_large]) {
i_large = j;
}
if(x[j] < x[i_small]) {
i_small = j;
}
}
int large = x[i_large];
int small = x[i_small];
x[i_large] = x[i];
x[i_small] = x[k];
int tmp;
if(i_large == k) {
tmp = x[i];
x[i] = large;
x[i_small] = tmp;
} else {
x[i] = large;
}
if(i_small == i) {
tmp = x[k];
x[k] = small;
x[i_large] = tmp;
} else {
x[k] = small;
}
}
Now it turns out, this particular implementation doesn't always sort all inputs fully. For example, below is an array of 100 random integers, ranging from 0 to 100. If laid out for each iteration, then in the last two lines, right in the middle of the array, you will see the number 52 simply being overwritten.
0 86 85 24 38 64 29 8 50 38 64 1 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 98 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 97 95 14 33 88 78 93 89 60 36 80 46 44 8 41 0 59 66 25 89 61 42 85 20 44 33 76 55 36 87 97 32 47 10 32 0 88 24 55 13 61 35 60 71 98
0 0 85 24 38 64 29 8 50 38 64 1 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 97 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 97 32 47 10 32 0 88 24 55 13 61 35 60 98 98
0 0 0 24 38 64 29 8 50 38 64 1 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 97 32 47 10 32 85 88 24 55 13 61 35 97 98 98
0 0 0 1 38 64 29 8 50 38 64 24 71 71 93 1 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 96 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 55 13 61 97 97 98 98
0 0 0 1 1 64 29 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 1 83 78 25 20 7 55 61 57 59 59 59 29 96 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 55 13 96 97 97 98 98
0 0 0 1 1 1 29 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 64 83 78 25 20 7 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 95 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 55 96 96 97 97 98 98
0 0 0 1 1 1 7 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 94 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 24 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 50 38 64 24 71 71 93 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 8 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 88 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 38 64 24 71 71 88 38 35 18 52 31 10 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 93 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 85 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 64 24 71 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 90 11 36 10 76 60 55 14 33 88 78 93 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 32 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 24 71 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 90 11 36 64 76 60 55 14 33 88 78 32 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 10 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 71 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 24 11 36 64 76 60 55 14 33 88 78 32 89 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 47 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 71 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 13 17 30 85 35 49 24 71 36 64 76 60 55 14 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 89 61 42 85 20 44 33 76 55 36 87 35 32 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 88 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 17 30 85 35 49 24 71 36 64 76 60 55 14 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 36 87 35 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 38 35 18 52 31 38 88 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 17 30 85 35 49 24 71 36 64 76 60 55 35 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 36 87 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 35 18 52 31 38 87 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 88 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 36 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 35 52 31 38 87 21 64 61 85 39 71 26 71 24 64 83 78 25 20 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 55 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 52 31 38 55 21 64 61 85 39 71 26 71 24 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 86 59 66 25 32 61 42 85 20 44 33 76 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 31 38 55 21 64 61 85 39 71 26 71 24 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 85 52 44 33 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 38 55 31 64 61 33 39 71 26 71 24 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 85 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 85 52 44 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 55 31 64 61 33 39 71 26 71 38 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 24 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 85 52 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 31 64 61 33 39 71 26 71 38 64 83 78 25 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 52 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 64 61 33 39 71 26 71 38 64 52 78 31 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 80 46 44 50 41 76 59 66 25 32 61 42 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 61 33 39 71 26 71 38 64 52 78 31 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 42 46 44 50 41 76 59 66 64 32 61 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 33 39 71 61 71 38 64 52 61 31 35 29 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 78 32 47 60 36 42 46 44 50 41 76 59 66 64 32 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 39 71 61 71 38 64 52 61 31 35 33 55 61 57 59 59 59 29 71 38 30 44 35 49 55 71 36 64 76 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 76 59 66 64 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 71 61 71 38 64 52 61 31 35 33 55 61 57 59 59 59 39 71 38 30 44 35 49 55 71 36 64 64 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 76 59 66 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 61 71 38 64 52 61 31 35 33 55 61 57 59 59 59 39 71 38 71 44 35 49 55 71 36 64 64 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 66 59 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 59 38 64 52 61 61 35 33 55 61 57 59 59 59 39 71 38 71 44 35 49 55 71 36 64 64 60 55 35 33 36 32 32 47 60 36 42 46 44 50 41 66 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 38 64 52 61 61 35 33 55 61 57 59 59 59 39 66 38 71 44 35 49 55 71 36 64 64 60 55 35 33 36 59 32 47 60 36 42 46 44 50 41 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 64 52 61 61 35 33 55 61 57 59 59 59 39 66 38 41 44 35 49 55 71 36 64 64 60 55 35 33 36 59 38 47 60 36 42 46 44 50 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 52 61 61 35 64 55 61 57 59 59 59 39 66 38 41 44 35 49 55 50 36 64 64 60 55 35 33 36 59 38 47 60 36 42 46 44 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 61 61 35 64 55 61 57 59 59 59 39 44 38 41 44 35 49 55 50 36 64 64 60 55 35 52 36 59 38 47 60 36 42 46 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 61 61 46 55 61 57 59 59 59 39 44 38 41 44 35 49 55 50 36 64 64 60 55 35 52 36 59 38 47 60 36 42 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 61 46 55 61 57 59 59 59 39 44 38 41 44 61 49 55 50 36 42 64 60 55 35 52 36 59 38 47 60 36 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 46 55 61 57 59 59 59 39 44 38 41 44 61 49 55 50 36 42 36 60 55 61 52 36 59 38 47 60 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 55 60 57 59 59 59 39 44 38 41 44 61 49 55 50 46 42 36 60 55 61 52 36 59 38 47 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 60 57 59 59 59 39 44 38 41 44 47 49 55 50 46 42 55 60 55 61 52 36 59 38 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 57 59 59 59 39 44 38 41 44 47 49 55 50 46 42 55 60 55 38 52 60 59 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 59 59 59 39 44 57 41 44 47 49 55 50 46 42 55 59 55 38 52 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 59 59 39 44 57 41 44 47 49 55 50 46 42 55 59 55 59 52 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 59 52 44 57 41 44 47 49 55 50 46 42 55 59 55 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 52 44 57 59 44 47 49 55 50 46 42 55 59 55 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 57 55 44 47 49 55 50 46 52 55 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 57 55 44 47 49 55 50 46 52 55 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 55 55 47 49 55 50 46 52 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 55 47 49 55 50 52 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 47 52 49 55 50 55 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 47 49 52 50 55 55 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
0 0 0 1 1 1 7 8 8 10 10 10 11 13 14 17 18 20 20 21 24 24 25 25 26 29 29 30 31 32 32 33 33 35 35 35 36 36 36 38 38 39 41 42 44 44 46 47 49 50 50 55 55 55 57 59 59 59 59 60 60 61 61 61 64 64 64 66 71 71 71 71 76 76 78 78 80 83 85 85 85 86 87 88 88 88 89 89 90 93 93 93 94 95 96 96 97 97 98 98
For every input, there's always one value overwritten, but if I'm lucky, that value is overwritten by a duplicate, then it's sorted. But that doesn't always happen.
How do I fix this?
As @Bob__ points out, the program does the wrong thing when the largest element of one of the sub-arrays appears at the first position (unless the smallest element also appears at the last position). It appears that this error is faithfully copied from the referenced authors' pseudocode, which seems par for the course with that not-very-impressive paper. Inasmuch as their analysis of specific complexity is based on their pseudocode, its details are also called into question, though the fact that the algorithm is faster than simple selection sort is not in doubt.
In any event, I would write the swapping section of this code rather differently:
// swap the maximum and minimum elements into place, handling
// a bit of trickiness when one (or both) of the extreme values
// is at the far opposite end of the interval from where it belongs.
int large = x[i_large];
int small = x[i_small];
if (i_small == i) {
if (i_large != k) {
// Three-way swap: move the middle element to index i_large
x[i_large] = x[k];
} // else a straight swap of positions k and i
} else if (i_large == k) {
// Three-way swap: move the middle element to index i_small
x[i_small] = x[i];
} else {
// Two independent swaps
x[i_small] = x[k];
x[i_large] = x[i];
}
// In all cases:
x[k] = small;
x[i] = large;
That