Участник: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++:

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; // Возвращаем индекс опорного элемента
}

// Рекурсивная функция быстрой сортировки
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).

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

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

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

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

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

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

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

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

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