クイックソート


  1. 整列問題

    数や文字を大きさの順に並べ替える処理は基本的であり、よく利用されます。しかし、単純な手法で並べ替えを行うと、多くの無駄な時間を消費してしまいます。ここでは、高速な整列処理としてよく利用されるクイックソート手法を紹介します。
    また、ここでは、処理の理解を助けるため、スレッドを用いて、処理をステップに分解し、各段階での並べ替えの状態を見られるよう工夫したプログラムを紹介します。

  2. 整列の基本（選択法）


    1. 最小値を取り出す

      並べ換えを行う手法で、よく用いられる手法は、最小値を取り出してそれを先頭のデータと交換する方法です。
          　<91, 4, 2, 53, 92, 82, 21, 16, 18, 95, 47, 26, 71, 38, 69, 12, 67,
    99, 35, 94, >
      このデータ列の最小は２で、これを先頭の９１と交換すると、次のようになります。＊は交換した数値を示します。＜　＞は次に処理をする範囲を示します。
          　2, < 4, *91, 53, 92, 82, 21, 16, 18, 95, 47, 26, 71, 38, 69, 12, 67,
    99, 35, 94, >
      次に、<　>の内部で同じ処理を行うと、次のようになります。たまたま、４が最小値のため、自分自身と交換しています。
          　2,* 4, <91, 53, 92, 82, 21, 16, 18, 95, 47, 26, 71, 38, 69, 12, 67,
    99, 35, 94, >
      これで、ようやく、2番目の数まで整列が終わりました。これを続けると、順に整列ができます。
          　 2, 4, 12, 16, 18, 21, 26, <53, 92, 95, 47, *82, 71, 38, 69, 91, 67,
    99, 35, 94, >

    2. 　比較の回数

      データの数をnとして、最初の最小値を探すのにすべての数を調べるため、n回の比較が必要です。つぎは、残りのn-1個の数を調べるためn-1回の比較が必要です。これを繰り返すと、
          　n + (n-1) + (n-2) + . . + 3 + 2 + 1
      の比較が必要です。これは、(n+1)*n / 2 　になります。n=1000のとき、約50万にもなります。

  3. 高速な並べ替え


    1. データを分割する

      クイックソート手法の特長はデータを分割することです。
          　<41, 67, 34, 0, 69, 24, 78, 58, 62, *64, 5, 45, 81, 27, 61, 91, 95,
    42, 27, 36, >
      を次のように、中央の64より、小さな数と大きな数に分割します。
          　<41, 36, 34, 0, 27, 24, 42, 58, 62, 61, 5, 45, 27, ><81, 64,
    91, 95, 78, 69, 67, >
      左<　>は64より小さなグループ、右の<　>は64より大きなグループです。
      　このように分割すると、次は、左と右のグループの内部だけを並べかえれば良いことになります。グループの間の交換は必要ありません。
      　そこで左のグループ
          　<41, 36, 34, 0, 27, 24, *42, 58, 62, 61, 5, 45, 27, >81, 64, 91,
    95, 78, 69, 67,
      を、中央の４２で分割すると、次のように分割出来ます。
          　<41, 36, 34, 0, 27, 24, 27, 5, ><62, 61, 58, 45, 42, >81,
    64, 91, 95, 78, 69, 67,
      さらに左の
          　<41, 36, 34, * 0, 27, 24, 27, 5, >62, 61, 58, 45, 42, 81, 64, 91,
    95, 78, 69, 67,
      を0で分割すると
          　 0, <36, 34, 41, 27, 24, 27, 5, >62, 61, 58, 45, 42, 81, 64, 91,
    95, 78, 69, 67,
      となります。今回は、中央の数が0でグループの最小値のため、0と他のグループに分割されます。左の数は0だけのため、もう、分割は不要です。

    2. 分割の方法
      分割には、簡単な方法があります。まず、左から64より大きな数67を探します。次の右端から、67より小さな数３６をさがし交換します。
          　<41, 67, 34, 0, 69, 24, 78, 58, 62, *64, 5, 45, 81, 27, 61, 91, 95,
    42, 27, 36, >
      の場合、
          　<41, 36, 34, 0, 69, 24, 78, 58, 62, *64, 5, 45, 81, 27, 61, 91, 95,
    42, 27, 67, >
      次に交換をした次の数から同じことを繰り返します。36の右で64より大きな数は69です。67の左で64より小さな数は26です。これを交換します。
          　<41, 36, 34, 0, 27, 24, 78, 58, 62, *64, 5, 45, 81, 27, 61, 91, 95,
    42, 69, 67, >
      となります。これを繰返し、左右からの探索が交差したら終了になるます。

    3. プログラム
      以下が分割プログラムです。leftとrightの間の配列data[]を分割します。分割する値は、　center=data[(left+right)/2];とします。i,jで左右からの探索します。まず、iをcenter以上の数が出るまで増やします。同様に、jをcenter以下の数が出るまで減らし、data[i] と data[j] を交換します。これを、i > j になるまで（　i <= j　の間は）繰り返します。
          center=data[(left+right)/2];//分割する値
    i=left;j=right;
    do{
      while(data[i] < center) i++;
      while(data[j] > center) j--;
      if( i<=j ){
        //TRACE("change %d %d \n",data[i],data[j]);
        w=data[i];data[i]=data[j];data[j]=w;
        i++;j--;
        //m_chg++;
      }
    } while(i<=j);

    4. 再帰呼び出し
      分割が終了したら、左のグループと右のグループに対し、再度分割処理をします。ただし、グループの要素の数が１になったら終了です。
      先の分割プログラムに続けます。jが左の分割グループの右端、iが右の分割グループの左端となりますから、
      if (j>left) QuickSort(left,j);
if(i<right) QuickSort(i,right);
      で、分割処理が出来ます。QuickSort（）の内部で、QuickSort（）を呼び出しますから再帰処理になります。再帰処理については、再帰計算のページを参照してください。

    5. なぜ高速か

      クイックソートが高速な理由は、グループの要素の数が急激に小さくなるからです。単純な方法では、整列が必要なグループの数は、１づつしか減りません。しかし、クイックソートでは、平均的に半分程度に分割されます。もし、毎回、半分になるとすると、m回分割すると、グループの数は、n / 2mになります。グループの数が1になれば終了です。n / 2m が1なる m は log2n です。従って、分割の回数は、log2nとなります。
      　1回の分割に必要な比較回数は n ですから、n*log2n が、全比較回数となります。n が1000の場合、
      log21000 は約10ですから、比較回数は10,000 となります。これは、単純ソートの50万と比較すると、1/50です。

      1. なぜ中央値で分割するか
        ここでは、二つのグループに分割するとき、中央にあるデータdata[(left+right)/2]を利用しました。理想は、中央の位置ではなく、中央の値を持つデータですが、中央の値を求めると整列すると同様の手間がかかってしまいます。中央でなく、区間の先頭や最後のデータでも良いのですが、このばあい、最初からソートされているデータを処理すると、最悪のケースになってしまいます。

      2. 比較回数と交換回数
        整列では、データの比較と交換が基本的な処理になります。データの比較回数は、単純ソートでは　(n+1)*n / 2、クイックソートでは　n*log2n　となります。交換回数は、単純ソートではn、クイックソートでは　比較回数　の半分程度となります。

    6. 再帰を使わない方法
      再帰呼び出しが利用できない場合や、利用したくない場合はスタックを利用します。
      　再帰呼び出しを行う代わりに、(left,j);および、(i,right);の範囲をスタックに保存します。クイックソートでは、このスタックより分割する範囲を取り出し、処理後に分割された範囲をスタックに保存します。
      　この方法は、プロジェクトのステップ処理で利用しています。

  4. プロジェクト


    1. 機能

      データ生成ボタンで、乱数を利用してデータを生成し、QuickSortと単純sortボタンは、整列処理を行い結果を表示します。step開始ボタンは、ステップ実行の前処理を行い、stepボタンで、整列処理をステップに分割して実行します。また、上部の二つのエディットボックスでステップ処理での比較回数と交換回数を表示します。

    2. スレッドの利用

      　途中経過を表示するため、step ボタンを押す毎に、分割処理をしたいのですが、単に sleep を行うと、ボタンまで無効になってしまいます。そこで、処理部分を　スレッド とし、スレッドの同期機能を利用します。スレッドで
      　wait() を行うと、別のスレッドから notify() されるまで、wait 状態を続けます。
      ソート処理をスレッドで行い、分割処理が終了したら wait() します。このとき、アプレット本体は実行を続けていますから ボタンは有効です。
      　step ボタンで、分割処理を行うスレッドに notify() を送ります。これで、スレッドは処理を再開できます。なお、同期処理を行う関数には、synchronized を付記する必要があります。

    3. レイアウト

      実行前と後の結果を表示する　textfield　を2個配置します。処理開始ボタンと、step実行ボタンとを配置します。
      execボタンを押すと、乱数でデータを生成し、最初のデータを上段に表示します。stepボタンを押すと、分割を行う毎に一時停止し、新たに作成した分割範囲を下段に　<　>　で表示します。
      終了すると、stepボタンは無効になります。途中で終了するには、stopボタンを押し、一回stepボタンを押します。これで、stopボタンがexecに戻り、再度実行が可能です。


    4. Applet1クラス

      1. exec_actionPerformed
        スレッドを拡張したprocクラスを生成し、procスレッドでクイックソートを開始します。execボタンのラベルはstopに変更し、stepボタンを有効にします。aliveはスレッドの実行中trueになります。スレッド実行中にこのボタンを押すと、スレッドの停止フラグをセットします。
          void exec_actionPerformed(ActionEvent e) {
    if(!alive){
      proc1=new proc(this);
      proc1.start();
      alive=true;
      exec.setLabel("stop");
      stepButton.setEnabled(true);
    }
    else{
      proc1.stopproc();
    }
  }

      2. stepButton_actionPerformed
        procクラスのstep()を実行し、次のステップを実行します。

    5. procクラス


      1. 拡張
        一時停止を行うため、Threadクラスを拡張したクラスを作成します。

      2. run()
        スレッドを実行します。乱数でデータを生成し、ソートを開始します。

      3. QuickSort(int left,int right)
        再帰呼び出しでクイックソートを実行します。再帰呼び出しの前に、分割した配列を表示し、waitButton()で一時停止します。

      4. printdata(int data[],int left,int j,int i,int right)
        現在の配列の状態を表示します。分割範囲を受け取り、分割範囲を<　>で表示します。

      5. waitButton()
        　ステップボタンが押されるまでスレッドを一時停止します。wait()を利用するため、synchronized　が必要です。
         synchronized  public void waitButton(){
      try{
          wait();
        }catch( InterruptedException e){}
  }

      6. step()
        　アプレットのステップボタンで呼び出されます。スレッドの一時停止を解除します。notify()を利用するため、synchronized　が必要です。
          synchronized public void step(){
    notify();
  }

    6. ダウンロード


      このプログラムのソースは、ここにからダウンロードできます。
      　Applet1.java proc.java

      このプロジェクト（Jbuilder）をダウンロードできます。次の行をクリックして、jqicksort.exeファイルを適当なフォルダに保存します。
      　ダウンロード開始

      このファイルは自己解凍型の圧縮ファイルです。このファイルを実行すると指定したフォルダに必要なファイルが生成されます。