【c++で楽しく実装！】クイックソート

zuka

クイックソートを実装するよ。

本記事では，クイックソートの簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。

本記事の概要

まずは，クイックソートのお気持ちをお伝えしていきます。その次に，クイックソートにおける対象配列の振る舞いを確認します。最後に，実装方法を確認していきます。

お気持ち

クイックソートは分割統治法の一種です。「困難は分割せよ」的なノリです。分割統治法のアイディアは，難しい問題をいくつかの小問題に分割して，それぞれに対して同じ操作を適用することで難しい問題を解こうというものです。

具体的には，ソートの対象配列を軸要素（ピボット）で分割し，その値より小さい要素は軸要素前の配列，大きい要素は軸要素後の配列に格納する操作を再帰的に行います。再帰の終了条件としては，要素数が1以下の配列ができたときです。その領域を確定することで，ソートを実現します。

クイックソートの平均計算量は$O(n\log n)$で，他のソート法と比べて一般的に最も高速だとされていますが，軸要素（ピボット）の選び方によっては最悪計算量が$O(n^2)$になってしまうという特性を持ちます。一方で，軸要素の選び方を少し工夫する（例えば毎回ランダムに選んだり3要素の中央値を取ったりする）だけで最悪計算量を回避することができますので，クイックソートはよく利用されるソートアルゴリズムになります。

zuka

クイックソートは分割統治法。これはキーワードだよ。

振る舞い

クイックソートの振る舞いを確認しましょう。例として，以下のような数列を考えます。

{3, 2, 6, 8, 5, 1, 7, 4}

まずは軸要素を選びます。今回は，対象とする領域の中央インデックスと定義することにしましょう。偶数の場合は，その左側のインデックスとします。最初の軸要素は8になります。8の左側は8より小さい要素で構成されていますので，いじる必要はありません。8の右側の要素を外側から考えていきます。4は8より小さいですので，4と8を入れ替えます。

{3, 2, 6, 4, 5, 1, 7, 8}

zuka

ちなみに，軸要素として最大値が選ばれてしまったため，このケースが最悪計算量を引き起こすパターンの１つに相当するよ。

続いて，8の両側の領域に対して再帰的にクイックソートを適用していきます。しかし，右側の領域は潰されてしまっていますので，左側の領域に注目します。左側の領域において，中央の要素は6になります。そこで，6を軸要素としてクイックソートを適用していきます。6の左側の要素に関しては6より小さく，右側の要素に関して右から調べていくと1が6より小さい要素としてヒットします。そこで，6と1を交換します。

{3, 2, 1, 4, 5, 6, 7, 8}

さて，6の右側の領域と左側の領域に関して注目していきますが，右側の領域はすでにソート済みです。そこで，左側の領域のみに注目していきます。軸要素は1です。1の右側は1より大きな要素で占めていますので，左側の要素を左から操作していくと，3がヒットします。そこで，1と3を交換します。

{1, 2, 3, 4, 5, 6, 7, 8}

これにて，ソートが完了しました。今回は「軸と該当する要素」での交換になりましたが，軸要素の左側で軸要素より大きい要素，右側で軸要素より小さい要素が見つかれば，それらを入れ替えれば効率的ですね。実装では，そのような方針で軸要素の両側の要素を条件に合うように揃えていきます。

実装

入力を以下の形式とします。

N
ソートしたい数列

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)

void quick_sort(int a[], int first, int last){
  int i, j, x, t;

  // 軸要素(ピボット)は要素の中央
  x = a[(first + last) / 2];
  // iを軸要素の左領域のインデックス
  // jを軸要素の右領域のインデックス
  i = first;
  j = last;

  while (true){
    // 軸要素以上になるまで左領域を左端から走査する
    while (a[i] < x) i++;
    // 軸要素以下になるまで右領域を右端から走査する
    while (a[j] > x) j--;
    // もし操作しているインデックスが交差したら終了
    if (i >= j) break;

    // 以下の3行は両側を走査してヒットした要素同士を入れ替える操作
    // 上のwhile文を全て抜けた場合にはヒットした要素が軸要素になっている
    t = a[i];
    a[i] = a[j];
    a[j] = t;

    // 次の要素からまあ捜査を始める
    i++; j--;
  }

  // クイックソートを再帰的に呼び出す
  if (first < i - 1) quick_sort(a, first, i-1);
  if (last > j + 1) quick_sort(a, j + 1, last);
}

// ソート対象を格納する配列。10は適当な長さ。
int A[10];
// ソート対象の長さ
int N;

int main(){
  cin >> N;
  rep(i, N) cin >> A[i];
  
  // firstの初期値は一番左側の0
  // lastの初期値は一番右側のN-1
  quick_sort(A, 0, N-1);

  // ソートされた数列を出力する
  rep(i, N) cout << A[i] << " ";
  cout << endl;
}