簡単なソートアルゴリズム


誰もが思いつく簡単なソートアルゴリズムは以下のようなものだろう.
  1. 一番小さな要素を見つける.
  2. それを除いた後で,次に小さい要素を見つける
  3. それを繰り返す.
このアルゴリズムに基づくプログラムが以下のものである.
 // BufferedReaderなどを使うので,java.io.*を import する.
import java.io.*;
 // Vectorを使うので java.util.* を importする.
import java.util.*;

class SortTest1 {
   // 比較回数を記録するための変数
  static int compareCount=0;
   // s1とs2を比較してs1が辞書式順序で小さいときは負,等しいときは0,大きいときは正の整数を返す
  static int compare(String s1, String s2){
    compareCount++;
    return s1.compareTo(s2);
  }
  // このメソッドの中で linesの並び替えをおこなう.
  // 最小値を元にしたソートu
  static void sort(String[] lines){
    int i,j,minJ,len=lines.length;
    String minStr;
    for(i=0;i< len-1;i++){
      // 最小値が仮にlines配列の i番目にあると仮定する.
      minStr=lines[i];
      minJ=i;
      // それ以降のもので, minStrよりも小さいものが見つかったら,それを最小値と仮定する.
      for(j=i+1;j< len;j++){
	if(compare(minStr,lines[j])>0){
	  minStr=lines[j];
	  minJ=j;
	}
      }
      // 最小値が minStrでそれが minJ番目に入っていると分かったので
      //  iとminJの中身を交換する
      lines[minJ]=lines[i];
      lines[i]=minStr;
    }
  }
  //  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 +" 回です");
  }
}
このプログラムは容易にわかるように,n行のファイルのソートに際して
n-1
Σ k = n * (n-1) /2
k=1
回の比較を必要とする.そのため,59行の長さの 1013.htmlをファイルに落としてソートすると 1711回の比較が生ずる.

ちょっとした工夫で,比較回数を減らすことができる.以下のプログラムは, ランダムなファイルに対しては n*n/4 程度の比較回数,最悪の場合n*n/2程度 の比較回数となるプログラムである(挿入ソートと呼ばれる).

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

class SortTest2 {
    // このメソッドの中で linesの並び替えをおこなう.
  static int compareCount=0;
  static int compare(String s1, String s2){
    compareCount++;
    return s1.compareTo(s2);
  }
   // 挿入ソート
  static void sort(String[] lines){
    int i,j,len=lines.length;
    String s;
     //  0からi-1までがソート済みの時に,lines[i]を適切なところに挿入する
    for(i=1;i< len;i++){
       // 挿入すべき行
      s=lines[i];
      for(j=i-1;j >=0;j--){
        // lines[j]がsよりも小さくなる jを求める.
	if(compare(s,lines[j])>0){
	  break;
	}
        // 右に1つ要素をずらす.
	lines[j+1]=lines[j];
      }
       // sを挿入する
      lines[j+1]=s;
    }
  }
  //  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に対しては,999回の比較回数となる.
次に進む