Алгоритм быстрой сортировки

Быстрая сортировка — один из самых известных алгоритмов сортировки, поскольку он реализован на нескольких языках программирования в стандартной библиотеке. Почему этот алгоритм так используется??
Благодаря своей скорости алгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки, имеющий временную сложность 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.