値の配列をソートするのではなく、昇順のインデックスリストを作る。
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int val[10];
int idx[10];
int top;
void print_idx(void)
{
printf("Top=%2d ", top);
for(int i = 0; i < 10; i++) {
printf("[%2d,%2d]", val[i], idx[i]);
}
putchar('\n');
}
int main(void)
{
int i;
/*
* ランダムな配列作成とインデックスリストの初期化
*/
for(i = 0; i < 10; i++) {
val[i] = i;
idx[i] = -1;
}
random_shuffle(val, val+10);
/*
* ソート
*/
top = 0;
for(i = 1; i < 10; i++) {
if(val[top] > val[i]) {
idx[i] = top;
top = i;
print_idx();
} else {
int pos = top;
while(idx[pos] != -1) {
if(val[idx[pos]] > val[i]) {
idx[i] = idx[pos];
idx[pos] = i;
break;
}
pos = idx[pos];
}
if(idx[pos] == -1) {
idx[pos] = i;
}
print_idx();
}
}
return 0;
}
----------
実行結果
Top= 1 [ 8,-1][ 1, 0][ 9,-1][ 2,-1][ 0,-1][ 5,-1][ 7,-1][ 3,-1][ 4,-1][ 6,-1]
Top= 1 [ 8, 2][ 1, 0][ 9,-1][ 2,-1][ 0,-1][ 5,-1][ 7,-1][ 3,-1][ 4,-1][ 6,-1]
Top= 1 [ 8, 2][ 1, 3][ 9,-1][ 2, 0][ 0,-1][ 5,-1][ 7,-1][ 3,-1][ 4,-1][ 6,-1]
Top= 4 [ 8, 2][ 1, 3][ 9,-1][ 2, 0][ 0, 1][ 5,-1][ 7,-1][ 3,-1][ 4,-1][ 6,-1]
Top= 4 [ 8, 2][ 1, 3][ 9,-1][ 2, 5][ 0, 1][ 5, 0][ 7,-1][ 3,-1][ 4,-1][ 6,-1]
Top= 4 [ 8, 2][ 1, 3][ 9,-1][ 2, 5][ 0, 1][ 5, 6][ 7, 0][ 3,-1][ 4,-1][ 6,-1]
Top= 4 [ 8, 2][ 1, 3][ 9,-1][ 2, 7][ 0, 1][ 5, 6][ 7, 0][ 3, 5][ 4,-1][ 6,-1]
Top= 4 [ 8, 2][ 1, 3][ 9,-1][ 2, 7][ 0, 1][ 5, 6][ 7, 0][ 3, 8][ 4, 5][ 6,-1]
Top= 4 [ 8, 2][ 1, 3][ 9,-1][ 2, 7][ 0, 1][ 5, 9][ 7, 0][ 3, 8][ 4, 5][ 6, 6]