アルゴリズムクイックリファレンス 第2版

4.1

 転置ソート

■

63

図4-3　小さい配列での挿入ソートの進展

4.1.2

 文脈

挿入ソート

は、要素数が少ないか、最初から集まりが「ほぼ整列」している場合に

使う。配列が「十分小さい」かどうかは、ハードウェアによっても、プログラミング

言語によっても異なる。実際には、比較される要素の型も重要になる。

4.1.3

 解

情報がポインタで格納されている場合、例 4-1の

C

プログラムは、比較関数

cmp

を使って、配列

ar

を整列する。

例

4-1

 ポインタを使った値の挿入ソート

void sortPointers(void **ar, int n,

int(*cmp)(const void *,const void *)) {

int j;

64

■

4

章 整列アルゴリズム

for (j = 1; j < n; j++) {

int i = j-1;

void *value = ar[j]

while (i >= 0 && cmp(ar[i], value)> 0) {

ar[i+1] = ar[i];

i--;

}

ar[i+1] = value;

}

}

A

が値で格納されている場合、サイズは

s

バイトの固定要素

n

個まで縮小できる。

値操作には比較関数とともに値をある位置から別の位置へとコピーする手段が必要 ...