빠른 정렬

빠른 정렬 알고리즘

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

어떻게 작동하나요?

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

알고리즘

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

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

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

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

위 내용은 빠른 정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!