4. ソート ( 教科書 p.205-p.273) 整列すなわちソートは アプリケーションを作成する際には良く使われる基本的な操作であり 今までに数多くのソートのアルゴリズムが考えられてきた 今回はこれらソートのアルゴリズムについて学習していく ソートとはソートとは与えられたデータの集合をキーとなる項目の値の大小関係に基づき 一定の順序で並べ替える操作である ソートには図 1 に示すように キーの値の小さいデータを先頭に並べる 昇順とその逆の降順がある 通常の英和辞典を例にとるとアルファベットをキーとして昇順に並べてあることが分かる ソート前 昇順 降順 図 1 昇順と降順 ソートを行った時 図 2 に示すように等しいキー値をもつデータの位置関係がソート前後においても保たれるアルゴリズムは安定なソートと呼ばれている ソートには安定なソートと安定でないソートがある ソート前 ソート後 7 8 9 3 2 4 9 1 6 8 7 0 5 ソート前後で同一キー値の順序関係が維持される図 2 ソートを行う際に コンピュータのメモリ上に確保される配列だけソートを行う場合と 外部記憶装置上のファイルとのやり取りを行いながらソートを行う場合によって 以下のように呼び方が異なる 内部ソートソートの対象となるすべてのデータが 1 つの配列上に格納できる場合に用いられる 外部ソートソートの対象となるデータが大量であり 1 度に並べかえることができない場合に用いられる 外部ソートは内部ソートの応用となるが その実現には作業用ファイルを用いたりするなど 複雑なアルゴリズムとなる 今回は内部ソートのアルゴリズムについて学習していく ソートを行うに当たって考え方の 3 大要素がある 交換 選択 挿入である ほとんどのソートアルゴリズムはこれらの考え方の応用で実現されている 単純交換ソート ( バブルソート ) - 1 -
次に示す数値の並びを昇順にソートするものとする 6 4 3 7 1 9 8 このソートでは配列の末尾側から操作を行っていく まず 末尾の数値 9 と 8 に着目する 昇順にソートするので この値を交換すると以下の数値の並びになる 6 4 3 7 1 8 9 次に末尾側から 2 番目と 3 番目の 1 と 8 に着目する 昇順に並んでいるので この場合は交換 を行う必要がない このように 隣り合う要素を比較し 必要ならば 交換する作業を先頭要素 まで続けていく様子を示したのが 図 3である 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 回 6 4 1 3 7 8 9 6 1 4 3 7 8 9 1 6 4 3 7 8 9 最小要素が先頭へと移動する 比較して交換する 比較するが交換しない 図 3 単純交換ソートにおける 1 回目のパス この操作を完了すると最小要素である 1 が配列の先頭に移動する 比較 必要に応じた交換を 1 セットの操作と考えると ソートすべき要素数が n であるとき n 1 回の操作が必要となるこ とが分かる ここまでの 一連の比較 交換の作業をパスと呼ぶ 1 回目のパスが終了した状態 から 2 回目のパスを行った様子を以下の図 4に示す 1 6 4 3 7 8 9 1 6 4 3 7 8 9 1 6 4 3 7 8 9 5 回 1 6 4 3 7 8 9 1 6 3 4 7 8 9 1 3 6 4 7 8 9 2 番目に小さい要素が 2 番目へと移動する図 4 単純交換ソートにおける 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); /* 配列を解放 */ - 3 -
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 番目に 小さい要素を並べるまでの様子を示した さらに比較 交換の操作を続けていく 図 5に 3 回目 のパスを示す 1 3 6 4 7 8 9 1 3 6 4 7 8 9 4 回 1 3 6 4 7 8 9 1 3 6 4 7 8 9 3 番目に小さい要素が 3 番目へと移動する 図 5 単純交換ソートにおける 3 回目のパス パスの終了後 3 番目に小さい要素である 4 が 3 番目に移動していることが確認できる 続いて 4 回目のパスを図 6 に示す 3 回 4 番目に小さい要素は最初からここに存在 交換は一度も行われない 図 6 単純交換ソートにおける 4 回目のパス - 4 -
4 回目のパスでは要素の交換が 1 度も行われない これは 3 パス目でソートがすでに完了しているためである したがって 5 パス目以降も要素の交換は行われない 各パスにおいて 要素が交換された回数をカウントしておき その値が 0 であったならば すべての要素がソート済みであると判断することができ それ以降のパスを省略することができる ソート済みの配列や それに近い状態の配列からソートするとき この打ち切りを導入すると非常に高速に動作することになる この打ち切りを導入した単純交換ソートの関数 ( 教科書 p.213 の List6-2) を以下に転載する List6-2 /*--- 単純交換ソート ( 第 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 に対して単純交換ソートを行ってみる 最初のパスにおける比較 交換の過程を示したのが 図 7 である 1 3 9 4 7 8 6 1 3 9 4 7 6 8 1 3 9 4 6 7 8 1 3 9 4 6 7 8 6 回 交換なし 最後に交換した位置より先頭側は整列済みとなる 図 7 単純交換ソートにおける 1 回目のパス この例では の時点で先頭の 3 要素がソート済みであり それ以降の交換が行われていない このことから 一連の比較 交換を行うパスにおいて ある時点以降に交換がない場合 それより先頭側はソート済みであり 次のパスでは走査範囲を限定することが分かる したがって 2 回目のパスは 先頭を除いた要素ではなく 図 8 に示すように 4 つの要素を対象とすれば良い - 5 -
3 回 1 3 4 6 9 7 8 図 8 単純交換ソートにおける 2 回目のパスこのアイデアに基づいて改良した関数 ( 教科書 p.215 の List6-3) を以下に転載する List6-3 /*--- 単純交換ソート ( 第 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 と交換すると 以下となる 1 4 8 3 6 9 7 引き続き 2 番目に小さい要素 3 に着目する 先頭から 2 番目に位置する 4 と交換すると 次に示すように 2 番目の要素までのソートが完了する 同様の操作を続けていく様子を図 9 に示す 1 3 8 4 6 9 7-6 -
6 4 8 3 1 9 7 1 4 8 3 6 9 7 未ソート部の最小要素未ソート部の先頭要素 1 3 8 4 6 9 7 1 3 4 8 6 9 7 ソート済み 未ソート部 1 3 4 6 8 9 7 1 3 4 6 7 9 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]); なお 離れた要素を交換することがあるので このアルゴリズムは安定ではない 安定でないソートが行われる例を図 10 に示す - 7 -
0 1 2 3 4 4 3 ** 1 3 * 2 1 4 2 3 ** 3 * 1 2 4 3 ** 3 * 1 2 3 ** 4 3 * 1 2 3 ** 3 * 4 先頭側の3が後ろ側に 末尾側の3が先頭側に移動する図 10 単純選択ソートが安定でないことを示す例 単純挿入ソート ( シャトルソート ) 単純挿入ソートは シャトルソートとも呼ばれる 例として 次のデータの並びを考える 6 4 1 7 3 9 8 まず 2 番目の要素である 4 に着目する これは先頭の 6 より先頭側に位置すべきであるので 先頭に挿入する これに伴って 6 を右にずらすと以下の状態になる 4 6 1 7 3 9 8 以下 同様にして 順に要素に着目し それを < 適当な位置に挿入する > 操作を繰り返すと図 11 に示すようにソートが完了する 6 4 1 7 3 9 8 4 6 1 7 3 9 8 1 4 6 7 3 9 8 1 4 6 7 3 9 8 1 3 4 6 7 9 8 1 3 4 6 7 9 8 着目要素を < 適当な位置へ挿入する > という作業を繰り返す 図 11 単純挿入ソート < 適当な位置に挿入する > 処理の具体的な手続きの例を図 12 に示す 左側の要素が 挿入すべき値より大きければ 左隣の要素の値を代入する作業を前方に走査しながら繰り返す ただし 挿入する値以下の要素に出会うと そこから先は比較 交換の必要がないので そこに挿入する値を代入する - 8 -
1 4 6 7 3 9 8 1 1 4 6 7 7 9 8 2 1 4 6 6 7 9 8 3 1 3 4 6 7 9 8 4 1~3 3より小さい要素に出会うまで一つ左側の要素を代入する 4 ストップした位置に3を代入 図 12 単純挿入ソートにおける挿入の手続き 以下に 単純挿入ソートのプログラム ( 教科書 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(n 2 ) であり 非常に効率が悪い 次回以降ではこれらのソートを改良した 効率の良いアルゴリズムを学習する - 9 -
課題 4 演習問題 4 以下の数列に関する問題である これをそれぞれのソートを行った際の数列の変化の様子を示しなさい ( 数列だけ示せば良い ) 単純交換ソートについては処理を減らす工夫も学習したが ここではそれらを考慮しなくて良い 51 78 89 10 21 82 43 問 1 単純交換ソート : テキストの図 3 図 4 などを参考にする パスが終了した後の結果について順次示していけば良い 問 2 単純選択ソート : テキストの図 9 を参考にする 問 3 単純挿入ソート : テキストの図 11 を参考にする プログラミングプログラム 1:List6-1 は単純交換ソートを用いてデータを昇順にソートするプログラムである このプログラムを降順にソートするよう 変更しなさい プログラム 2:List6-4 は単純選択ソートを用いてデータを昇順にソートする関数である この関数を List6-1 の関数 bubble と交換し 単純選択ソートを行うことが可能なソースプログラムに変更しなさい さらに このプログラムを降順にソートするよう 変更しなさい プログラム 3:List6-5 は単純挿入ソートを用いてデータを昇順にソートするプログラムである このプログラムを降順にソートするよう 変更しなさい - 10 -