Теория и практика параллельных вычислений
Последовательный алгоритм
Последовательный алгоритм пузырьковой сортировки (the bubble sort algorithm) (см., например, [[26], [50]]) сравнивает и обменивает соседние элементы в последовательности, которую нужно отсортировать. Для последовательности
(a1, a2, ..., an)
алгоритм сначала выполняет n-1 базовых операций "сравнения-обмена" для последовательных пар элементов
(a1, a2), (a2, a3), ..., (an-1, an).
В результате после первой итерации алгоритма самый большой элемент перемещается ("всплывает") в конец последовательности. Далее последний элемент в преобразованной последовательности может быть исключен из рассмотрения, и описанная выше процедура применяется к оставшейся части последовательности
(a'1, a'2, ..., a'n-1).
Как можно увидеть, последовательность будет отсортирована после n-1 итерации. Эффективность пузырьковой сортировки может быть улучшена, если завершать алгоритм в случае отсутствия каких- либо изменений сортируемой последовательности данных в ходе какой-либо итерации сортировки.
Алгоритм 9.1. Последовательный алгоритм пузырьковой сортировки
// Алгоритм 9.1. // Последовательный алгоритм пузырьковой сортировки void BubbleSort(double A[], int n) { for (int i = 0; i < n - 1; i++) for (int j = 0; j < n - i; j++) compare_exchange(A[j], A[j + 1]); }
Общая идея сортировки Шелла (the Shell sort) (см., например, [26, 50]) состоит в сравнении на начальных стадиях сортировки пар значений, располагаемых достаточно далеко друг от друга в упорядочиваемом наборе данных. Такая модификация метода сортировки позволяет быстро переставлять далекие неупорядоченные пары значений (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов).
Общая схема метода состоит в следующем. На первом шаге алгоритма происходит упорядочивание элементов n/2 пар (ai, an/2+i) для 1in/2. Далее, на втором шаге упорядочиваются элементы в n/4 группах из четырех элементов (ai, an/4+i, an/2+i, a3n/4+i) для 1in/4. На третьем шаге упорядочиваются элементы уже в n/4 группах из восьми элементов и т.д. На последнем шаге упорядочиваются элементы сразу во всем массиве (a1, a2, ..., an). На каждом шаге для упорядочивания элементов в группах применяется метод сортировки вставками. Как можно заметить, общее количество итераций алгоритма Шелла равно log2n.
В более полном виде алгоритм Шелла может быть представлен следующим образом.
Алгоритм 9.4. Последовательный алгоритм сортировки Шелла
// Алгоритм 9.4 // Последовательный алгоритм сортировки Шелла void ShellSort(double A[], int n) { int incr = n / 2; while (incr > 0) { for (int i = incr + 1; i < n; i++) { int j = i - incr; while (j > 0) if (A[j] > A[j + incr]) { swap(A[j], A[j + incr]); j = j - incr; } else j = 0; } incr = incr/2; } }
При общем рассмотрении алгоритма быстрой сортировки (the quick sort algorithm), предложенной Хоаром (C.A.R. Hoare), прежде всего следует отметить, что этот метод основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока). На первой итерации метода осуществляется деление исходного набора данных на первые две части – для организации такого деления выбирается некоторый ведущий элемент и все значения набора, меньшие ведущего элемента, переносятся в первый формируемый блок, все остальные значения образуют второй блок набора. На второй итерации сортировки описанные правила применяются рекурсивно для обоих сформированных блоков и т.д. При надлежащем выборе ведущих элементов после выполнения log2n итераций исходный массив данных оказывается упорядоченным. Более подробное изложение метода может быть получено, например, в [[26], [50]].
Эффективность быстрой сортировки в значительной степени определяется правильностью выбора ведущих элементов при формировании блоков. В худшем случае трудоемкость метода имеет тот же порядок сложности, что и пузырьковая сортировка (т.е. T1~n2). При оптимальном выборе ведущих элементов, когда разделение каждого блока происходит на равные по размеру части, трудоемкость алгоритма совпадает с быстродействием наиболее эффективных способов сортировки . В среднем случае количество операций, выполняемых алгоритмом быстрой сортировки, определяется выражением (см., например, [[26], [50]]):
Общая схема алгоритма быстрой сортировки может быть представлена в следующем виде (в качестве ведущего элемента выбирается первый элемент упорядочиваемого набора данных).
Алгоритм 9.5. Последовательный алгоритм быстрой сортировки
// Алгоритм 9.5 // Последовательный алгоритм быстрой сортировки void QuickSort(double A[], int i1, int i2) { if (i1 < i2) { double pivot = A[i1]; int is = i1; for (int i = i1 + 1; i < i2; i++) if (A[i] Ј pivot) { is = is + 1; swap(A[is], A[i]); } swap(A[i1], A[is]); QuickSort(A, i1, is); QuickSort(A, is + 1, i2); } }
