Алгоритмы сортировки
Выбери формат для чтения
Статья: Алгоритмы сортировки
Загружаем конспект в формате pdf
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Алгоритмы сортировки
лекция 3
Задача сортировки (sorting problem)
▪ Дана последовательность из n ключей
𝑎1 , 𝑎2 , … , 𝑎𝑛
▪ Требуется упорядочить ключи по неубыванию или по невозрастанию – найти перестановку
(i1, i2, …, in) ключей
▪ По неубыванию (non-decreasing order)
𝑎𝑖 1 ≤ 𝑎𝑖 2 ≤ ⋯ ≤ 𝑎𝑖 𝑛
▪ По невозрастанию (non-increasing order)
𝑎𝑖 1 ≥ 𝑎𝑖 2 ≥ ⋯ ≥ 𝑎𝑖 𝑛
2
Задача сортировки (sorting problem)
▪ Алгоритму сортировки должен быть известен способ сравнения ключей
a v[i] then
swap(v[i - 1], v[i])
swapped = True
end if
end for
end while
𝑻𝑩𝒖𝒃𝒃𝒍𝒆𝑺𝒐𝒓𝒕 = 𝑶(𝒏𝟐)
end function
5
54
23
45
2
4
4
42
34
“Легкие” элементы перемещаются (всплывают) в начало массива
8
Сортировка вставкой (Insertion Sort)
function InsertionSort(A[1:n], n)
for i = 2 to n do
key = A[i]
/* Вставляем A[i] в упорядоченный подмассив A[1..i-1] */
j = i - 1
while j > 0 and A[j] > key do
A[j + 1] = A[j]
j = j - 1
end while
A[j + 1] = key
end for
end function
▪ Двигаемся по массиву слева направо: от 2-го до 𝑛-го элемента
▪ На шаге 𝑖 имеем упорядоченный подмассив 𝐴[1. . 𝑖 1] и элемент 𝐴[𝑖], который необходимо
вставить в этот подмассив
9
Сортировка вставкой (Insertion Sort)
▪ В худшем случае цикл while всегда доходит до первого элемента массива – на вход
поступил массив, упорядоченный по убыванию
▪ Для вставки элемента 𝐴[𝑖] на своё место требуется 𝑖 1 итерация цикла while; на каждой
итерации выполняем 𝑐 действий
▪ Учитывая, что нам необходимо найти позиции для 𝑛 1 элемента, время 𝑇(𝑛) выполнения
алгоритма в худшем случае равно
𝑛
𝑇 𝑛 = 𝑐 𝑖 − 1 = 𝑐 + 2𝑐 + ⋯ + 𝑖 − 1 𝑐 + ⋯ + 𝑛 − 1 𝑐 =
𝑖=2
𝑐𝑛(𝑛 − 1)
=
= Θ 𝑛2 .
2
10
Сортировка вставкой (Insertion Sort)
▪ Лучший случай для Insertion Sort?
11
Сортировка вставкой (Insertion Sort)
▪ Лучший случай для Insertion Sort?
▪ Массив уже упорядочен
▪ Алгоритм сортировки вставкой является устойчивым – не меняет относительный порядок
следования одинаковых ключей
▪ Использует константное число дополнительных ячеек памяти (переменные 𝑖, 𝑘𝑒𝑦 и 𝑗), что
относит его к классу алгоритмов сортировки на месте (in-place sort).
▪ Кроме того, алгоритм относится к классу online-алгоритмов – он обеспечивает возможность
упорядочивания массивов при динамическом поступлении новых элементов
12
Сортировка слиянием (merge sort)
▪ Сортировка слиянием (merge sort) – рекурсивный алгоритм сортировки сравнением, основанный на методе
декомпозиции (decomposition)
[1, 1] [2, 2]
MergeSort(1, 9)
1
2
5
4
3
6
9
8
7
9
9 12 5 7 6 9 1 2 3
[1, 9]
12
Merge(1, 1, 2) 9 12
[1, 5]
[3, 3] [4, 4] [5, 5]
5
7
6
6 7
9
1
1 9
2
3
2 3 Merge(8, 8, 9)
[6, 9]
Merge(1, 2, 3) 5 9 12
[1, 3]
[1, 2]
[6, 6] [7, 7] [8, 8] [9, 9]
[4, 5]
[6, 7]
1 2 3 9 Merge(6, 7, 9)
[8, 9]
[3, 3]
[4, 4]
[5, 5]
[6, 6]
[7, 7]
[8, 8]
[9, 9]
5
7
6
9
1
2
3
Merge(1, 3, 5) 5 6 7 9 12
[1, 1] [2, 2]
9
Merge(1, 5, 9) 1 2 3 5 6 7 9 9 12
12
Фаза разделения
Фаза слияния
13
Сортировка слиянием (merge sort)
function MergeSort(A[1:n], low, high)
if low < high then
mid = floor((low + high) / 2)
MergeSort(A, low, mid)
MergeSort(A, mid + 1, high)
Merge(A, low, mid, high)
end if
end function
▪ Сортируемый массив 𝐴[𝑙𝑜𝑤 . . ℎ𝑖𝑔ℎ] разделяется на две максимально равные по длине
части
▪ Первая часть содержит ⌈𝑛/2⌉ элементов, вторая – ⌊𝑛/2⌋ элементов
▪ Подмассивы рекурсивно сортируются
14
Сортировка слиянием (merge sort)
function Merge(A[1:n], low, mid, high)
for i = low to high do
B[i] = A[i]
/* Создаем копию массива A */
end for
l = low
/* Номер первого элемента левого подмассива */
r = mid + 1 /* Номер первого элемента правого подмассива */
i = low
while l <= mid and r <= high do
if B[l] <= B[r] then
A[i] = B[l]
l = l + 1
else
A[i] = B[r]
r = r + 1
end if
i = i + 1
end while
15
Сортировка слиянием (merge sort)
while l <= mid do
/* Копируем оставшиеся элементы из левого подмассива */
A[i] = B[l]
l = l + 1
i = i + 1
end while
while r <= high do
/* Копируем оставшиеся элементы из правого подмассива */
A[i] = B[r]
r = r + 1
i = i + 1
end while
end function
▪ Функция Merge требует порядка Θ(𝑛) ячеек памяти для хранения копии 𝐵 сортируемого
массива
▪ Сравнение и перенос элементов из массива 𝐵 в массив 𝐴 требует Θ(𝑛)
16
Сортировка слиянием (merge sort)
▪ Время 𝑇(𝑛) работы алгоритма включает время сортировки левого подмассивов длины
𝑛/2 и правого – с числом элементов 𝑛/2 , а также время Θ(𝑛) слияния подмассивов
после их рекурсивного упорядочивания
𝑇 𝑛 = 𝑇 𝑛Τ2 + 𝑇 𝑛Τ2 + Θ(𝑛)
▪ Необходимо решить это рекуррентное уравнение – получить выражение для 𝑇(𝑛) без
рекуррентности
17
Дерево рекурсивных вызовов MergeSort
Слияние 2-х
подмассивов
Слияние 4-х
подмассивов
Слияние 8-и
подмассивов
18
Дерево рекурсивных вызовов MergeSort
Слияние 2-х
подмассивов
Слияние 4-х
подмассивов
▪ Высота дерева Θ(𝑙𝑜𝑔𝑛)
Слияние 8-и
подмассивов
▪ На каждом уровне i находится 2𝑖 узлов
▪ Каждый узел требует выполнения
𝑛
𝑖 операций
2
19
Дерево рекурсивных вызовов MergeSort
Слияние 2-х
подмассивов
ℎ
𝑇 𝑛 =
2𝑖
𝑖=0
ℎ
𝑛
= 𝑛 = ℎ + 1 𝑛 = 𝑛 log 2 𝑛 + 𝑛 = Θ(𝑛 log 𝑛).
2𝑖
𝑖=0
▪ Высота дерева Θ(𝑙𝑜𝑔𝑛)
Слияние 4-х
подмассивов
Слияние 8-и
подмассивов
▪ На каждом уровне i находится 2𝑖 узлов
▪ Каждый узел требует выполнения
𝑛
𝑖 операций
2
20
Быстрая сортировка (Quick Sort)
1. Из элементов 𝑣[1], 𝑣[2], … , 𝑣[𝑛] выбирается опорный элемент (pivot element)
▪ Опорный элемент желательно выбирать так, чтобы его значение было близко к
среднему значению всех элементов
▪ Вопрос о выборе опорного элемента открыт (первый/последний, средний из трех,
случайный и т.д.)
2. Массив разбивается на 2 части: элементы массива переставляются так, чтобы элементы
расположенные левее опорного были не больше (<=), а расположенные правее – не меньше
него (>=). На этом шаге определяется граница разбиения массива.
3. Шаги 1 и 2 рекурсивно повторяются для левой и правой частей
21
Быстрая сортировка (Quick Sort)
function QuickSort(v[1:n], n, l, r)
if l < r then
k = Partition(v, n, l, r)
QuickSort(v, n, l, k - 1)
QuickSort(v, n, k + 1, r)
end if
end function
// Разбиваем
// Левая часть
// Правая часть
QuickSort(1, n)
QuickSort(l, k – 1)
• Худший случай: 𝑻𝑸𝒖𝒊𝒄𝒌𝑺𝒐𝒓𝒕 = 𝑶(𝒏𝟐)
• Средний случай: 𝑻𝑸𝒖𝒊𝒄𝒌𝑺𝒐𝒓𝒕 = 𝑶(𝒏𝒍𝒐𝒈𝒏)
QuickSort(k + 1, r)
22
Быстрая сортировка (Quick Sort)
function Partition(v[1:n], n, l, r)
pivot_idx = r
/* Выбрали индекс опорного элемента */
swap(v[pivot_idx], v[r])
2 8 7 1 3 5 6 4
pivot = v[r]
r=n
l=1
i = l – 1
pivot = 4
i=0
for j = l to r – 1 do
j = 1: swap(v[1], v[1])
if v[j] <= pivot then
j = 4: swap(v[2], v[4])
i = i + 1
2 1 7 8 3 5 6 4
swap(v[i], v[j])
j = 5: swap(v[3], v[5])
end if
2 1 3 8 7 5 6 4
end for
swap(v[4], v[8])
swap(v[i + 1], v[r])
return i + 1
2 1 3 4 7 5 6 8
end function
return 4
23
Быстрая сортировка (Quick Sort)
▪ Худший случай для Quick Sort?
▪ В качестве опорного элемента выбрали наименьший или наибольший ключ
24
Сортировка подсчетом (Counting Sort)
𝑨[𝟎. . 𝟔] 𝒌 = max 𝑨[𝟎. . 𝟔] = 𝟕
4
1
1
7
5
3
▪
▪
▪
▪
Не использует операцию сравнения!
Целочисленная сортировка (integer sort)
Вычислительная сложность 𝑂(𝑛 + 𝑘)
Сложность по памяти 𝑂(𝑛 + 𝑘)
𝑪[𝟎. . 𝒌] 𝑪[𝟎. . 𝒌] 𝑩[𝟎. . 𝟔]
0 1
0 1
1 2
1 3
1
2 0
2 3
1
3 1
3 4
3
4 1
4 5
4
5 1
5 6
5
6 0
6 6
7
7 1
7 7
25
Литература
▪ [DSABook]: Глава 3
▪ [Aho, C. 228-247]: Глава 8. Сортировка – разделы 8.1 – 8.4 (простые схемы
сортировки, QuickSort, HeapSort)
▪ [Levitin, С. 169]: Сортировка слиянием
26
