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

На вход алгоритма подаётся последовательность n элементов

Задача

На выходе алгоритм должен вернуть

Сортировка пузырьком
(bubble sort)

Пример

i = 1

i = 2

i = 3

i = 4

Алгоритм

for i = 1 to n-1
for j = 1 to n-i
if

Сложность

for i = 1 to n-1
for j = 1 to n-i
if

Сортировка вставками
(insertion sort)

Пример

Алгоритм

for j = 2 to n
key = A[j]
i

Сложность

n
n-1
n-1
n-1

Количество операций

for j = 2 to n
key = A[j]

Сложность

Лучший случай: массив отсортирован по возрастанию, тогда

Худший случай: массив отсортирован

Сортировка выбором
(selection sort)

Пример

Алгоритм

for i = 1 to n-1 do
min = i
for j =

Сложность

for i = 1 to n-1 do
min = i
for j =

Быстрая сортировка (Хоара)
(QuickSort)

Идея

Вход: массив А, индексы l и r, которые определяют подмассив для

Алгоритм

QuickSort(A,l,r)
If lq = Partition(A,l,r)
QuickSort(A,l,q-1)
QuickSort(A, q+1,r)

Partition(A,l,r)
X = A[r]
i = l -

Алгоритм (случайный выбор опорного элемента)

RandomQuickSort(A,l,r)
If lq = RandomPartition(A,l,r)
RandomQuickSort(A,l,q-1)
RandomQuickSort(A, q+1,r)

RandomPartition(A,l,r)
i=random(l,r)
A[i] <-->

Процедура разбиения

X = A[r] - опорный элемент (разделитель)
A[l...i] <= X
A[i+1...j-1] >X
A[j...r-1]

A[j]=2 < X=4 => i=i+1, j=j+1

A[j]=8 > X=4 => j=j+1

A[j]=7 >

Сложность

Лучший случай. В наиболее сбалансированном варианте при каждой операции разделения массив

Cортировка слиянием
(merge sort)

Идея

Вход: массив А, индексы l и r, которые определяют подмассив для

Пример

Алгоритм MergeSort

MergeSort(A,l,r)
If lq = [(l + r)/2]
MergeSort(A,l,q)
MergeSort(A,q+1,r)
Merge(A,l,q,r)

Сложность алгоритма
T(n) =