クイックソートの基本概念

クイックソートは、分割統治法に基づく効率的なソートアルゴリズムです。これはバブルソートの改良版とも言え、バブルソートのO(n²)の計算量を改善します。クイックソートでは、ある基準値（ピボット）を選び、配列をそれより大きいグループと小さいグループに分割して再帰的に処理します。

問題設定

整数配列を受け取り、クイックソートを使って昇順に並び替えるプログラムを作成します。入力は以下の形式：

• 1行目：整数n（配列の長さ）
• 2行目：n個の整数（1～10⁹）

出力はソート済みの整数列です。

実装例と比較

1. 最初の要素をピボットとする方法

#include <iostream>
using namespace std;

const int MAX = 1e6 + 5;
int arr[MAX];

int divide(int arr[], int left, int right) {
    int pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        if (left < right) swap(arr[left], arr[right++]);
        
        while (left < right && arr[left] <= pivot) left++;
        if (left < right) swap(arr[left], arr[right]);
    }
    return left;
}

void quickSort(int arr[], int left, int right) {
    if (left < right) {
        int pivotIndex = divide(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

2. 中央値をピボットとする方法

// 中央値のインデックスを計算する関数
int findMedian(int arr[], int start, int mid, int end) {
    if (arr[start] <= arr[mid]) {
        if (arr[mid] <= arr[end]) return mid;
        return (arr[start] <= arr[end]) ? end : start;
    } else {
        if (arr[start] <= arr[end]) return start;
        return (arr[mid] <= arr[end]) ? mid : end;
    }
}

int divideMedian(int arr[], int left, int right) {
    int mid = (left + right) / 2;
    int medianIndex = findMedian(arr, left, mid, right);
    swap(arr[left], arr[medianIndex]);
    return divide(arr, left, right); // 前述のdivide関数を再利用
}

3. ランダムな要素をピボットとする方法

#include <cstdlib>

int divideRandom(int arr[], int left, int right) {
    int randomIndex = left + rand() % (right - left + 1);
    swap(arr[left], arr[randomIndex]);
    return divide(arr, left, right); // 前述のdivide関数を再利用
}

計算量の解析

クイックソートのパフォーマンスはピボットの選択に大きく依存します。

• 最良時間計算量： O(n log n) - 各分割で配列がほぼ半分になる場合。
• 最悪時間計算量： O(n²) - 入力が既にソート済みなど、偏った分割が続く場合。
• 空間計算量： 再帰呼び出しの深さに依存します。
  • 最良：O(log n)
  • 最悪：O(n)