C++でクイックソートを実装する - プログラミング原人の進化論

もっとも高速なソートであると言われているクイックソートを実装します。前回実装したパーティションを利用します。最後に問題を解きます。
パーティションの記事はここ↓
programgenjin.hatenablog.com

目標

クイックソートを実装できるようになる。

クイックソート

分割統治法を利用してソートを行います。分割統治法とは、問題を分割して個々の部分問題を解いた後、それらを統合することにより解を得る手法の総称です。
パーティションを再帰的に適用することで次々と配列を分割していきますが、パーティションの性質から、最終的に配列がソートされることが分かります。

アルゴリズム

パーティションアルゴリズムにより配列を２つに分割する。
前後の部分列に対してそれぞれ再帰的にクイックソートを適用する。

パーティションの性質から、クイックソートは安定ではありません。なお、安定なソートとは、同じ値の要素の交換が起こらないソートのことです。安定なソートには、要素が複数の値を持つ時に、ある値を基準にソートした時に他の値の並び順が変わらないという利点があります。
また、計算量は分割の階層が $O(log N)$ 、それぞれの階層でのパーティションの計算量が $O(N)$ であることから、結局クイックソートの計算量は $O(N log N)$ となります。ただし、パーティションが効率よく行われない場合（半分くらいづつが効率が良いと考えられます）は時間がかかり、最悪 $O(N^2)$ の計算量となります。今回は行なっていませんが、パーティションの基準の選び方を工夫しても良いでしょう。

実装してみる

パーティションの実装は次のようになります。

int partition(int A[], int p, int r) {
  int i, j, x, tmp;
  // initialize
  i = p - 1;
  x = A[r];
  for (j =  p; j < r ; j++) {
    if (A[j] <= x) {
      i++;
      // exchange
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  // exchange
  tmp = A[i+1];
  A[i+1] = x;
  A[r] = tmp;

  return i + 1;
}

これを利用して、クイックソートを行う関数を次のように定義します。

void quick_sort(int A[], int p, int r) {
  int q;  // partition分割の基準となる要素のインデックス
  if (p < r) {    
    q = partition(A, p, r);
    quick_sort(A, p, q-1);
    quick_sort(A, q+1, r);
  }
}

問題を解く

Aizu Online Judge のクイックソートに関する問題を解いてみます。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_C

２種類の値があることを考慮して、少し上で定義した関数を修正して用います。カードの絵柄と数字を保持する構造体Cardを定義しておきます。また、安定なソートであるかどうか調べるために、マージソートでソートした結果と比較します。

解答例：

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;

#define MAX 100000
#define INFTY 100001

struct Card {
  char suit;
  int value;
};


void merge(Card A[], int left, int mid, int right) {
  int i, j, k, n1, n2;
  
  n1 = mid - left;
  n2 = right - mid;
  
  Card L[n1+1], R[n2+1];
  for (i = 0; i < n1; i++) L[i] = A[left + i];
  for (i = 0; i < n2; i++) R[i] = A[mid + i];
  L[n1].value = INFTY;
  R[n2].value = INFTY;

  j = 0;
  k = 0;
  for (i = left; i < right; i++) {
    if (L[j].value <= R[k].value) {
      A[i] = L[j];
      j++;
    } else {
      A[i] = R[k];
      k++;
    }
  }  
}

void merge_sort(Card A[], int left, int right) {
  int mid;
  if (left + 1 < right) {    
    mid = (left + right) / 2;
    merge_sort(A, left, mid);
    merge_sort(A, mid, right);
    merge(A, left, mid, right);
  }
}

int partition(Card A[], int p, int r) {
  int i, j;
  Card x, tmp;
  // initialize
  i = p - 1;
  x = A[r];
  for (j =  p; j < r ; j++) {
    if (A[j].value <= x.value) {
      i++;
      // exchange
      tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  // exchange
  tmp = A[i+1];
  A[i+1] = x;
  A[r] = tmp;

  return i + 1;
}

void quick_sort(Card A[], int p, int r) {
  int q;  // partition分割の基準となる要素のインデックス
  if (p < r) {    
    q = partition(A, p, r);
    quick_sort(A, p, q-1);
    quick_sort(A, q+1, r);
  }
}

int main() {
  int i, n;
  string is_stable;
  Card A[MAX], B[MAX];

  cin >> n;
  for (i = 0; i < n; i++) cin >> A[i].suit >> A[i].value;
  for (i = 0; i < n; i++) {
    B[i].suit = A[i].suit;
    B[i].value = A[i].value;
  }      

  quick_sort(A, 0, n-1);
  merge_sort(B, 0, n);

  is_stable = "Stable";
  for (i = 0; i < n; i++) {
    if (A[i].suit != B[i].suit) {
      is_stable = "Not stable";
    }
  }

  cout << is_stable << endl;
  for (i = 0; i < n; i++) cout << A[i].suit << " " << A[i].value << endl;

  return 0;
}