Реализация быстрой сортировки на C/C++

До текущего момента единственной публикацией о сортировке в моем блоге была статья про реализацию топологической сортировки вершин графа. Пора это исправлять! Строить грандиозных планов о покорении всех видов сортировки я не стану, а начну с одной из самых популярных — быстрая сортировка.

Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.

Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.

Как работает быстрая сортировка

Схему алгоритма можно описать таким образом:

1. Выбрать опорный элемент в массиве — часто встречается вариант с центральным элементом.
2. Разделить массив на две части следующим образом: все элементы из левой части, которые больше или равны опорному, перекидываем в правую, аналогично, все элементы из правой, которые меньше или равны опорному кидаем в левую часть.
3. В результате предыдущего шага в левой части массива останутся элементы, которые меньше или равны центральному, а в правой — больше либо равны.
   Наглядно это можно показать таким образом:
   |———————|—————————|———————|
   | mas[i] <= mid  | mid = mas[size/2]  | mas[i] >= mid   |
   |———————-|—————————|———————|
4. Рекурсивно повторяем действие для левой и правой части массива.

Заходы в рекурсию прекратятся в тот момент, когда размер обоих частей будет меньше или равен единице.

Иллюстрацию одного шага алгоритма я позаимствовал отсюда, больно уж она наглядная.

Рекурсивная реализация быстрой сортировки

На вход функция принимает сам массив(указатель на начало) и его размер.

void qsortRecursive(int *mas, int size) {
    //Указатели в начало и в конец массива
    int i = 0;
    int j = size - 1;

    //Центральный элемент массива
    int mid = mas[size / 2];

    //Делим массив
    do {
        //Пробегаем элементы, ищем те, которые нужно перекинуть в другую часть
        //В левой части массива пропускаем(оставляем на месте) элементы, которые меньше центрального
        while(mas[i] < mid) {
            i++;
        }
        //В правой части пропускаем элементы, которые больше центрального
        while(mas[j] > mid) {
            j--;
        }

        //Меняем элементы местами
        if (i <= j) {
            int tmp = mas[i];
            mas[i] = mas[j];
            mas[j] = tmp;

            i++;
            j--;
        }
    } while (i <= j);


    //Рекурсивные вызовы, если осталось, что сортировать
    if(j > 0) {
        //"Левый кусок"
        qsortRecursive(mas, j + 1);
    }
    if (i < size) {
        //"Првый кусок"
        qsortRecursive(&mas[i], size - i);
    }
}

Заключение

Это задание одновременно помогает понять, как работает рекурсия и учит прослеживать изменение данных во время исполнения алгоритма. Рекомендуется «дойти» и написать это самостоятельно, но все же вот моя реализация, мне и самому она может пригодиться. На этом у меня все, спасибо за внимание!