データをソート(並べ替え)することは、 さまざまな場面で必要となるため、 その方法については多くの提案がなされてきました。 ここでは代表的なアルゴリズムのうち特に3つを取り上げ、 それらの考え方と特徴を学びます。
今回は教科書「明解 Javaによるアルゴリズムとデータ構造」の第6章(p.182-)を参照します。 この書籍に掲載されているサンプルプログラムは著者の後援会のサイトからダウンロードできますが、 そのサイトに掲載されているものは文字コードが Shift JIS となっています。 これは Linux 環境では不便なため、UTF-8 に変換したものを以下に置いておきます。
単純交換ソート (バブルソート)は、 隣り合う2つの要素を比較し、 必要に応じて入れ替えることを繰り返すことにより 全体を並び替えるソートアルゴリズムです。 効率は良くないものの、単純なアルゴリズムとして有名です。
「明解 Javaによるアルゴリズムとデータ構造」のサンプルプログラムは、 キーボードからデータを入力するようになっています。 そのために java.util パッケージの Scanner クラスを使っています。
// 標準入力 System.in から読み込む scanner オブジェクトを生成
Scanner scanner = new Scanner(System.in);
// 例: 整数値の読み取り
int i = scanner.nextInt();
// 例: 文字列の読み取り [次の区切り(標準では空白)まで]
String s = scanner.next();
// 例: 文字列の読み取り [行末まで]
String s = scanner.nextLine();
上記の例では標準入力 System.in から読み込んでいますが、 InputStream であればファイルでも何でも読み込むことができます。 なお、標準入力から読み込むようにしておけば、 リダイレクトによりファイルを読み込ませることも可能です。
以下のデータファイルは、参考書のサンプルプログラムの入力とすることを想定したものです。 1行目が要素の個数(65535)、それ以降の行が 0 - 10,000 の範囲で発生させた乱数です。
$ java クラス名など < sorted.txt
実行時間を比較してみましょう。
long start = System.currentTimeMillis();
// ここに実行時間を計測する処理
long stop = System.currentTimeMillis();
System.out.println((stop - start) + " [ミリ秒]");
マージソートは、2分割したリストをそれぞれソートしマージ(併合)することを繰り返すアルゴリズムです。 安定なアルゴリズムであり、 Java のクラスライブラリのメソッド Collections.sort でも採用されています。
クイックソートはその名のとおり、極めて高速な部類のソートアルゴリズムです。 非常によく利用されています。
リストをある値(枢軸)と比較した大小で分割することを再帰的に繰り返します。 メソッドの再帰呼び出しを用いるのが一般的です。
教科書では pp.211-217 において非再帰的クイックソートを扱っていますが、この授業内では扱いません。再帰を用いない場合にはスタックを利用することになりますので、その利用法に興味がある人は読んでみましょう。