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

誰もが思いつく簡単なソートアルゴリズムは以下のようなものだろう．

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-1
Σ k = n * (n-1) /2
k=1

ちょっとした工夫で，比較回数を減らすことができる．以下のプログラムは， ランダムなファイルに対しては 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 +" 回です");
  }
}