Algorithms/Sorting/Quick Sort

Quick Sort

クイックソート

Outline

クイックソートは分割統治法(Divide and Conquer Approach?)に基づく高速なアルゴリズムである.1960年にC. A. R. Hoareによって発明された.クイックソートは色々なところで利用されているアルゴリズムである.その理由として、

• 余分な記憶領域を必要としない
• 実装が容易である
• 平均的に&mimetex(\Theta(n \log_{2} n));で実行出来る

というものが挙げられる.
この中で三番目の特徴に関して、確かにクイックソートの平均実行時間は
&mimetex( \Theta(n \log_{2} n) );であるが、
最悪の場合の実行時間は&mimetex( \Theta(n^2));となる.
加えて、クイックソートは再帰関数により実装することが多いので
関数のオーバヘッドの分も考慮に入れなければならない.
ICPCでは常に最悪の場合を考えなくてはならないので、
大量のデータをソートする必要があるときには、
クイックソートを使うべきではない.
しかし、多くのソフトウェアでのソートは
クイックソートで実装されており、
またクイックソートはアルゴリズムの解析という側面からは
非常に興味深く、構造が単純なので分割統治法を直感的に理解するのに役立つ.

クイックソートでは、枢軸(pivot)となる基準値を選び
その基準値より小さいデータと大きいデータを分けることで
ソートを進行していく.
以下のプログラムではpivotとしてデータ列のちょうど真ん中の値を採用しているが、
これ以外でも上手くいく.

Program

サイズnの配列dataに対してクイックソートを行う関数.

void quick_sort(int data[], int l, int r) {
  int left = l, right = r;
  int p = data[(l + r) / 2];  // pivot

  if(l < r) {
   while(true) {
      while(data[left] < p) {
        left++;
      }

      while(data[right] > p) {
        right--;
      }

      if(left < right) {
        swap(data[left], data[right]);
      } else {
        break;
      }
    }

    quick_sort(data, l, right);
    quick_sort(data, right + 1, r);
  }
}

Consideration

Average Case Running Time : &mimetex(\Theta(n \log_{2} n));

Worst Case Running Time : &mimetex(\Theta(n^2));