ソート
バブルソートはn個のデータの系列(a1, a2,…, an)を左から右へ走査しながら隣り合う2つの数値を比較し、それらが小さい順になっていなければそれら2つの数値を互いに入れ替えていく。この入れ替えがなくなるまで走査を繰り返すことでソートが行われる。
27 31 15 7 11 9 |
このアルゴリズムを実現するには、入力されたn個の数列を格納する配列をまず用意し、隣り合う配列要素を順に比較し、入れ替えを行っていく。この操作を、配列の最初から最後まで比較が起こらなくなるまで続ければよい。具体的なプログラムの流れ図は以下のようになる。(画像をクリックすると拡大）
ソート済みの2つの系列α= (a1, a2,…, ap)とβ= (b1, b2,…, bq)を合成して一つのソートされた系列γを得る処理をマージという。この処理はαとβの長さの和p+qに比例する時間で実行できる。αとβはそれぞれすでにソートされているので、各々の先頭どうしを比べ、小さい方をそれを含む系列から取り出す。これを2つの系列に対し繰り返し、途中で比べる相手がなくなった時には、要素の残っている系列から順に取り出すことにする。このようにして、各要素を取り出された順に並べれば、ソートされた系列γが得られる。
n個のデータの系列α = (a1, a2,…, an)をソートする場合、まずデータの系列を同じ大きさの2つの系列α1 = (a1, a2,…, ah)、α2 = (ah+1, a h+2,…, an)に分割する。ここで、h = n / 2である。次に、α1とα2をそれぞれソートして得られる2つの系列をマージすれば、αをソートしたことになる。
α1とα2をソートするのはこれと同じ操作を再帰的に行えばよい。このように、分割とマージを繰り返してソートを行うのがマージソートである。
18 37 21 14 7 12 19 6 まず、系列の分割が再帰的に行われる。 (18 37 21 14)( 7
12 19 6) 次に、隣り合う系列どうしのマージが繰り返される。 (18 37)(14 21)( 7
12)( 6 19) |
このアルゴリズムは系列を分割する部分と、マージを行う部分に分けられる。分割を行う部分は関数の再起呼び出しで実現できる。
関数の再起呼び出しは、ある関数の中からそれ自身の関数を呼び出す。以下のサンプルプログラムは、文字列の1次元配列を再帰的に半分に分割し表示するプログラムである。ここでは、半分に分割する関数を再帰的に呼び出している。文字列の長さが1よりも大きな場合にだけ分割を行うことに注意すること。
#include<stdio.h> printf(" "); |
マージの部分は以下のフローチャートのようにして実現できる。(画像をクリックすると拡大）
プログラム中で用いるprintf関数やscanf関数は、標準入出力として、printf関数なら画面に出力し、scanf関数ならキーボードからの入力となる。
これを、ファイルに出力したり、ファイルの内容を入力したりできる。以下の例は、実行ファイルmergeの出力をファイルresultに出力する。出力結果はテキストファイルとして保存され、ファイルは自動的に作成される。
% merge > result |
このように、実行ファイルの後の">"に続けてファイル名を指定すると、printf関数で出力される結果はファイルの中に出力される。同様に、"<"に続けてファイル名を指定すると、テキストファイルをscanf関数などへの入力として用いることができる。以下の例は、数値の入っているテキストファイルdata1000をプログラムmergeに入力する方法である。
% merge < data1000 |
プログラムの実行時間を計るにはtimeコマンドを用いる。実行は以下のように行う。
/usr/bin/time 実行ファイル名 例） |
出力される結果はrealが実際にプログラムを呼び出してから終了するまでにかかった時間を表わすので、これを見ればよい。