プログラミング言語 C

・次の関数は整数配列を整列させるためのシェルソートである。

・ 1959年に D.L.Shell によって考えられたこのソートアルゴリズムの基本概念は、

初期の段階で、単純な交換配列のようなとなりあった要素間の比較を行うのではなく、まず遠くの離れた要素間の比較を行う

ことにある。

・これは大量の (データの) 無秩序をすばやく整列させるという利点をもち、したがって (ソートの) 後半ではあまり多量の仕事を必要としない。

・ (なぜなら) 比較する要素間の間隔がしだいに小さくなり、それが 1 になるとこの整列法は事実上、(単純な) 隣接交換法となる (からである)。

void shell_sort(int v[], int n)
}
int gap, i, j, tmp;
for (gap = n/2; gap > 0; gap /= 2) {
for (i = gap; i < n; i++) {
for (j = i - gap; j >= 0 && v[j] > v[j+gap]; j -= gap) {
tmp = v[j];
v[j] = v[j+gap];
v[j + gap] = tmp;
}
}
}
}

・ここには 3つの入れ子になったループがある。

・もっとも外側のループでは比較される要素間の gap をその値が 0 になるまで n/2 から 2 で割りながら小さくしていくよう制御している。

・真ん中のループでは要素にそって進行している。

・もっとも内側のループでは gap分だけ離れた 2つずつの要素を比較して整列していない要素を (tmp を使って) 入れかえている。

・ gap は (その間隔を) 1 になるまで減らしていくので最終的には正しい整列になる。

・ for文の一般性(?)により、もっとも外側のループでは順序だてて進行していないにもかかわらず、他のループと同一の形式をとっていることに注意してほしい。

・ C の演算子の 1つにコンマがある。この演算子は for文の中でもっともよく使われる。

・コンマで分けられた 2つの式は左から右へと計算され、右側の式の型と値が (そのままこの 2つの式全体の) 型と値になる。

・このように多くの式を for文中の各部分に記述することができ、インデックス中の並列処理が可能になる。

・ (当然のことだが) 関数引数や宣言中の変数を分離するときのコンマは演算子ではないので、左から右へ順に評価されるということは (C では) 保証されていない。

・このコンマ演算子は (できれば) ひかえめに使うべきである。そのもっとも適切な使用法としては相互に強く関連づけられた構文や多段階にわたる計算を 1つの式に含めなければならない場合のマクロがある。

・例として文字列 s をその位置で逆順にする関数 reverse() を示してみよう。

include
void reverse(char s[])
{
int c, i, j;
for (i = 0, j = strlen(s) - 1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
/* strlen() は文字列の長さを数える関数だった . . .よね ? */

・関数 reverse() の場合、要素の変換は 1つの (まとまった) 操作と考えることができるのでコンマ演算子を上のように使うのは適切だと思われる。(p75-76)