クイックソート

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

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

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

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

アルゴリズム

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

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

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 < 11; ++i)
    {
        printf("%u ", list[i]);
    }

    return EXIT_SUCCESS;
}

// Just a helper to have a cleaner interface
void quick_sort(uint32_t *arr, size_t size)
{
    // Note: here we are passing the high bound as the size - 1,
    // so in here we are having an inclusive range
    // this is important because it makes the algorithm slightly simpler
    // and it requires less -1's which usually causes a lot of off-by one mistakes
    _quick_sort(arr, 0, size - 1);
}

size_t partition(uint32_t *arr, size_t low, size_t high)
{
    // Partition is the operation that puts all the elements smaller than the pivot
    // We are picking the last element as the pivot always,
    // I guess we could be more clever and pick a random element
    // or the median of the first, middle and last elements
    // but this is just a simple example
    size_t pivot_index = high;
    uint32_t pivot = arr[pivot_index];

    // This is going to be the index of the pivot at the end
    // of the loop
    size_t i = low;
    for (size_t j = low; j <= high; ++j)
    {
        // If the current element is less than the pivot,
        // we swap it with the element at index i
        // and increment i,
        // doing this we will know exacyly where the pivot
        // should be placed after the iteration is done
        // because all the elements of index < i are less than the pivot
        // and all the elements of index > i are greater than the pivot
        // so we just need to swap the pivot with the element at index i
        if (arr[j] < pivot)
        {
            uint32_t temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;

            ++i;
        }
    }

    // putting the pivot at the right spot, remember, it could've been anywhere
    arr[pivot_index] = arr[i];
    arr[i] = pivot;

    return i;
}

void _quick_sort(uint32_t *arr, size_t low, size_t high)
{
    // The main idea of this function, is to use a window, that has the bounds
    // [low, high] inclusive, so if the window has length 0, low = high
    // it means we reached our base case, and the list is already sorted
    // since an array without elements is always going to be sorted
    // I guess
    if (low >= 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 になります。

以上がクイックソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。