빠른 정렬 알고리즘

빠른 정렬은 표준 라이브러리 내부의 여러 프로그래밍 언어로 구현되기 때문에 가장 유명한 정렬 알고리즘 중 하나입니다. 이 알고리즘이 왜 그렇게 사용됩니까??
빠른 정렬 알고리즘은 속도 때문에 O(n * log n)의 시간 복잡도를 갖는 가장 빠른 정렬 알고리즘 중 하나입니다. 여기서 n은 배열의 크기이고 log는 로그 밑수 2입니다.

어떻게 작동하나요?

퀵 정렬 알고리즘을 이해하는 데 필요한 주요 개념은 분할 정복 전략입니다.
분할 정복 전략은 유명한 군사 용어로, 큰 나라를 정복하려면 먼저 국가를 만들어야 하고, 종종 내부 갈등이나 내전으로 분열된 다음, 국가 전체를 휩쓸어야 한다는 의미였습니다. 바쁘다.
좋습니다. 그런데 이 개념이 컴퓨터 과학으로 어떻게 해석되나요? 알고리즘에서 분할 및 정복은 더 작은 문제를 해결하여 문제를 해결한다는 것을 의미합니다. 이는 수학적 귀납법의 개념과 다소 유사합니다. 여기서 f(1)을 설정한 다음 f(n)을 설정하고 다음을 수행합니다. 우리는 f(n - 1)이 작동한다는 것을 보여줍니다. 이를 통해 개념을 증명할 수 있습니다.
분할 및 정복 문제는 동일한 방식으로 작동합니다. 먼저 기본 사례라고 불리는 가장 간단한 문제를 해결한 다음 재귀 사례를 공식화하고 마지막으로 문제를 가장 간단한 문제로 분류합니다. 왜냐하면 우리는 해결 방법을 알고 있기 때문입니다.

알고리즘

C로 구현한 것을 보여주고 이것이 어떻게 작동하는지 한 줄씩 설명하겠습니다. 꽤 복잡한 아이디어이기 때문입니다.

#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);
}

따라서 알고리즘의 주요 아이디어는 다소 간단합니다. 배열 분할을 목록을 두 부분으로 나누는 것입니다. 하나는 모든 요소가 피벗보다 작고 다른 하나는 모든 요소가 피벗보다 큽니다.
그런 다음 부품에 요소가 없을 때까지 부품 자체에 이 알고리즘을 재귀적으로 적용합니다. 이 경우 부품이 올바르게 정렬되었는지 확인할 수 있습니다.

빠른 정렬 알고리즘에서 피벗을 선택할 때 중요한 뉘앙스가 있습니다. 잘못된 피벗을 선택하면 배열이 두 개의 배열로 분할될 때마다 작은 결과가 나오기 때문에 끔찍한 복잡성으로 끝날 것입니다. 배열, 이 경우 n 재귀 호출이 있고 n 요소를 탐색해야 하므로 퀵 정렬은 O(n*n)이라는 최악의 시나리오를 갖습니다. 이는 끔찍하므로 다음과 같은 경우에 주의해야 합니다. 피벗을 선택하는 한 가지 좋은 방법은 임의의 숫자를 선택하는 것입니다. 그렇게 함으로써 우리는 O(n * log n), log n인 중간 사례를 얻게 될 것이라고 확신합니다. 평균 사례에서 우리는 분할할 것이기 때문입니다. 배열을 초기 배열 요소의 절반으로 구성된 두 개의 배열로 나누고, 모든 요소를 ​​조사해야 하므로 n의 인수가 있습니다.