Участник:Yaselivoxin/Алгоритм

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

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм быстрой сортировки (Quicksort) — это один из наиболее известных и часто применяемых алгоритмов сортировки с использованием стратегии "разделяй и властвуй". Алгоритм работает следующим образом: выбирается опорный элемент массива (pivot), и все элементы массива разделяются на две части: те, что меньше опорного, и те, что больше или равны ему. Затем рекурсивно сортируются эти две части. Сортировка продолжается, пока каждый подмассив не будет отсортирован, что приводит к полному упорядочиванию элементов массива.

Этот алгоритм работает на основе сравнений элементов и выполняет операцию сортировки "на месте", то есть без использования дополнительных массивов для хранения промежуточных результатов. Время работы алгоритма зависит от выбора опорного элемента и в лучшем случае составляет 𝑂(nlogn).

Математическое описание алгоритма

Входные данные: Массив А = [a₁, a₂, ... , a_n] длинной n, где каждый элемент массива a_i сравнивается с другими элементами массива с помощью операции "<=" ("меньше или равно").

Выходные данные: Отсортированный массив А, такой что для всех i и j выполняется условие:

a₁ ≤ a₂ ≤ ... ≤ a_n.

Псевдокод алгоритма:

int partition(std::vector<int>& A, int lo, int hi) {
    int pivot = A[hi]; // Опорный элемент
    int i = lo - 1; // Индекс для меньших элементов
    for (int j = lo; j < hi; ++j) {
        if (A[j] <= pivot) {
            ++i;
            std::swap(A[i], A[j]); // Меняем местами элементы
        }
    }
    std::swap(A[i + 1], A[hi]); // Ставим опорный элемент на правильную позицию
    return i + 1; // Возвращаем индекс опорного элемента
}

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма быстрой сортировки заключается в разделении массива на два подмассива относительно опорного элемента, после чего рекурсивно сортируются эти подмассивы. Основная операция, выполняющаяся за O(n) в каждом вызове рекурсии, — это разбиение массива на две части (пункт 1.2). Таким образом, вычислительное ядро — это функция partition.

Макроструктура алгоритма

Алгоритм состоит из двух основных макроопераций:

1. Выбор опорного элемента (pivot).
2. Разделение массива на две части, элементы которых меньше и больше опорного.
3. Рекурсивная сортировка двух частей.

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

Схема реализации последовательного алгоритма

Пример реализации быстрой сортировки на языке псевдокода:

• Разделение массива относительно опорного элемента.
• Рекурсивная сортировка двух подмассивов.

Пример кода на C++:

// Рекурсивная функция быстрой сортировки
void quicksort(std::vector<int>& A, int lo, int hi) {
    if (lo < hi) {
        int p = partition(A, lo, hi); // Разбиение массива
        quicksort(A, lo, p - 1); // Сортируем левую часть
        quicksort(A, p + 1, hi); // Сортируем правую часть
    }
}

Последовательная сложность алгоритма

Временная сложность:

• Лучший случай: O(nlogn), когда выбор опорного элемента сбалансирован, и массив делится примерно пополам.
• Средний случай: O(nlogn), для случайного массива.
• Худший случай: O(n²), если опорный элемент всегда оказывается наименьшим или наибольшим элементом.

Пространственная сложность: O(logn), поскольку рекурсия в худшем случает требует глубины стека O(n), а в среднем случае - O(logn).

Информационный граф

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

Рис.1. Информационная структура алгоритма быстрой сортировки

Вводимые замены:

• ОЭ - опорный элемент
• ЛЧ - левая часть
• ПЧ - правая часть

Ресурс параллелизма алгоритма

Алгоритм быстрой сортировки обладает хорошим потенциалом для параллельной реализации. Основной параллелизм можно достичь за счет выполнения рекурсивных вызовов для левых и правых подмассивов параллельно. Для этого можно использовать многозадачность, например, с помощью библиотек OpenMP или стандартной библиотеки C++. Например, с использованием

std::async

Входные и выходные данные алгоритма

Входные данные: Массив чисел (или других объектов, для которых определено сравнение), например: A = [5,3,8,4,2]

Выходные данные: Отсортированный массив: A = [2,3,4,5,8]

Свойства алгоритма

• Сложность: В худшем случае O(n²), в среднем O(nlogn).
• Устойчивость: Алгоритм неустойчив — элементы с одинаковыми значениями могут менять свой порядок.
• Память: Работает на месте, не требуя дополнительной памяти.
• Параллельность: Хорошо поддаётся параллельной реализации с использованием многозадачности для рекурсивных вызовов.

Литература

1. Cormen, T. H. , Leiserson, C. E. , Rivest, R. L. , Stein, C. (2009). Introduction to Algorithms. MIT Press.
2. Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley.
3. Hoare, C. A. R. (1961). Quicksort. Computer Journal, 5(1), 10-15.