100個の要素をクイックソートで並べ替えるC++プログラムの解説

クイックソートは、リストを2つの部分に分割することで並べ替えを行うソート手法です。最初にパーティションアルゴリズムによってピボット要素を選択します。ピボットの左側にはピボットより小さい値が、右側にはピボットより大きい値が配置されます。パーティション分割が完了した後、分割されたそれぞれのリストに対して同じ手順を再帰的に適用していきます。

本記事では、約100要素という比較的大きな配列をソートする例を扱います。まず連続した数値を用意し、それをランダムな順序にシャッフルして未ソート状態を作り出します。その後、クイックソートを使って配列を並べ替えます。

クイックソートの計算量

• 時間計算量 − 最良ケースおよび平均ケースで O(n log n)、最悪ケースで O(n²)

• 空間計算量 − O(log n)

入力 − 未ソートのリスト: 90 45 22 11 22 50
出力 − ソート後の配列: 11 22 22 45 50 90

アルゴリズム

partition(array, lower, upper)

入力 − データセットの配列、下限境界、上限境界

出力 − 正しい位置に配置されたピボット

Begin
    pivot := array[upper]
    i := lower – 1
    for j in range lower to higher, do
        if array[j] < pivot, then
            exchange the values of array[i] and array[j]
            i := i + 1
    done
    exchange the values of array[upper] and array[i + 1]
    return i + 1
End

quickSort(array, left, right)

入力 − データの配列、および配列の下限と上限

出力 − ソート済みの配列

Begin
    if lower < right then
    q = partition(array, left, right).
    quickSort(array, left, q-1)
    quickSort(array, q+1, right)
End

サンプルコード

#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) { //配列の要素をランダムな位置にシャッフルする関数
    srand(time(NULL));
    for (int i = MAX - 1; i > 0; i--) {
        int j = rand()%(i + 1);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
int partion(int arr[], int p, int r) {
    int pivot = arr[r]; //最後の要素をピボットとする
    int i = p - 1;
    for (int j = p; j < r; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[r]);
    return i + 1;
}
void quick_sort(int arr[], int p, int q) { //リストを再帰的にソートする
    int j;
    if (p < q) {
        j = partion(arr, p, q);
        quick_sort(arr, p, j - 1);
        quick_sort(arr, j + 1, q);
    }
}
int main() {
    int i;
    int arr[MAX];
    for (i = 0;i < MAX;i++)
    arr[i] = i + 1;
    random_shuffle(arr); //配列をランダム化する
    quick_sort(arr, 0, MAX-1); //配列の要素をソートする
    for (i = 0; i < MAX;i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

実行結果

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

このプログラムでは、まず1から100までの連続した数値で配列を初期化し、Fisher–Yates法に基づくシャッフル関数で要素をランダムに並べ替えています。その後、パーティション関数で最後の要素をピボットとして選び、ピボットより小さい要素を左側に集める処理を繰り返しながら、quick_sort関数が再帰的に左右の部分配列をソートしていきます。最終的に、シャッフルされた100個の要素が昇順に正しく並べ替えられて出力されます。