効率の良いソートアルゴリズム


前のページのようにちょっとした工夫で比較回数を半分ほどに減らすことが できたが,それでも行数 n の2乗に比例するアルゴリズムということに変わり はない(これを O(n2)のアルゴリズムであると言う).それに対し て,O(n * log n)の効率の良いアルゴリズムがいくつか知られている.

その中で一番簡単なマージソートというアルゴリズムを示す.

 // BufferedReaderなどを使うので,java.io.*を import する.
import java.io.*;
 // Vectorを使うので java.util.* を importする.
import java.util.*;

class SortTest3 {
   // 比較回数を記録するための変数
  static int compareCount=0;
   // s1とs2を比較してs1が辞書式順序で小さいときは負,等しいときは0,大きいときは正の整数を返す
  static int compare(String s1, String s2){
    compareCount++;
    return s1.compareTo(s2);
  }
  // ソート済みの配列 src1とsrc2を合わせて,ソート済みの配列を作る
  static String[] merge(String[] src1, String[] src2){
    int len1=src1.length, len2=src2.length;
     // 合わせた要素を入れる文字列を作る
    String[] dst=new String[len1+len2];
     // 文字列 src1, src2, dstの何番目に注目しているかを示すインデックス(添字)
    int i1=0,i2=0,i3=0;
    for(;;){
      // src1とsrc2から先頭の要素を1つ取る.
      // src1の先頭の方が小さい時は,
      if(compare(src1[i1],src2[i2])<0){
      // src1から1つ要素を取り,dstに加える
      // dst[i3]=src1[i1]; i3++; i1++; と同じ
	dst[i3++]=src1[i1++];
	// src1の要素が残っていない時は,src2の残り部分を dstにコピーして終了する
	if(i1>=len1) {
	  System.arraycopy(src2,i2,dst,i3,len2-i2);
	  break;
	}
      }
      // src2の要素の方が小さいときは
      else{
        // src2から1つ要素を取り,dstに加える
        // dst[i3]=src2[i2]; i3++; i2++; と同じ
	dst[i3++]=src2[i2++];
	// src2の要素が残っていない時は,src1の残り部分を dstにコピーして終了する
	if(i2>=len2) {
	  System.arraycopy(src1,i1,dst,i3,len1-i1);
	  break;
	}
      }
    }
    return dst;
  }
  // linesの内容をソートする
  static void sort(String[] lines){
    int i,j,len=lines.length;
    // 要素数が0,1の場合はソート済みなのでそのまま返す
    if(len<2) return;
    // linesの前の半分,後の半分の入った配列 s1, s2を作る
    int len1=len/2;
    int len2=len-len1;
    String[] s1=new String[len1],s2=new String[len2];
    System.arraycopy(lines,0,s1,0,len1);
    System.arraycopy(lines,len1,s2,0,len2);
    // s1, s2をそれぞれソートする
    sort(s1);
    sort(s2);
    // ソート済みのs1, s2を合わせてソート済みの配列を作る
    String[] sorted=merge(s1,s2);
    // linesにコピーする
    System.arraycopy(sorted,0,lines,0,len);
  }
  //  IOExceptionを catchしていないので,throws IOExceptionをつける.
  public static void main(String args[]) throws IOException{
    // ファイル名と思って BufferedReader
    BufferedReader is=new BufferedReader(new FileReader(args[0]));
    // 何行になるかわからないので,Vectorで記憶しておく
    Vector v=new Vector();
    String s;
    // 1行読み込んでファイルの終端に到達しない間
    while((s=is.readLine())!=null){
      // Vectorの最後に要素を加える
      v.addElement(s);
    }
    // 入力ストリームを閉じる
    is.close();
    // Vectorから配列に変換するために,領域を確保する
    String[] lines=new String[v.size()];
    // Vectorから配列に変換する.
    v.copyInto(lines);
    // ソートする
    sort(lines);
    // ソートした結果を出力する.
    for(int i=0;i< lines.length;i++)
      System.out.println(lines[i]);
    System.err.println("比較回数は "+ compareCount +" 回です");
  }
}
これを 1013.html に対して適応してみると比較回数は 277回となった.59行 程度の小さいプログラムを相手にしていたので,4倍程度のスピードアップに 終わっているが大きなプログラムを相手にすると更に変わるはずである.