クイックソート

説明

quicksort は数列 a = [a_0, ..., a_{n-1}] が与えられたとき，これをソートする．

アルゴリズムは次のとおり．まず適当にピボットを選ぶ．次にピボットより小さい値と大きい値に要素を分類する．そしてそれぞれの集合に対して再帰的にソートを行い，結果を結合する．要素を分割するときに同じ領域を使いまわすことにすると結合操作が不要になり，アルゴリズムはシンプルになる．計算量は，ピボットをランダムに選んだとすると平均的に小さな値の集合と大きな値の集合は同じ程度のサイズとなるため，期待計算量が従う漸化式は T(n) = 2 T(n/2) + O(n) となって，これを解くと T(n) = O(n log n) となる．

クイックソートは不安定なソートである．すなわち，順位が同じ要素の並び順は不定である．若干の工夫によって安定化することもできるが，その場合はマージソートを用いたほうが高速になることが多い．

なお，通常はソーティングには std::sort を使えば十分である．このアルゴリズムを記載したのは，例えば k 番目に小さなの要素を探すアルゴリズムのように，小さい集合と大きな集合に分割して統治するアルゴリズムのテンプレートのためである．

計算量

• 期待計算量の意味で O(n log n)．

ソースコード

void quicksort(vector<int> &a, int l, int r) {
  if (l < r) {
    int p = a[(l+r)/2];
    int i = l-1, j = r+1;
    while (1) {
      while (a[++i] < p);
      while (a[--j] > p);
      if (i >= j) break;
      swap(a[i], a[j]);
    }
    quicksort(a, l, i-1);
    quicksort(a, j+1, r);
  }
}
void quicksort(vector<int> &a) {
  quicksort(a, 0, a.size()-1);
}

Verified