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

Что такое быстрая сортировка? Как это работает? Какова его временная и пространственная сложность? Это лучший алгоритм сортировки? В этой статье мы дадим ответы на все эти вопросы.

Быстрая сортировка – это эффективный и широко используемый алгоритм сортировки, основанный на принципе разделяй и властвуй. Этот подход предполагает разбиение сложной проблемы на более мелкие, более управляемые части, которые можно легко решить.

Рекомендуемые предварительные знания:

• Рекурсия
• Массивы

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

Быстрая сортировка основана на концепции функции partition. Фундаментальная идея этой функции состоит в том, чтобы выбрать основной элемент из массива для сортировки и переупорядочить другие элементы таким образом, чтобы все значения, большие или равные опорному, были помещается после него, а все значения, меньшие опорного, помещаются перед ним.

Выбирая подходящую опорную точку, QuickSort эффективно делит массив на два подмассива, каждый из которых можно сортировать независимо. Процесс разделения повторяется рекурсивно для подмассивов, пока не будет отсортирован весь массив.

Важно отметить, что основная обязанность функции секционирования — не сортировка всего массива, а правильное определение и позиционирование опорной точки. Именно через все последующие рекурсивные вызовы массив постепенно сортируется.

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

Как выбрать хороший разворот

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

Наиболее распространенные методы выбора точки опоры:

Первый элемент, последний элемент или средний элемент

Самый простой подход — выбрать либо первый элемент, либо последний элемент, либо средний элемент массива в качестве опорного. Этот метод легко реализовать, но не всегда можно получить сбалансированные разделы, особенно если массив уже отсортирован или почти отсортирован.

Случайный элемент

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

При случайном выборе опорной точки вероятность встретить отсортированный или почти отсортированный массив снижается, что приводит к более сбалансированным разбиениям.

Медиана из трех

Метод медианы трех направлен на выбор опорной точки, которая ближе к истинной медиане массива. Он включает в себя сравнение и выбор медианного значения среди первого элемента, среднего элемента и последнего элемента массива. Такой подход помогает получить более сбалансированные разделы и во многих случаях повышает общую производительность QuickSort.

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

В нашем случае для простоты мы будем реализовывать первый метод. Мы выберем в качестве точки опоры средний элемент массива.

Помните, что то, как мы выбрали опорную точку, не влияет на результат, которым является отсортированный массив, а только на его эффективность.

Как работает раздел

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

После применения алгоритма разбиения к массиву мы видим, что ни левые, ни правые элементы свода не отсортированы. Однако в чем мы можем быть уверены, так это в том, что точка поворота правильно расположена внутри массива.

Когда дело доходит до схем разделов, нам представлены два популярных варианта: Lomuto и Hoare.

Схема разделения Lomuto обычно считается более простой в реализации из-за ее простой логики и простоты.

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

Мы будем работать по схеме Ломуто.

int partition(int array[], int low, int high)
{
    int pivot, pivotIndex, i;

    swap(array, low, (low+high)/2);       // 1

    pivot = array[low];                   // 2
    pivotIndex = low;                     // 2
    
    for(i = low+1; i <= high; i++)        // 3
        if(array[i] < pivot)
            swap(array, ++pivotIndex, i); // 3

    swap(array, low, pivotIndex);         // 4

    return pivotIndex;                    // 5
}

Принцип работы с разделами довольно прост.

1. Чтобы упростить манипулирование массивом и сосредоточиться исключительно на остальных элементах, мы заменяем первый элемент средним элементом. Следовательно, опорная точка, ранее располагавшаяся посередине, теперь располагается в начале массива. .
2. Мы определяем первый элемент как опорный и сохраняем его начальное положение как поворотный индекс.
3. Начиная с элемента сразу после поворота, мы итерируем оставшиеся элементы. На каждом шаге мы сравниваем значение текущего элемента (в позиции i) с опорным значением. Если текущий элемент меньше опорного, мы заменяем его новой позицией опорного элемента (pivotPosition, которая увеличивается на единицу перед обменом). Важно отметить, что позиция опорной точки больше не указывает на ее положение в массиве, а указывает, куда ее следует поместить, чтобы гарантировать, что все предыдущие значения будут меньше (и все последующие значения будут больше после завершения цикла).
4. Мы заменяем значение в начале массива значением в опорной позиции. Этот шаг имеет решающее значение, поскольку он гарантирует, что точка поворота, которая изначально находилась в начале массива, теперь правильно расположена в точке поворота. Такое размещение гарантирует, что все значения, предшествующие опорной точке, будут меньше, а все значения, следующие за ней, будут больше. Стоит отметить, что конкретное значение, хранящееся в массиве[pivotPosition], не имеет значения; единственное требование состоит в том, что он должен быть меньше, чем стержень. Как только опорная точка правильно расположена в массиве, она остается фиксированной в этом месте на протяжении всего остального процесса сортировки. Его окончательное размещение гарантирует, что он действует как точка отсчета для разделения массива на два раздела; элементы меньше, чем стержень слева, и элементы больше, чем стержень справа.
5. На этом этапе мы возвращаем pivotPosition. Это значение имеет решающее значение для последующих шагов функции QuickSort, поскольку оно обеспечивает правильную адресацию двух подмассивов, которые необходимо отсортировать.

void swap(int array[], int index1, int index2)
{
    int temp = array[index1];

    array[index1] = array[index2];
    array[index2] = temp;
}

void quickSort(int array[], int low, int high)
{
    int pivotIndex;

    if(low < high)                                // 1
    {
        pivotIndex = partition(array, low, high); // 2
        quickSort(array, low, pivotIndex-1);      // 3
        quickSort(array, pivotIndex+1, high);     // 4
    }
    // 5
}