---

クイックソート

---

N個のデータが，配列 a[0]〜 a[N-1]に格納されているとする．

クイックソート：

1. データが1個の場合は，並べ替えの必要がないので処理を終える
   データが複数の場合は，以下の処理を行う
   1. ピボットを適当に選ぶ
   2. ピボットよりも小さいデータが左に， 大きいデータが右にくるようデータを入れ換える
   3. ピボットよりも小さい左側をソートする
   4. ピボットよりも大きい右側をソートする

詳細化 ：

配列a[0], a[1], ... a[N-1]の from 番目から to 番目までの範囲をソートする関数を

      quick_sort(int a[], int from, int to)

quick_sort内での処理：

      if(from < to) {
          ピボットを定める( pivot ← a[(from+to)/2])
          ピボットよりも小さいデータが左に，大きいデータが右にくるようデータを入れ換える
          左側をソートする
          右側をソートする
      }

• ピボットよりも小さいデータが左に，大きいデータが右にくるようデータを入れ換える :
  • 準備

    	   left ← from  (左端)
               right ← to   (右端)
    

  • left から右に向かって pivot より大きいデータを探す

               while( a[left] < pivot ) left++;
    

  • right から右に向かって pivot より小さいデータを探す

               while( a[right] > pivot ) right--;
    

  • a[left]とa[right]を交換する
  • 範囲を狭めて，交換するデータを探す

               left ← left+1;
               right ← right-1;
    

  • 以上を探す範囲がなくなるまで繰り返す

               do {
                    ...
               } while( left <= right );
    

    処理の具体化:

                  left = from;
                  right = to;
                  do {
                     while( a[left] < pivot ) left++;
                     while( a[right] > pivot ) right--;
                     a[left]とa[right]の値を交換する;
                     left++;
                     right--;
                  } while( left <= right );
    

  • 左側をソートする

               quick_sort(a, from, right);
    

  • 右側をソートする

               quick_sort(a, left, to);