Изобретена Нойманном в 1945 году.
Сложность алгоритма O(n log n).
Это стабильная сортировка, сохраняющая порядок одинаковых элементов.
Алгоритм состоит в разделении массива на подмассивы, содержащие по одному элементу, и последовательному слиянию отсортированных подмвссивов в новые отсортированные подмассивы.
При сортировке массива используется дополнительный массив такого же размера.
Процедура TopDownMergeSort<вх: A: массив, B: массив, n: натуральное число>
! Дано: в массиве A n чисел, массив B – рабочий
! Надо: в массиве А числа расположены по возрастанию
копировать(A, B, n) ! Копировать A в B
TopDownSplitMerge(B, 0, A, n) ! Сортировать из B в A
Конец процедуры
Процедура TopDownSplitMerge<вх: B: массив, beg: индекс, end: индекс, A: массив>
Если end-beg >= 2 то
mid := (beg+end)/2
TopDownSplitMerge(A, beg, mid, B)
TopDownSplitMerge(A, mid, end, B)
Merge(B, beg, mid, end, A)
Конец если
Конец процедуры
Процедура Merge<вх: A: массив, beg: индекс, mid: индекс, end: индекс, B: массив>
! Дано: A[beg:mid-1] и A[mid:end] отсортированы
! Надо: слить их в B с сортировкой
left = beg ! Индекс первого неучтенного числа из левой половины
right = mid ! Индекс первого неучтенного числа из правой половины
Цикл для каждого k из beg...end выполнять
Если (left < mid) и ((right >= end) или (A[left] < A[right])) то
! Если остались числа из левой половины,
! а в правой кончились или они больше то
B[k] = A[left] ! Добавить в B из левой половины
left = left + 1
Иначе
B[k] = A[right] ! Добавить в B из правой половины
right = right + 1
Конец если
Конец цикла
Конец процедуры
Процедура BottomUpMergeSort<вх: A: массив, B: массив, n: натуральное число>
! Дано: в массиве A n чисел, массив B – рабочий
! Надо: в массиве А числа расположены по возрастанию
width = 1
Цикл пока width < n выполнять
Цикл для каждого i из 0...n с шагом widh*2 выполнять
Merge(A, i, min(i+width, n), min(i+width*2, n), B)
Конец цикла
копировать(B, A, n)
width = width * 2
Конец цикла
Конец процедуры
Алгоритм сортировки Quick Sort был разработан Тони Хоаром в 1959 году во время учебы в МГУ под научным руководством А.Н.Колмогорова.
Сложность алгоритма в среднем O(n log n), в наихудшем случае — O(n2).
Идея алгоритма состоит в разделении большого массива на две (возможно, неравные) части и перемещении меньших значений в одну часть, а больших - в другую. Если этот процесс продолжать для каждой из частей массива до тех пор, пока размер частей не достигнет 1, то массив окажется отсортированным.
Шаги алгоритма следующие:
1. Выбрать из элементов массива стержневой (pivot)
2. Разделение: поменять порядок элементов массива так, что те, что меньше стержневого, идут до него, те, что больше, после него. Стержневой элемент, таким образом, оказывается на своем окончательном месте.
3. Последовательное повторение двух первых шагов для обеих частей массива (до и после стержневого).
Различные реализации алгоритма используют разные схемы выбора стержневого элемента и схемы изменения порядка элементов.
Так, например, в схеме Ломуто в качестве стержневого элемента выбирается последний элемент массива, а затем последовательно просматриваются все элементы с начала массива и те из них, кто меньше стержневого, меняются местами с теми из просмотренных, кто не удовлетворяет этому условию.
В схеме Хоара в качестве стержневого выбирается первый или последний элемент массива, а просматриваются элементы как с начала, так и с конца. Как только в начале находится элемент, больший стержневого, а в конце — меньше стержневого, они меняются местами.
Процедура QuickSort<вх: ar: массив, lo: индекс, hi: индекс>
! lo – индекс начала фрагмента, hi – индекс конца фрагмента,
! который надо отсортировать
Если lo < hi то
p := partition(ar, lo, hi) ! Стержневой элемент
QuickSort(ar, lo, p-1) ! Сортировать элементы до стержневого
QuickSort(ar, p+1, hi) ! Сортировать элементы после стержневого
Конец если
Конец процедуры
Процедура partition<вх: ar: массив, lo: индекс, hi: индекс>
! Инвариант цикла: те из просмотренных элементов, которые оказались
! меньше стержневого, лежат в начале массива, а
! их количество хранится в переменной «количество_меньших»
! Если очередной просматриваемый (i-ый) элемент меньше стержневого, то он добавляется
! к этим элементам: помещается в элемент за ними
! (то есть обменивается содержимым с элементом, расположенным за ними),
! а количество элементов, меньших стержневого, увеличивается на 1
pivot := ar[hi]
количество_меньших = 0
Цикл для каждого i из lo, hi-1 выполнять
Если ar[i] < pivot то
обменять(i, lo+количество_меньших)
количество_меньших += 1
Конец если
Конец цикла
Если ar[lo+количество_меньших] > pivot то ! Поставить стержневой сразу после меньших
обменять(hi, lo+количество_меньших)
Конец если
ответ := lo + количество_меньших
Конец процедуры
Процедура QuickSort<вх: ar: массив, lo: индекс, hi: индекс>
! lo – индекс начала фрагмента, hi – индекс конца фрагмента,
! который надо отсортировать
Если lo < hi то
p := partition(ar, lo, hi) ! Стержневой элемент
QuickSort(ar, lo, p) ! Сортировать элементы до стержневого включительно
QuickSort(ar, p+1, hi) ! Сортировать элементы после стержневого
Конец если
Конец процедуры
Процедура partition<вх: ar: массив, lo: индекс, hi: индекс>
! Инвариант цикла: те из просмотренных элементов, которые оказались
! меньше стержневого, лежат в начале массива и
! их количество хранится в переменной «количество_меньших»,
! в те, которые оказались больше стержневого, хранятся в конце массива
! и их количество хранится в переменной «количество_больших»
! На каждой итерации цикла за элементами, меньшими стержневого,
! ищется элемент, больший стержневого, а затем перед элементами,
! большими стержневого, ищется элемент, меньший стержневого
! Если поиск удался, найденные элементы меняются местами
pivot = ar[lo]
количество_меньших := 0
количество_больших := 0
Цикл пока lo+количество_меньших < hi-количество_больших выполнять
Цикл пока ar[lo+количество_меньших] < pivot выполнять
количество_меньших += 1
Конец цикла
Цикл пока ar[hi-количество_больших] > pivot выполнять
количество_меньших += 1
Конец цикла
обменять(lo+количество_меньших, hi-количество_больших]
Конец цикла
Конец процедуры