【ソート】クイックソート

〇、思想#

分治

一、步骤#

配列の中から基準 base を選び、元の配列を【base より小さい】- base -【base より大きい】に分ける
【base より小さい】、【base より大きい】の 2 つの配列に対してそれぞれステップ 1、2 を繰り返し、ソートが完了するまで続ける

快速排序

二、実装#

void my_qsort(short *arr, int start, int end)
{
    if (start >= end) {
        return;
    }

    int i = start;
    int j = end;
    int base = arr[start];
    
    while (i < j) {
        while (arr[j] >= base && i < j) {
            j--;
        }
        while (arr[i] <= base && i < j) {
            i++;
        }
        if (i < j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    arr[start] = arr[i];
    arr[i] = base;

    my_qsort(arr, start, i - 1);
    my_qsort(arr, j + 1, end);
}

三、性能分析#

最悪の場合#

毎回選択する要素 base がソート対象の最大 / 最小要素である場合、配列は毎回ソート後に 1 つの要素の位置が確定し、時間がかかります：$\theta (n)$、その後、n-1 個の要素と 0 個の要素の配列に対してクイックソートを再帰的に行います。実行時間は：$T (n) = T (n-1)+T (0)+\theta (n)$
得られる時間計算量は：$O (n^2)$

最良の場合#

毎回選択する要素が配列の中央の要素である場合、配列は毎回ソート後に 1 つの要素の位置が確定し、時間がかかります：$\theta (n)$、その後、2 つの n/2 の要素に対してクイックソートを再帰的に行います。実行時間は $T (n) = 2T (n/2)+\theta (n)$
得られる時間計算量は：$O (nlogn)$

平均の場合#

クイックソートの平均実行時間は最良の場合に近く、すなわち $O (nlogn)$ です。

四、最適化#

クイックソートにおける基準 base の選択は性能に直接影響します。そのため、ランダム化選択を加えてクイックソートを最適化できます。
小さな配列のソートには他の方法を使用できます。
再帰ではなく反復を使用します。

Done！

この文は Mix Space によって xLog に同期更新されました
元のリンクは https://www.vikifish.com/posts/algo/qsort