QuickSort.java



/** ソートのアルゴリズム(その3 クイックソート) */
public class QuickSort {

  /** 確認用のサンプルデータ */
    private static int[] test
                          = { 10, 75, 24, 32, 98,
                              72, 88, 43, 60, 35,
                              54, 62,  2, 12, 82,
                            };

  /** 作業領域用データ */
    private static int[] tmp = null;

  /** 処理の開始のメソッド(確認用) */
    public static void main( String[] argv ) {

   //ソートの作業
        sort( test, 0, test.length-1 );

   //ソートの結果の確認
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }
    }

  /** 与えられた範囲の値を2グループに分け、
      自分自身の仕事を再帰的に呼び出す */
    public static void sort( int[] array, int min, int max ) {

   //数が少ない時はバブルソートで処理する
        if( ( max - min ) < 5 ) {
            bsort( array, min, max ); 
            return;
        }

   //作業領域の確保(最初の呼び出しの時のみ)
        if( tmp == null )
            tmp = new int[ array.length ];

   //平均値より大きいグループと小さいグループに分ける
        float m = average( array, min, max );
        int largeCount=0;
        int smallCount=0;
        for( int i=min; i<=max; i++ ) {
           if( array[i] > m ) {
              tmp[ min+largeCount ] = array[i];
              largeCount++;
           }
           else {
              tmp[ max-smallCount ] = array[i];
              smallCount++;
           }
        }
        for( int i=min; i<=max; i++ ) {
           array[i] = tmp[i];
        }

   //それぞれのグループに対して同じことを繰り返す
        sort( array, min, min+largeCount-1 );
        sort( array, max-smallCount+1, max );
    }

  /** バブルソートで並び変えるメソッド */
    private static void bsort( int[] array, int min, int max ) {

        for( int i=min; i<max; i++ ) {
           for( int j=min; j<max-(i-min); j++ ) {
              if( array[j] < array[j+1] ) {
                  int tmp = array[j];
                  array[j] = array[j+1];
                  array[j+1] = tmp;
              }
           }
        }
    }

  /** 与えられた範囲の値の平均値を求めるメソッド */
    public static float average( int[] array, int min, int max ) {

        float sum = 0.0f;
        for( int i=min; i<=max; i++ ) {
            sum += array[i];
        }
        return sum/( max - min + 1);
    }
}