8 мар в 23:27

Быстрая сортировка quicksort (студентам и начинающим)

Средний

Ожидает приглашения

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

Цель статьи — дать базовое понимание работы алгоритма, которое позволит применять его на практике.

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

Быстрая сортировка - это элегантный и относительно быстрый алгоритм, сложность которого в среднем около O(n log n). Но может колебаться от O(n) до O(n²).

Разбор алгоритма

В рамках примера представим, что перед нами стоит задача произвести сортировку одномерного массива целых чисел.

Для начала создадим метод SortQuick, который в качестве результата будет возвращать целочисленный массив, и в качестве аргумента(параметра) метод так же будет ожидать целочисленный массив.

int[] SortQuick(int[] arr)
{            
}

Разделим логику выполнения метода на две ситуации:
1. Базовый случай - массив пуст или состоит из одного элемента.
2. Рекурсивный случай - массив содержит более одного элемента.

Разберем базовый случай

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

int[] SortQuick(int[] arr)
{
    //Базовый случай
    if (arr.Length < 2) { return arr; }
}

Разберем рекурсивный случай

Программа зашла в блок кода для рекурсивного случая – значит полученный в качестве аргумента массив пуст или содержит более одного элемента.
Для рекурсивного случая выделим три шага.

Шаг 1. Выбор опорного элемента
Опорным можно выбрать абсолютно любой элемент из массива, который был передан в метод в качестве аргумента. Но нужно запомнить, что от выбора опорного элемента зависит скорость выполнения сортировки. Есть разные подходы к выбору опорного элемента и это отдельная тема, которую лучше опустить при изучении только основ быстрой сортировки.
В рамках примера мы будем выбирать в качестве опорного первый элемент массива, элемент с индексом 0.

//Выбираем опорный элемент
int support = arr[0];

Шаг 2. Разделение полученного в качестве аргумента массива на три подмассива
1. Левый – для элементов, которые меньше опорного
2. Центральный – для элементов, которые равны опорному
3. Правый – для элементов, которые больше опорного

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

int[] left = SortQuick(arr.Where(x => x < support).ToArray());
int[] right = SortQuick(arr.Where(x => x > support).ToArray());
int[] center = arr.Where(x => x == support).ToArray();

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

Шаг 3. Объединение результатов
Теперь мы уже имеем три подмассива, которые "отсортированы". Осталось их объединить в естественном порядке: левый + центральный + правый. Это и будет наш ожидаемый от метода результат.

return left.Concat(center).Concat(right).ToArray();

Готово. Ниже, для наглядности, весь код реализованного метода SortQuick.

int[] SortQuick(int[] arr)
{
    //Базовый случай>>
    if(arr.Length < 2) { return arr;}

    //Рекурсивный случай>>
    //Выбираем опорный элемент (Для простоты восприятия это будет первый элемент)
    int support = arr[0];

    //Разделяем на подмассивы
    //Передавая элементы отобранные по критериям рекурсивно в метод SortQuick
    int[] left = SortQuick(arr.Where(x => x < support).ToArray());
    int[] right = SortQuick(arr.Where(x => x > support).ToArray());
    int[] center = arr.Where(x => x == support).ToArray();

    //Возвращаем правильно склеенный массив
    return left.Concat(center).Concat(right).ToArray();
}

Хабы: