Сортировка слиянием: различия между версиями
м (Добавлены категории) |
(Дописала табличку с примером и асимптотику) |
||
Строка 5: | Строка 5: | ||
<b>Пример</b>: | <b>Пример</b>: | ||
− | Пусть дан массив $a = [7, 0, 1, 3, 5, 2, 6, 4]$. | + | Пусть дан массив $a = [7, 0, 1, 3, 5, 2, 6, 4]$. В таблице ниже показано, в каком порядке будут происходить деления и как потом ответ будет собираться из отсортированных кусочков. |
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
− | ! | + | ! colspan="8" align="center" | Разделяем |
|- | |- | ||
− | | colspan="8" align="center" | 7 0 1 3 5 2 6 4 | + | | colspan="8" style="padding: 7px" align="center" | 7 0 1 3 5 2 6 4 |
|- | |- | ||
− | | colspan="4" align="center" | 7 0 1 3 || colspan="4" align="center" | 5 2 6 4 | + | | colspan="4" style="padding: 7px" align="center" | 7 0 1 3 || colspan="4" align="center" | 5 2 6 4 |
|- | |- | ||
− | |colspan="2" align="center" | 7 0 || colspan="2" align="center" | 1 3 ||colspan="2" align="center" | 5 2 || colspan="2" align="center" | 6 4 | + | |colspan="2" style="padding: 7px" align="center" | 7 0 || colspan="2" align="center" | 1 3 ||colspan="2" align="center" | 5 2 || colspan="2" align="center" | 6 4 |
|- | |- | ||
− | |7 || 0 || 1 || 3 || 5 || 2 || 6 || 4 | + | |style="padding: 7px" | 7 || 0 || 1 || 3 || 5 || 2 || 6 || 4 |
+ | |- | ||
+ | ! colspan="8" align="center" | Сливаем | ||
+ | |- | ||
+ | |colspan="2" style="padding: 7px" align="center"|0 7 || colspan="2" align="center"|1 3 || colspan="2" align="center"|2 5 || colspan="2" align="center"|4 6 | ||
+ | |- | ||
+ | |colspan="4" style="padding: 7px" align="center" | 0 1 3 7 || colspan="4" align="center" | 2 4 5 6 | ||
+ | |- | ||
+ | |colspan="8" style="padding: 7px" align="center" | 0 1 2 3 4 5 6 7 | ||
|} | |} | ||
===Функция Merge=== | ===Функция Merge=== | ||
− | Научимся <em>сливать</em> (объединять) два отсортированных массива. | + | Научимся <em>сливать</em> (объединять) два отсортированных массива. Для этого воспользуемся техникой <em>двух указателей</em>. |
+ | Пусть указатель $p_1$ стоит на некотором элементе первого массива, указатель $p_2$ на элементе второго массива. Будем поддерживать условие, что сейчас в отсортированный массив надо добавить либо элемент $p_1$, либо $p_2$. Какой именно - можно узнать, сравнив между собой эти два элемента. Если $a[p_1] \le b[p_2]$, то надо сложить в ответ $a[p_1]$ и сдвинуть $p_1$ на единицу вправо. Иначе делаем то же самое, но уже с $p_2$. | ||
+ | |||
+ | Количество смещений двух указателей не превосходит суммы длин двух массивов, поэтому такое слияние выполнится за $O(n + m)$, где $n, m$ - длины двух массивов. | ||
+ | |||
===Асимптотика=== | ===Асимптотика=== | ||
+ | Вычислим итоговое время работы MergeSort. | ||
+ | |||
+ | <b>Первое доказательство - наглядное</b> | ||
+ | |||
+ | Вспомним наш пример. Заметим, что каждый уровень состоит из одинакового количества элементов, на каждом уровне происходит серия операций merge, но суммарно на каждом уровне все они выполнятся за $O(n)$, так как время на merge линейно зависит от количества чисел в массивах. Теперь оценим количество уровней. На каждом размер сортируемого блока уменьшается в два раза, быть меньше единицы этот блок не может(иногда они вырождаются в пустые блоки, если длины массива - не степень двойки), поэтому уровней будет столько, сколько раз $n$ можно поделить на $2$. Это $\log n$. Тогда весь алгорритм работает за $O(n\log n)$. | ||
+ | |||
+ | <b>Второе доказательство - на формулах</b> | ||
+ | |||
+ | Пусть $T(n)$ - время, за которое мы умеем сортировать массив длины $n$. | ||
+ | Предположим, что $T(n) < Cn\log n$ для некоторой константы $C$. Теперь посмотрим, из чего складывается время сортировки: | ||
+ | |||
+ | $T(n) = 2T(n/2) + An$, где $A$ - какая-то константа, а $An$ - время на merge. | ||
+ | |||
+ | $T(n) < 2C\frac{n}{2}\log \frac{n}{2} + An =Cn\log \frac{n}{2} + An = n(C\log n - C + A) < Cn\log n$ | ||
+ | |||
+ | если $C > A$. Такие константы мы можем подобрать, поэтому доказана верхняя оценка $n\log n$ на время работы сортировки слиянием. | ||
{{Автор|Полина Романченко|Romanchenko}} | {{Автор|Полина Романченко|Romanchenko}} | ||
[[Категория:Конспект]] | [[Категория:Конспект]] | ||
[[Категория:Сортировки за логарифм]] | [[Категория:Сортировки за логарифм]] |
Версия 21:47, 16 августа 2019
Содержание
Сортировка слиянием (MergeSort)
Описание алгоритма
Допустим, нам надо отсортировать массив из $N$ чисел. Заметим, что если в нем только одно число($N = 1$), то массив уже отсортирован. Иначе предположим, что массивы размеров меньше $N$ мы уже умеем сортировать. Тогда сделаем следующее: разделим массив на две примерно равные части (просто делим пополам), отдельно отсортируем левую, отдельно отсортируем правую часть. Нам останется только объединить эти два массива и получить результат.
Пример:
Пусть дан массив $a = [7, 0, 1, 3, 5, 2, 6, 4]$. В таблице ниже показано, в каком порядке будут происходить деления и как потом ответ будет собираться из отсортированных кусочков.
Разделяем | |||||||
---|---|---|---|---|---|---|---|
7 0 1 3 5 2 6 4 | |||||||
7 0 1 3 | 5 2 6 4 | ||||||
7 0 | 1 3 | 5 2 | 6 4 | ||||
7 | 0 | 1 | 3 | 5 | 2 | 6 | 4 |
Сливаем | |||||||
0 7 | 1 3 | 2 5 | 4 6 | ||||
0 1 3 7 | 2 4 5 6 | ||||||
0 1 2 3 4 5 6 7 |
Функция Merge
Научимся сливать (объединять) два отсортированных массива. Для этого воспользуемся техникой двух указателей. Пусть указатель $p_1$ стоит на некотором элементе первого массива, указатель $p_2$ на элементе второго массива. Будем поддерживать условие, что сейчас в отсортированный массив надо добавить либо элемент $p_1$, либо $p_2$. Какой именно - можно узнать, сравнив между собой эти два элемента. Если $a[p_1] \le b[p_2]$, то надо сложить в ответ $a[p_1]$ и сдвинуть $p_1$ на единицу вправо. Иначе делаем то же самое, но уже с $p_2$.
Количество смещений двух указателей не превосходит суммы длин двух массивов, поэтому такое слияние выполнится за $O(n + m)$, где $n, m$ - длины двух массивов.
Асимптотика
Вычислим итоговое время работы MergeSort.
Первое доказательство - наглядное
Вспомним наш пример. Заметим, что каждый уровень состоит из одинакового количества элементов, на каждом уровне происходит серия операций merge, но суммарно на каждом уровне все они выполнятся за $O(n)$, так как время на merge линейно зависит от количества чисел в массивах. Теперь оценим количество уровней. На каждом размер сортируемого блока уменьшается в два раза, быть меньше единицы этот блок не может(иногда они вырождаются в пустые блоки, если длины массива - не степень двойки), поэтому уровней будет столько, сколько раз $n$ можно поделить на $2$. Это $\log n$. Тогда весь алгорритм работает за $O(n\log n)$.
Второе доказательство - на формулах
Пусть $T(n)$ - время, за которое мы умеем сортировать массив длины $n$. Предположим, что $T(n) < Cn\log n$ для некоторой константы $C$. Теперь посмотрим, из чего складывается время сортировки:
$T(n) = 2T(n/2) + An$, где $A$ - какая-то константа, а $An$ - время на merge.
$T(n) < 2C\frac{n}{2}\log \frac{n}{2} + An =Cn\log \frac{n}{2} + An = n(C\log n - C + A) < Cn\log n$
если $C > A$. Такие константы мы можем подобрать, поэтому доказана верхняя оценка $n\log n$ на время работы сортировки слиянием.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko