４．ソート（教科書 p.205-p.273） 整列すなわちソートは、アプリケーションを作成する際には良く使われる基本的な操作であり、 今までに数多くのソートのアルゴリズムが考えられてきた。今回はこれらソートのアルゴリズム について学習していく。 ソートとは ソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき、一定の順序で 並べ替える操作である。ソートには図１に示すように、キーの値の小さいデータを先頭に並べる、 昇順とその逆の降順がある。通常の英和辞典を例にとるとアルファベットをキーとして昇順に並 べてあることが分かる。 ソート前 昇順 降順 図１ 昇順と降順 ソートを行った時、図２に示すように等しいキー値をもつデータの位置関係がソート前後にお いても保たれるアルゴリズムは安定なソートと呼ばれている。ソートには安定なソートと安定で ないソートがある。 ソート前 1 2 3 4 6 7 8 9 3 2 4 9 1 6 8 0 5 7 0 5 ソート後 ソート前後で同一キー値の順序関係が維持される 図２ ソートを行う際に、コンピュータのメモリ上に確保される配列だけソートを行う場合と、外部 記憶装置上のファイルとのやり取りを行いながらソートを行う場合によって、以下のように呼び 方が異なる。 ■内部ソート ソートの対象となるすべてのデータが 1 つの配列上に 格納できる場合に用いられる。 ■外部ソート ソートの対象となるデータが大量であり、1 度に並べかえる ことができない場合に用いられる。 外部ソートは内部ソートの応用となるが、その実現には作業用ファイルを用いたりするなど、 複雑なアルゴリズムとなる。今回は内部ソートのアルゴリズムについて学習していく。 ソートを行うに当たって考え方の 3 大要素がある。交換・選択・挿入である。ほとんどのソー トアルゴリズムはこれらの考え方の応用で実現されている。 単純交換ソート（バブルソート）
次に示す数値の並びを昇順にソートするものとする。
6
4
3
7
1
9
8
このソートでは配列の末尾側から操作を行っていく。まず、末尾の数値 9 と 8 に着目する。昇 順にソートするので、この値を交換すると以下の数値の並びになる。6
4
3
7
1
8
9
次に末尾側から 2 番目と 3 番目の 1 と 8 に着目する。昇順に並んでいるので、この場合は交換 を行う必要がない。このように、隣り合う要素を比較し、必要ならば、交換する作業を先頭要素 まで続けていく様子を示したのが、図３である。 0 1 2 3 4 5 6 6 4 3 7 1 9 8 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 1 7 8 9 6 4 1 3 7 8 9 6 1 4 3 7 8 9 6 4 3 7 1 8 9 比較して交換する 比較するが交換しない 最小要素が先頭 へと移動する 6回 図３ 単純交換ソートにおける 1 回目のパス この操作を完了すると最小要素である 1 が配列の先頭に移動する。比較・必要に応じた交換を 1 セットの操作と考えると、ソートすべき要素数が n であるとき n – 1 回の操作が必要となるこ とが分かる。ここまでの、一連の比較・交換の作業をパスと呼ぶ。1 回目のパスが終了した状態 から、2 回目のパスを行った様子を以下の図４に示す。 0 1 2 3 4 5 6 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 3 4 7 1 8 9 6 4 3 7 1 8 9 5回 2番目に小さい要素が 2番目へと移動する 図４ 単純交換ソートにおける 2 回目のパス2 回目のパスは、配列の 1 番目の要素を除いて行うため、2 回目のパスで行われる比較・交換の 操作は 1 つ減って n – 2 回となる。このようにパスを行うたびにソートすべき要素数が 1 つずつ 減っていく。したがって、パスを（n - 1）回行うと全体のソートが完了する。（先頭から n – 1 個の要素がソート済みとなると、残った末尾要素は必ず最大値となるため、パスを 1 回省略する ことができる。） 以上のアイデアによって配列のソートを行うアルゴリズムが単純交換ソートである。値の小さ いデータが先頭に上昇していく様子を液体中の泡と例えて、バブルソートあるいは泡立ちソート とも呼ばれる。 教科書 p.211 の List6-1 の単純交換ソートのプログラムを以下に転載する。 List6-1 /* 単純交換ソート */ #include <stdio.h> #include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0) /*--- 単純交換ソート ---*/
void bubble(int a[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) { for (j = n - 1; j > i; j--)
if (a[j - 1] > a[j])
swap(int, a[j - 1], a[j]); } } int main(void) { int i, nx; int *x; /* 配列の先頭要素へのポインタ */ puts("単純交換ソート"); printf("要素数 : "); scanf("%d", &nx);
x = calloc(nx, sizeof(int)); /* 要素数nxのint型配列を生成 */ for (i = 0; i < nx; i++) { printf("x[%d] : ", i); scanf("%d", &x[i]); } bubble(x, nx); /* 配列xを単純交換ソート */ puts("昇順にソートしました。"); for (i = 0; i < nx; i++) printf("x[%d] = %d\n", i, x[i]); free(x); /* 配列を解放 */
return 0; } 出力例（斜体は入力値） 単純交換ソート 要素数 : 7 x[0] : 22 x[1] : 5 x[2] : 11 x[3] : 32 x[4] : 120 x[5] : 68 x[6] : 70 昇順にソートしました。 x[0] = 5 x[1] = 11 x[2] = 22 x[3] = 32 x[4] = 68 x[5] = 70 x[6] = 120 ここからはアルゴリズムの改良について考える。先ほどまでは 2 回目のパスによって 2 番目に 小さい要素を並べるまでの様子を示した。さらに比較・交換の操作を続けていく。図５に 3 回目 のパスを示す。 0 1 2 3 4 5 6 6 4 3 7 1 8 9 4回 3番目に小さい要素が 3番目へと移動する 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 図５ 単純交換ソートにおける 3 回目のパス パスの終了後、3 番目に小さい要素である 4 が 3 番目に移動していることが確認できる。続い て、4 回目のパスを図６に示す。 0 1 2 3 4 5 6 4番目に小さい要素は 最初からここに存在 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 3回 交換は一度も行われない 図６ 単純交換ソートにおける 4 回目のパス
4 回目のパスでは要素の交換が 1 度も行われない。これは 3 パス目でソートがすでに完了して いるためである。したがって、5 パス目以降も要素の交換は行われない。各パスにおいて、要素 が交換された回数をカウントしておき、その値が 0 であったならば、すべての要素がソート済み であると判断することができ、それ以降のパスを省略することができる。ソート済みの配列や、 それに近い状態の配列からソートするとき、この打ち切りを導入すると非常に高速に動作するこ とになる。この打ち切りを導入した単純交換ソートの関数（教科書 p.213 の List6-2）を以下に 転載する。 List6-2 /*--- 単純交換ソート（第２版：交換回数による打切り）---*/ void bubble(int a[], int n)
{ int i, j; for (i = 0; i < n - 1; i++) { int exchg = 0; /* パスにおける交換回数 */ for (j = n - 1; j > i; j--) if (a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]); exchg++; } if (exchg == 0) break; /* 交換が行われなかったら終了 */ } } 次は、{1, 3, 9, 4, 7, 8, 6}に対して単純交換ソートを行ってみる。最初のパスにおける比較・ 交換の過程を示したのが、図７である。 6 4 3 7 1 9 8 0 1 2 3 4 5 6 6回 最後に交換した位置より 先頭側は整列済みとなる 6 4 3 7 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 9 8 交換なし 図７ 単純交換ソートにおける 1 回目のパス この例では★の時点で先頭の 3 要素がソート済みであり、それ以降の交換が行われていない。 このことから、一連の比較・交換を行うパスにおいて、ある時点以降に交換がない場合、それよ り先頭側はソート済みであり、次のパスでは走査範囲を限定することが分かる。したがって、2 回目のパスは、先頭を除いた要素ではなく、図８に示すように 4 つの要素を対象とすれば良い。
6 4 3 7 1 9 8 0 1 2 3 4 5 6 6 4 3 7 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 9 8 3回 図８ 単純交換ソートにおける 2 回目のパス このアイデアに基づいて改良した関数（教科書 p.215 の List6-3）を以下に転載する。 List6-3 /*--- 単純交換ソート（第３版：走査範囲を限定）---*/ void bubble(int a[], int n)
{ int k = 0; /* a[k]より前はソート済み */ while (k < n - 1) { int j; int last = n - 1; /* 最後に交換した位置 */ for (j = n - 1; j > k; j--) if (a[j - 1] > a[j]) {
swap(int, a[j - 1], a[j]); last = j; } k = last; } } 単純選択ソート 次に示す数値の並びを昇順にソートするものとする。
6
4
8
3
1
9
7
まず、最小である要素 1 に着目する。これは、先頭に位置すべきものであるので、先頭要素の 6 と交換すると、以下となる。6
4
3
7
1
8
9
引き続き、2 番目に小さい要素 3 に着目する。先頭から 2 番目に位置する 4 と交換すると、次 に示すように、2 番目の要素までのソートが完了する。6
4
3
7
1
8
9
同様の操作を続けていく様子を図９に示す。0 1 2 3 4 5 6 6 4 8 3 1 9 7 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 8 9 6 4 3 7 1 9 8 6 4 3 7 1 8 9 ソート済み 未ソート部 未ソート部の先頭要素 未ソート部の最小要素 図９ 単純選択ソート このように、最小の要素を選択し、それを先頭の要素と交換することによって、ソートを行う 方法が単純選択ソートである。単純選択ソートの関数（教科書 p.217 の List6-4）を以下に転載 する。この関数の利用については、前述のプログラム List6-1 において、関数 bubble と置き換え るなどすれば良い。 List6-4 /*--- 単純選択ソート ---*/ void selection(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { int min = i; for (j = i + 1; j < n; j++) if (a[j] < a[min]) min = j; swap(int, a[i], a[min]); }
}
なお、離れた要素を交換することがあるので、このアルゴリズムは安定ではない。安定でない ソートが行われる例を図１０に示す。
1
3
**4
3
*2
1
4
2
3
**3
*1
2
4
3
**3
*1
2
3
**4
3
*1
2
3
**3
*4
0 1 2 3 4 先頭側の3が後ろ側に、 末尾側の3が先頭側に移動する 図１０ 単純選択ソートが安定でないことを示す例 単純挿入ソート（シャトルソート） 単純挿入ソートは、シャトルソートとも呼ばれる。例として、次のデータの並びを考える。6
4
1
7
3
9
8
まず 2 番目の要素である 4 に着目する。これは先頭の 6 より先頭側に位置すべきであるので、 先頭に挿入する。これに伴って 6 を右にずらすと以下の状態になる。6
4
1
7
3
9
8
以下、同様にして、順に要素に着目し、それを＜適当な位置に挿入する＞操作を繰り返すと図 １１に示すようにソートが完了する。 0 1 2 3 4 5 6 着目要素を＜適当な位置へ挿入する＞ という作業を繰り返す 6 4 1 7 3 9 8 6 4 1 7 3 9 8 6 4 7 3 1 9 8 6 4 7 3 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 9 8 6 4 3 7 1 8 9 図１１ 単純挿入ソート ＜適当な位置に挿入する＞処理の具体的な手続きの例を図１２に示す。左側の要素が、挿入すべ き値より大きければ、左隣の要素の値を代入する作業を前方に走査しながら繰り返す。ただし、 挿入する値以下の要素に出会うと、そこから先は比較・交換の必要がないので、そこに挿入する 値を代入する。6
4
7
3
1
9
8
6
4
7
7
1
9
8
6
4
7
1
9
8
6
4
7
1
9
8
6
3
① ② ③ ④ ①～③…3より小さい要素に出会うまで一つ左側の 要素を代入する ④ …ストップした位置に3を代入 図１２ 単純挿入ソートにおける挿入の手続き 以下に、単純挿入ソートのプログラム（教科書 p.220 の List6-5）を転載する。 List6-5 /*--- 単純挿入ソート ---*/ void insertion(int a[], int n) {int i, j;
for (i = 1; i < n; i++) { int tmp = a[i];
for (j = i; j > 0 && a[j - 1] > tmp; j--) a[j] = a[j - 1]; a[j] = tmp; } } ここまでに学習してきた基本的な 3 つの単純ソートの時間計算量はいずれも O（n2）であり、非 常に効率が悪い。次回以降ではこれらのソートを改良した、効率の良いアルゴリズムを学習する。
課題４ 演習問題４ 以下の数列に関する問題である。これをそれぞれのソートを行った際の数列の変化の様子を示しな さい。（数列だけ示せば良い） 単純交換ソートについては処理を減らす工夫も学習したが、ここではそれらを考慮しなくて良い。 ５１ ７８ ８９ １０ ２１ ８２ ４３ 問１ 単純交換ソート：テキストの図３、図４などを参考にする。パスが終了した後の結果について 順次示していけば良い。 問２ 単純選択ソート：テキストの図９を参考にする。 問３ 単純挿入ソート：テキストの図１１を参考にする。 プログラミング プログラム１：List6-1 は単純交換ソートを用いてデータを昇順にソートするプログラムである。 このプログラムを降順にソートするよう、変更しなさい。 プログラム２：List6-4 は単純選択ソートを用いてデータを昇順にソートする関数である。この関数を List6-1 の関数 bubble と交換し、単純選択ソートを行うことが可能なソースプログラムに変更しなさ い。さらに、このプログラムを降順にソートするよう、変更しなさい。 プログラム３：List6-5 は単純挿入ソートを用いてデータを昇順にソートするプログラムである。 このプログラムを降順にソートするよう、変更しなさい。
