配列のソート（整列）とは？
配列を値の大きさ順に並べ替えることを「ソート」（整列）といいます． 例えば，次のような並べ替えです．
5 2 3 1 4 => 1 2 3 4 5
小さい順に並び替えることを昇順ソート，大きい順に並び替えることを降順ソートといいます． ソートには多くの方法が知られています．
＊注意＊
以下に紹介するソート方法は，要素の数が増えると，ソートに必要な時間（あるいは比較回数）が急速に増大します（要素数を n とすると，必要な時間は n**2 に比例します）． このため，大規模な配列に使うことはできません． 計算時間の増加を押さえた高速なソート方法として，ヒープソート (heap sort) やクイックソート (quick sort) などが知られており，これらの方法では計算時間は n*log(n) に比例します．
バブルソート
バブルソート (bubble sort) は，隣り合う2つのデータを比較して，前の要素の方が大きかったら交換します． これを配列の後方から前方に対して行うと，最も小さいデータが先頭にきて，位置が確定します． 2回目のソートでは，ソート対象は2番目以降のデータになります． 2回目のソートで2番目に小さな要素が確定します． これを繰り返すとソートが完成します． 下の例をみるとわかるように，バブルソートでは値が泡のように浮かび上がっていきます．
5, 2, 3, 1, 4 という長さ5の配列をバブルソートでソートしてみましょう．
【1回目の繰り返し：1番目以降のデータが対象】 5 2 3 1 4 | 1 と 4 を比較 5 2 3 1 4 | 3 と 1 を比較 => 交換 5 2 1 3 4 | 2 と 1 を比較 => 交換 5 1 2 3 4 | 5 と 1 を比較 => 交換 1 5 2 3 4 | 1回目のソートが完了 【2回目の繰り返し：2番目以降のデータが対象】 1 5 2 3 4 | 3 と 4 を比較 1 5 2 3 4 | 2 と 3 を比較 1 5 2 3 4 | 5 と 2 を比較 => 交換 1 2 5 3 4 | 2回目のソートが完了 【3回目の繰り返し：3番目以降のデータが対象】 1 2 5 3 4 | 3 と 4 を比較 1 2 5 3 4 | 5 と 3 を比較 => 交換 1 2 3 5 4 | 3回目のソートが完了 【4回目の繰り返し：4番目以降のデータが対象】 1 2 3 5 4 | 5 と 4 を比較 => 交換 1 2 3 4 5 | 4回目のソートが完了（整列完成）
このアルゴリズムをプログラムにして，バブルソートで配列をソートする関数 bsort() を作ってみましょう． bsort() は長さ n の real(8) 型配列 x(1:n) を引数とし， n 個の実数値 x(1), x(2), …, x(n) を値の小さい順（昇順）に並び替えるものとします．
!----------------------------------------------------------------- ! バブルソート !----------------------------------------------------------------- subroutine bsort(n, x) implicit none integer :: n real(8) :: x(1:n) ! local integer :: i, j real(8) :: tmp ! i 番目以降のデータを対象とする do i = 1, n-1 ! x(j), x(j+1) を比較し，必要なら値を入れ替える do j = n-1, i, -1 !***************************************************************** ! この部分を自分で考えてみましょう． !***************************************************************** end do end do return end subroutine bsort !----------------------------------------------------------------- ! チェック用の main 関数 !----------------------------------------------------------------- program main implicit none integer, parameter :: NMAX = 120 real(8) :: x(NMAX) call random_seed() call random_number(x) call bsort(NMAX, x) write(*,'(1F20.18)') x stop end program main
単純ソート (insertion sort)
トランプの整列などで使われる方法です．
- まず2番目の要素に注目し，1番目との大小関係が正しくなるようにする．
- 次に3番目の要素に注目し、最初の2つと見比べて正しい位置に挿入する．
- 次に4番目の要素に注目し、最初の3つと見比べて正しい位置に挿入する．
- 以下，同様の操作を繰り返し，最後の要素を適当な場所に挿入した時点で並び替えが完了する．
この方法を「単純挿入法」といいます． 整列している配列に追加要素を適切な場所に挿入して全体をソートする方法です．
5, 2, 3, 1, 4 という長さ5の配列を単純挿入法でソートすると，次のようになります．
【2番目の要素に注目する】
5 2 3 1 4 | 2 （2番目の要素）に注目する
5 * 3 1 4 | 5 と 2 を比較: 5 を右にずらす
* 5 3 1 4 | 空いたところに 2 を入れる
2 5 3 1 4 | 2 が正しいところに入った
【3番目の要素に注目する】
2 5 3 1 4 | 3 （3番目の要素）に注目する
2 5 * 1 4 | 5 と 3 を比較: 5 を右にずらす
2 * 5 1 4 | 2 と 3 を比較: 2 は動かす必要なし
2 * 5 1 4 | 空いたところに 3 を入れる
2 3 5 1 4 | 3 が正しいところに入った
【4番目の要素に注目する】
2 3 5 1 4 | 1 （4番目の要素）に注目する
2 3 5 * 4 | 5 と 1 を比較: 5 を右にずらす
2 3 * 5 4 | 3 と 1 を比較: 3 を右にずらす
2 * 3 5 4 | 2 と 1 を比較: 2 を右にずらす
* 2 3 5 4 | 空いたところに 1 を入れる
1 2 3 5 4 | 1 が正しいところに入った
【5番目の要素に注目する】
1 2 3 5 4 | 4 （5番目の要素）に注目する
1 2 3 5 * | 5 と 4 を比較: 5 を右にずらす
1 2 3 * 5 | 3 と 4 を比較: 3 は動かす必要なし
| これ以上の比較は不要（先頭3つは既に整列しているので）
| 空いたところに 4 を入れる
1 2 3 4 5 | 4 が正しいところに入った（整列完成）
このアルゴリズムをプログラムにして，単純挿入法で配列をソートする関数 isort() を作ってみましょう． isort() は長さ n の real(8) 型配列 x(1:n) を引数とし， x(1), x(2), …, x(n) を値の小さい順（昇順）に並び替えるものとします．
!----------------------------------------------------------------- ! 単純挿入法 !----------------------------------------------------------------- subroutine isort(n, x) implicit none integer :: n real(8) :: x(1:n) ! local integer :: i, j real(8) :: tmp ! i 番目の要素に注目する do i = 2, n tmp = x(i) ! x(i) の値を保存 !***************************************************************** ! この部分を自分で考えましょう．ヒントは次の通り． ! (1) x(i) と x(i-1), x(i-2), ..., x(1) を順に比べて，x(i) より ! 小さい要素が見つかるまで，要素を1つずつ右にずらす． ! 上書きされても構わないように x(i) の値を tmp に保存しておく． ! (2) 空いた場所に，保存しておいた x(i) の値を入れる． !***************************************************************** end do return end subroutine isort !----------------------------------------------------------------- ! チェック用の main 関数 !----------------------------------------------------------------- program main implicit none integer, parameter :: NMAX = 10 real(8) :: x(NMAX) call random_seed() call random_number(x) call isort(NMAX, x) write(*,'(1F20.18)') x stop end program main
コムソート
コムソート (comb sort) は Stephen Lacey と Richard Box によって1991年4月に開発された新しいソートアルゴリズムです．
- データ数 n を 1.3 で割り，小数点以下を切り捨てた数を間隔 h とする．
- i=1 とする．
- i 番目と i+h 番目を比べ，i+h 番目が小さい場合は入れ替える．
- i=i+1 とし，i+h>n となるまで 3 を繰り返す．
- h がすでに 1 になっている場合は，入れ替えが発生しなくなるまで上の操作を繰り返す．
- h を 1.3 で割り，小数点以下を切り捨てた数を新たに間隔 h として操作を繰り返す．
h=9 または 10 となったとき，強制的に h=11 とすることで高速化したアルゴリズムを Comb sort 11 と呼びます． なぜ h=11 とするとソートが速くなるのでしょうか？ それは，h が 9→6→4→3→2→1 や 10→7→5→3→2→1 と変化するよりも， 11→8→6→4→3→2→1 と変化する方がうまく櫛が梳けるため，だそうです．
コムソートで配列のソートを行う関数 csort() を作ってみましょう． csort() は長さ n の real(8) 型配列 x(1:n) を引数とし， x(1), x(2), …, x(n) を値の小さい順（昇順）に並び替えるものとします．
!----------------------------------------------------------------- ! コムソート !----------------------------------------------------------------- subroutine csort(n, x) implicit none integer :: n real(8) :: x(1:n) ! local integer :: i, h, c real(8) :: tmp ! 初期間隔 ! h には n を 1.3 で割り小数点以下を切り捨てた値が入る． h = n * 10 / 13 do ! 間隔 h の調整 if (h < 1) h = 1 if (h == 9 .OR. h == 10) h = 11 ! Comb sort 11 ! 間隔 h で要素を比較し，必要なら要素を入れ替える． ! c は入れ替えが発生した回数を記憶する． c = 0 do i = 1, n-h !***************************************************************** ! (A) この部分を自分で考えましょう． ! x(i) と x(i+h) を比較する． ! x(i) > x(i+h) なら値を入れ替え，c の値を 1 増やす． !***************************************************************** end do ! h = 1 の場合: c = 0 ならソート終了，c /= 0 ならソートを繰り返す． ! h > 1 の場合: 間隔を縮小しソートを繰り返す． !***************************************************************** ! (B) この部分を自分で考えましょう． !***************************************************************** end do return end subroutine csort !----------------------------------------------------------------- ! チェック用の main 関数 !----------------------------------------------------------------- program main implicit none integer, parameter :: NMAX = 10 real(8) :: x(NMAX) call random_seed() call random_number(x) call csort(NMAX, x) write(*,'(1F20.18)') x stop end program main
レポート課題
ホームディレクトリに report1 というディレクトリを作成し， その中に bsort(), isort(), csort() のソースファイル（ファイル名は bsort.f90, isort.f90, csort.f90 とせよ）を置くこと． 関数が正しく書けているか自動チェックできるようにするため，各ソースファイルにはソート関数だけを記述し，メインプログラムを含めないこと．
次のコマンドを実行しすべて OK! と表示されたら，高木または TA （田中さん）を呼んでチェックしてもらうこと． このチェックを受けないと課題を提出したとは見なされないので注意．
% ~mtkg/report1/check.sh bsort.f90 % ~mtkg/report1/check.sh isort.f90 % ~mtkg/report1/check.sh csort.f90
締め切りは 12/3 (火) の講義終了までとする．
ディレクトリの作成方法
ホームディレクトリに report1 というディレクトリを作成し，誰にでも読めるようにパーミッションを設定する．
% cd # ホームディレクトリに移動 % mkdir report1 # report1 ディレクトリを作成 % chmod 755 report1 # パーミッションを変更
コマンドの使い方はインターネットで調べましょう．
ファイルのコピー方法
ファイルを ~/report1 ディレクトリにコピーし，誰にでも読めるようにパーミッションを設定する．
% cp bsort.f90 ~/report1/ % chmod 644 ~/report1/bsort.f90
課題ができたら
高速なソートアルゴリズムの一種であるヒープソートに挑戦してみましょう．
