はじめての C

「ソート法 3」

void insertion_sort (int *list, int left, int right)
{
int step, i; /* <- これは リストの添字 */
int temp; /* <- こちらは 値 */
/*
* 左から 右へ 移動して、step と right の
* 間の 値 - values - を ソートする
*/
for (step = left; step < right; step++) {
/* h番目の 要素、list[step] を 選択 */
temp = list[step];
/*
* (逆順に) step から left へ 移動して、
* 必要なら 値を シフトする
*/
for (i = step; i >= left; i -= left)
/*
* ソートした値を セットする場所 - room - を
* つくるため、値を シフトする
*/
if (temp < list[i - left])
list[i] = list[i - left];
else
break;
/* ソートした値を 新しい位置へ セットする */
list[i] = temp;
}
}

挿入整列法では、リストの要素の 全総数を ソートするので、2つの 代入値 - arguments - しか 必要としません。 ここで 注意してほしいのは、この実装 - implementation - では それが 3つ あるということです。 つまり、リストと、ソートを 開始する 配列の左端 - left end -、それに ソートが 終了する 配列の右端 - right end - です。

これには 2つ 理由が あり、まず 1つ目は、この実装では、常に 0 から 始めて n まで 移動するかわりに、リストの ある部分だけを ソートできます。 分割した リストの部分 - piece - を 渡して、そこだけ ソートできるわけです。

2つ目の 理由としては、シェルソートの実装が 簡単に 行なえる、ということです。 では、どうするかを 手短かに - ただし 正確に - 説明しましょう。