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

Алгоритм быстрой сортировки Quicksort
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^2) }[/math]
Объём входных данных	[math]\displaystyle{ n }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(log n) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(n) }[/math]

Основные авторы описания: Я.А.Селивохин.

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

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

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

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

Алгоритм относится к сортировкам сравнением и выполняется in-place, то есть не требует дополнительной памяти для хранения подмассивов. В среднем случае время работы алгоритма составляет O(nlogn), однако сильно зависит от выбора опорного элемента.

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

Входные данные:' Массив A = [a₁, a₂, … , a_n], в котором элементы сравниваются операцией ≤, задающей полный порядок.

Выходные данные: Отсортированный массив A, удовлетворяющий:

a₁ ≤ a₂ ≤ … ≤ a_n.

Алгоритм основывается на операции разбиения массива относительно pivot:

L = { aᵢ | aᵢ < pivot }, R = { aᵢ | aᵢ ≥ pivot }.

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

T(n) = T(|L|) + T(|R|) + Θ(n).

В среднем случае при равномерном разделении:

T(n) = 2T(n/2) + Θ(n) = Θ(n log n).

В худшем случае (несбалансированное разбиение):

T(n) = T(n − 1) + Θ(n) = Θ(n²).

Код разбиения (С):

 
int partition(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; // Меняем местами элементы
 int temp = A[i];
 A[i] = A[j];
 A[j] = temp; } } // Ставим опорный элемент на правильную позицию
 int temp = A[i + 1];
 A[i + 1] = A[hi];
 A[hi] = temp;
 return i + 1; // Возвращаем индекс опорного элемента
}

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

Вычислительным ядром алгоритма является процедура partition, которая за время O(n) выполняет:

• последовательный просмотр массива,
• сравнение каждого элемента с pivot,
• перестановку элементов.

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

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

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

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

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

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

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

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

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

void quicksort(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. Информационная структура алгоритма быстрой сортировки

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

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

Граф зависит от структуры данных: для различных входов он имеет различную форму — граф недетерминирован.

Ключевые особенности:

• высота дерева рекурсии равна глубине алгоритма;
• ширина уровней может доходить до O(n) маленьких подмасивов;
• длинные дуги возникают при обменах pivot и элементов, так как значения могут находиться далеко в массиве.

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

Параллельная сложность определяется высотой рекурсивного дерева.

В среднем:

T_p=O(logn) (высота дерева ≈ log₂ n уровней).

Максимальный параллелизм — ширина ярусов:

P_max(k)=2n/2^k, то есть на верхних уровнях доступно больше параллелизма, чем на глубоких.

Важно:

• в среднем "идеальный параллелизм" близок к n / log n;
• в худшем случае (квадратичный сценарий):

ресурс параллелизма резко падает (цепочка из n узлов).

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

Входные данные: массив чисел из линейно упорядоченного множества (ℝ, ℤ или пользовательский тип с тотальным порядком). Например: A = [5,3,8,4,2]

Выходные данные: перестановка входного массива, удовлетворяющая насыщенному порядку. Например: A = [2,3,4,5,8]

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

• Детерминированность: Алгоритм недетерминированный по структуре: дерево рекурсии зависит от pivot, структура обменов зависит от данных, порядок сравнений непостоянен.
• Балансировка: Алгоритм плохо сбалансирован в худшем случае. При хороших pivot'ах — сбалансирован.
• Сложность: В худшем случае O(n²), в среднем O(nlogn).
• Устойчивость: Алгоритм неустойчив — элементы с одинаковыми значениями могут менять свой порядок.
• Память: Работает на месте, не требуя дополнительной памяти.
• Вычислительная плотность: Операции: почти все операции — сравнения; обращения к памяти играют заметную роль; вычислительная мощность ≈ 1 (низкая).
• Параллельность: Хорошо поддаётся параллельной реализации с использованием многозадачности для рекурсивных вызовов.
• Особенности реализации: кэш-локальность важна (partition использует последовательный проход → хорошая локальность); без оптимизации хвостовой рекурсии — возможно глубокое дерево вызовов.

Программная реализация алгоритма

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

быстрой сортировки (quicksort) над массивом целых чисел. Используется классическая схема разделения массива (partition), в которой последний элемент выбирается в качестве опорного. Данный подход обеспечивает хорошую производительность в среднем случае, однако в худшем случае приводит к квадратичной сложности. На практике это компенсируется случайным наполнением исходного массива и использованием параллельной сортировки на верхних уровнях рекурсии.

Важной особенностью реализации является управление глубиной рекурсии, передаваемое параметром depth. В последовательной ветке алгоритма этот параметр используется для ограничения порождения OpenMP-задач в параллельной версии, однако для последовательного исполнения это формирует чёткую структуру рекурсивного дерева вызовов.

Для ускорения исполнения используется условный переход к блочному распараллеливанию: если размер подмассива меньше порога THRESHOLD = 10000, сортировка выполняется последовательно без порождения задач. Такой блочный подход позволяет уменьшить накладные расходы, связанные с работой планировщика OpenMP, и обеспечивает лучшую локальность данных, поскольку каждый мелкий фрагмент обрабатывается одним потоком.

Алгоритм работает только с целыми числами (int), что избавляет от необходимости учитывать разрядность вещественных операций. Использование типа int снижает требования к памяти и увеличивает скорость вычислений благодаря простой арифметике и лучшей кэш-локальности.

Структура данных максимально проста — одномерный массив, передаваемый в рекурсивную функцию сортировки. Временные массивы не используются, за исключением локальной переменной при обмене элементов. Это делает реализацию экономичной по памяти: затраты ограничиваются O(1) дополнительной памятью, а общая глубина рекурсии ограничена длиной массива.

Ресурс параллелизма в последовательной форме ограничивается уровнем независимости подмассивов, возникающих после операции partition. Для случайного массива подмассивы приблизительно равны по размеру, что обеспечивает высокий потенциальный параллелизм. В последовательной реализации это свойство не используется непосредственно, но формирует основу для эффективного перехода к OpenMP и MPI в параллельной версии.

Параллельная реализация алгоритма и её особенности

Параллельная версия использует гибридную модель MPI + OpenMP и включает параллелизм двух уровней:

  1 Межузловой (распределённая память — MPI)

Исходный массив делится между всеми MPI-процессами. Распределение выполняется через MPI_Scatterv, что позволяет корректно передавать неравномерные размеры блоков (из-за возможного остатка N % size). Такой подход обеспечивает почти равномерную загрузку процессов.

Каждый MPI-процесс сортирует свою часть массива независимо. После локальной сортировки используется MPI_Gatherv для полного сбора данных в процесс с рангом 0. Для объединения частично отсортированных блоков может быть применён доп. этап слияния, но в данной реализации весь массив собирается как есть, что подходит для исследования производительности стадии сортировки.

Стоимость коммуникаций определяется:

• пересылкой N элементов при Scatterv и Gatherv;
• отсутствием обменов во время сортировки — полная независимость процессов.

  2 Внутриузловой (общая память — OpenMP)

Внутри каждого MPI-процесса сортировка осуществляется с помощью OpenMP-задач (#pragma omp task). Параллельный quicksort строит дерево задач, где каждая задача отвечает за сортировку подмассива.

Особенности:

• Параллелизм ограничен глубиной MAX_DEPTH = 5, чтобы не создавать слишком много задач.
• Задачи создаются только для крупных подмассивов (THRESHOLD = 10000), что минимизирует накладные расходы и улучшает кэш-локальность.
• Конструкция #pragma omp single обеспечивает корректный запуск рекурсии из одного потока.
• Синхронизация достигается через #pragma omp taskwait.

   Особенности гибридной модели MPI+OpenMP

Преимущества:

• Разделение работ между узлами кластера (масштабирование по N).
• Распараллеливание рекурсивных вызовов внутри узлов (масштабирование по ядрам).
• Локальность данных: каждый узел сортирует свою часть памяти.

Недостатки:

• Финальный массив после Gatherv не является глобально отсортированным без дополнительного параллельного слияния.
• Производительность зависит от того, как равномерно разбиение Scatterv распределило данные.

Количество операций на каждый MPI-процесс ≈ O((N/size) log(N/size)). Коммуникации = 2 передачи объёма N (одна Scatterv, одна Gatherv).

Результаты прогонов

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

   1 Массив из 100 млн. элементов

Локальный компьютер (8 MPI-процесса) Команда: mpirun -np 8 ./quicksort_res Результат: Local sort time (first process): 4.437600 sec Total MPI time: 4.604241 sec

СК «Ломоносов-2» (8 MPI процессов, очередь test) Команда: sbatch -p test -n 8 ompi ./quicksort_res Результат: Local sort time (first process): 1.301150 sec Total MPI time: 2.216287 sec

   2 Массив из 1 млрд. элементов

Локальный компьютер (8 MPI-процесса) Команда: mpirun -np 8 ./quicksort_res Результат:

BAD TERMINATION OF ONE OF YOUR APPLICATION PROCESSES PID 22917 RUNNING AT yaroslav-BRG-XXX EXIT CODE: 9 CLEANING UP REMAINING PROCESSES YOU CAN IGNORE THE BELOW CLEANUP MESSAGES

YOUR APPLICATION TERMINATED WITH THE EXIT STRING: Killed (signal 9) Локальный компьютер уже не способен обработать массив из 1 млрд. элементов.

СК «Ломоносов-2» (8 MPI процессов, очередь test)

Замер на 1 node Команда: sbatch -p test -n 8 -N 1 ompi ./quicksort_res Результат: Local sort time (first process): 6.017083 sec Total MPI time: 8.022983 sec

Замер на 2 node Команда: sbatch -p test -n 8 -N 2 ompi ./quicksort_res Результат: Local sort time (first process): 5.994353 sec Total MPI time: 8.194636 sec

Замер на 4 node Команда: sbatch -p test -n 8 -N 4 ompi ./quicksort_res Результат: Local sort time (first process): 5.484756 sec Total MPI time: 7.773029 sec

Замер на 8 node Команда: sbatch -p test -n 8 -N 8 ompi ./quicksort_res Результат: Local sort time (first process): 5.984324 sec Total MPI time: 8.361505 sec

Выводы для классов архитектур

   Многоядерные SMP-системы (общая память)

• OpenMP-parallel quicksort показывает существенное ускорение при достаточном размере данных.
• Ограничение глубины задач MAX_DEPTH предотвращает деградацию производительности.
• Локальность данных в рекурсивных подмассивах хорошо соответствует кэш-иерархии современных CPU.

   Кластеры с распределённой памятью (MPI)

• Статическое разбиение массива через Scatterv обеспечивает сбалансированную загрузку узлов.
• Обмены ограничиваются двумя глобальными коммуникациями, что делает алгоритм масштабируемым.
• Для полной сортировки после Gatherv требуется глобальное параллельное слияние, если нужна полноценная сортировка.

   Гибридные системы MPI + OpenMP

• Наиболее эффективная архитектура для данного алгоритма.
• Комбинация распределённой сортировки и локального распараллеливания обеспечивает максимальный параллелизм.
• Минимальное пересечение данных между узлами снижает сетевые затраты.

   GPU-архитектуры

Реализация в текущем виде не ориентирована на GPU:

• рекурсивная структура и неоднородность памяти плохо ложатся на SIMD-архитектуру.
• требуются специализированные алгоритмы на основе bitonic sort или radix sort.

Тем не менее часть вычислений может быть перенесена при переработке алгоритма.

Литература

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.