クイックソートアルゴリズム

クイック ソートは、標準ライブラリ内の複数のプログラミング言語で実装されているため、最も有名なソート アルゴリズムの 1 つです。なぜこのアルゴリズムがこれほど使用されるのでしょうか??
クイック ソート アルゴリズムは、その速度により、時間計算量が O(n * log n) の最も高速なソート アルゴリズムの 1 つです。ここで、n は配列のサイズ、log は 2 を底とする対数です。

どのように機能するのでしょうか?

クイック ソート アルゴリズムを理解するために必要な主な概念は、分割統治戦略です。
分割統治戦略は有名な軍事用語で、かつては大国を征服するには、まず国内紛争や内戦によってまず国を分裂させ、その後、分裂している間に国全体を掃討するという意味でした。忙しい。
わかりましたが、この概念はコンピューター サイエンスにどのように変換されるのでしょうか?アルゴリズムにおける分割統治とは、より小さな問題を解決することで問題を解決することを意味します。これは数学的帰納法の概念にかなり似ています。つまり、f(1) を確立し、次に f(n) を確立し、次に、 f(n - 1) が機能することを示します。これにより、概念を証明できます。
問題の分割統治も同様に機能します。まず、基本ケースと呼ばれる最も単純な問題を解決します。次に、再帰ケースを定式化し、最後に問題を最も単純な問題に分割します。なぜなら私たちは解決方法を知っているからです。

アルゴリズム

C での実装を示し、それからこれがどのように機能するかを 1 行ずつ説明します。これは、かなり複雑なアイデアであるためです。

#include 
#include 
#include 

void _quick_sort(uint32_t *arr, size_t low, size_t high);
void quick_sort(uint32_t *arr, size_t size);

int32_t main(void)
{
    uint32_t list[] = {1, 4, 5, 10, 2, 9, 17, 100, 4, 2, 1000};

    // 11 is the number of elements list has
    // this is really usefull, because whenever we pass an array to a function, it decays as a pointer
    // due to this, if the function is in another translation layer it won't be able to know, so it can do the 
    // sizeof(list) / sizeof(list[1]) trick
    quick_sort(list, 11);

    for (size_t i = 0; i  i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] = high)
    {
        return;
    }

    // The pivot index is the index of the pivot element after partitioning,
    // so it means that the list is weakly sorted around the pivot,
    // (i.e. all elements to the left of the pivot are less than the pivot)
    // and all elements to the right are greater then
    size_t pivot_index = partition(arr, low, high);

    // Here we have a cool implementation detail
    // since pivot_index is a size_t, it is unsigned
    // and if we subtract 1 from an unsigned 0,
    // we get undefined behavior
    // This would happen, if the last element should be the first
    // in this case, no sorting is necessary, since there is nothing
    // before it
    if (pivot_index > 0)
    {
        // Sorting the left hand window
        // they have the bounds, [low, pivot_index - 1]
        // the -1 is so it is inclusive
        // because we now know the pivot is in the right spot
        _quick_sort(arr, low, pivot_index - 1);
    }

    // Same thing with before, now, we are sorting the right side of the window
    _quick_sort(arr, pivot_index   1, high);
}

したがって、アルゴリズムの主な考え方は非常に単純です。配列パーティションのリストを 2 つの部分に分割します。1 つはすべての要素がピボットより小さい部分で、もう 1 つはすべての要素がピボットより大きい部分です。
次に、パーツに要素がなくなるまで、このアルゴリズムをパーツ自体に再帰的に適用します。この場合、正しくソートされていることを確認できます。

クイックソートアルゴリズムでのピボットの選択には重要なニュアンスがあります。間違ったピボットを選択すると、配列が 2 つの配列に分割されるたびに、最終的に小さな配列になるため、非常に複雑になります。配列の場合、この場合、n 個の再帰呼び出しがあり、n 個の要素をたどる必要があるため、クイックソートでは O(n*n) という最悪のシナリオが発生し、これはひどいことになるため、次の場合には注意する必要があります。ピボットを選択する場合、1 つの良いアプローチは、乱数を選択することです。そうすることで、平均的なケースでは分割されるため、O(n * log n), log n である中間のケースが確実に得られます。配列を、最初の配列の半分の要素を持つ 2 つの配列に分割します。すべての要素を調べる必要があるため、因数は n.