Cортировка слиянием с использованием O(1) дополнительной памяти — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Ссылки и литература)
м (rollbackEdits.php mass rollback)
 
(не показано 36 промежуточных версий 9 участников)
Строка 1: Строка 1:
После того, как мы научились сливать с использованием <tex> O(1) </tex> дополнительной памяти и <tex> O(n) </tex> операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пары, то просто ничего не делаем. Выполняем это для всех i от <tex> 2 </tex> до <tex> \lceil ln(n) \rceil </tex>
+
{{boring}}
 +
В конспекте содержится несколько ошибок, которые никто не исправлял уже лет 5, половины доказательств нету и вообще это стоит переписать. Если хотите заимплементить корректный алгоритм, придется дополнительно подумать головой. Алсо, про "сравнение в реальных условиях" - бред, по времени этот алгоритм в несколько раз медленнее std::sort. ~[[Участник:Yurik|Yurik]]~, 2017
  
==Алгоритм слияния ==
+
<br/>
[[Файл:Freememorymergesort.png|right|380px|thumb|Пример работы алгоритма слияния]]
 
На вход алгоритм получает массив, который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Алгоритм состоит из нескольких шагов.
 
=== Шаг 1 ===
 
Разобьем наш массив на группы подряд идущих элементов длиной <tex> \sqrt{n} </tex>. Остаток трогать не будем. Найдем группу, содержащую конец первого отсортированного куска. Поменяем ее с последней. Добавим последнюю группу в остаток.
 
  
Количество операций на этом  шаге <tex> O(n) </tex>.
+
На вход алгоритм получает массив, который состоит из двух отсортированных частей. Нам необходимо за <tex>O(1)</tex> дополнительной памяти и <tex>O(n)</tex> времени получить отсортированный массив.<br>
 +
В реализации алгоритм весьма громоздкий. Но сравнение в реальных условиях реализации на C++ (на массивах длиной до <tex>10^8</tex>) показало, что по числу сравнений алгоритм выигрывает у qsort примерно 10%, а по общему времени работы – от <tex>1.2</tex> до <tex>1.3</tex> раз.
  
=== Шаг 2 ===
+
== Алгоритм ==
Возьмем и отсортируем группы по первому элементу (в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой, которая требует дополнительной памяти <tex> O (1) </tex>, например сортировка выбором. Следует заметить, что, после сортировки этих групп, элементы, которые стоят левее заданного и больше его, находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше
+
У нас есть массив, который состоит из двух отсортированных частей:
<tex> \sqrt{n} </tex>.
 
  
Так как кусков <tex> \sqrt{n} </tex>, количество операций на этом  шаге <tex> O(n) </tex>.
+
[[Файл:Merge_O(1)_1.png|525px]]
  
=== Шаг 3 ===
+
Разобьем наш массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем.  
Попытаемся слить первую и вторую группу. Поменяем местами первую группу и часть остатка. И, как в обычном слиянии, пользуясь двумя указателями, сливаем вторую группу и только что измененную часть остатка. Результат начинаем записывать с начала первой группы. Чтобы ничего не перезаписалось, вместо записи используем обмен элементов. Так как группы имеют одинаковую длину, и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректно.
 
  
Пример :
+
[[Файл:Merge_O(1)_2.png|525px]]
Пусть длины групп равны трем и <tex> x_1<y_1<x_2<x_3<y_3 </tex>, где первая группа  <tex> x_1,x_2,x_3 </tex> , а вторая <tex> y_1,y_2,y_3. </tex>
 
  
{| border="1"
+
Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.
!Номер операции
 
!Массив до выполнения операции
 
!Массив после выполнения операции
 
|-
 
|1
 
|<tex>[x_1,x_2,x_3,y_1,y_2,y_3,a_1,a_2,a_3] </tex>
 
|<tex>[a_1,a_2,a_3,y_1,y_2,y_3,x_1,x_2,x_3] </tex>
 
|-
 
|2
 
|<tex>[a_1,a_2,a_3,y_1,y_2,y_3,x_1,x_2,x_3] </tex>
 
|<tex>[x_1,a_2,a_3,y_1,y_2,y_3,a_1,x_2,x_3] </tex>
 
|-
 
|3
 
|<tex>[x_1,a_2,a_3,y_1,y_2,y_3,a_1,x_2,x_3] </tex>
 
|<tex>[x_1,y_1,a_3,a_2,y_2,y_3,a_1,x_2,x_3] </tex>
 
|-
 
|4
 
|<tex>[x_1,y_1,a_3,a_2,y_2,y_3,a_1,x_2,x_3] </tex>
 
|<tex>[x_1,y_1,x_2,a_2,y_2,y_3,a_1,a_3,x_3] </tex>
 
|-
 
|5
 
|<tex>[x_1,y_1,x_2,a_2,y_2,y_3,a_1,a_3,x_3] </tex>
 
|<tex>[x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3] </tex>
 
|-
 
|6
 
|<tex>[x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3] </tex>
 
|<tex>[x_1,y_1,x_2,y_2,x_3,y_3,a_1,a_3,a_2] </tex>
 
|}
 
  
Потом аналогично сольем вторую и третью группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента  не больше <tex> \sqrt{n} </tex>, то ему надо сдвинутся влево не больше, чем на <tex> \sqrt{n} </tex> элементов, поэтому в конце, не учитывая остаток, массив будет отсортированный.
+
[[Файл:Merge_O(1)_3.png|525px]]
  
Количество групп <tex> \sqrt{n} </tex>, и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex> .
+
Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему).  
  
=== Шаг 4 ===
+
[[Файл:Merge_O(1)_4.png|525px]]
Пусть размер остатка <tex> s </tex>. Начиная с конца, разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> O(1) </tex>, отсортируем подмассив длиной <tex> 2s </tex>, который находится в конце. На последних <tex> s </tex> местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен<tex> s </tex>. По аналогии с шагом 3 в обратном порядке сливаем группы длиной <tex> s </tex>.  
 
  
Количество операций на этом  шаге <tex> O(n) </tex>.
+
Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Для сохранения линейной асимптотики надо использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором]]. Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом  шаге <tex> O(n) </tex>.
  
=== Шаг 5 ===
+
Следует заметить, что, после сортировки этих блоков, элементы, которые стоят левее заданного и больше его, находились в противоположной части отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>.
Опять, используя экономную по памяти, хотя и квадратичную, сортировку, отсортируем:
 
  
#остаток и первую группу.  
+
Пользуясь буфером обмена, последовательно сольем пары соседних блоков <tex>([0, ~ len - 1]</tex> и <tex>[len, ~ 2 ~ len - 1],</tex> потом <tex>[len, ~ 2 ~ len - 1]</tex> и <tex>[2 ~ len, ~ 3 ~ len - 1],</tex> и т.д.<tex>)</tex>.
#последнюю группу.
 
  
Не стоит забывать, что после новой разметки остаток находится в начале, а не в конце.
+
Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно (пример использования буфера обмена приведен ниже).
  
В результате массив будет отсортированным
+
[[Файл:Merge_O(1)_5.png|525px]]
  
Количество операций на этом шаге <tex> O(n) </tex>.
+
Так как после предыдущего шага количество инверсий для каждого элемента не больше <tex>\sqrt{n}</tex>, то ему надо сдвинуться влево не больше, чем на <tex>\sqrt{n}</tex> элементов, поэтому в результате мы получим, что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы. Количество блоков <tex> \sqrt{n} </tex> и каждое слияние  работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.
  
=Ссылки и литература=
+
<tex>S</tex> {{---}} размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку, которая требует  <tex> O(1) </tex> дополнительной памяти, отсортируем подмассив длиной <tex> 2S </tex>, который находится в конце.
*[http://e-maxx.ru/bookz/files/knuth_3.djvu Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4]
+
 
*[http://pastebin.com/hN2SnEfP  Реализация алгоритма на JAVA]
+
Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>.
 +
 
 +
[[Файл:Merge_O(1)_6.png|525px]]
 +
 
 +
Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.
 +
 
 +
[[Файл:Merge_O(1)_7.png|525px]]
 +
 
 +
В результате мы получили отсортированный исходный массив.
 +
 
 +
== Пример использования буфера обмена ==
 +
 
 +
[[Файл:Merge_O(1)_buffer.png|355px]]
 +
 
 +
== Источники информации ==
 +
*[http://habrahabr.ru/post/138146/ Habrahabr {{---}}Сортировка слиянием без использования дополнительной памяти ]
 +
*[http://e-maxx.ru/bookz/files/knuth_3.djvu Д.Е.Кнут {{---}} Искусство программирования (том 3) упр 18 к разделу 5.2.4]
 +
*[http://pastebin.com/hN2SnEfP PASTEBIN {{---}} Реализация алгоритма на JAVA]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировки]]

Текущая версия на 19:33, 4 сентября 2022

nothumb
Эта статья сделана из уныния и отчаяния.
Сделайте с ней что-нибудь.
Пожалуйста.

В конспекте содержится несколько ошибок, которые никто не исправлял уже лет 5, половины доказательств нету и вообще это стоит переписать. Если хотите заимплементить корректный алгоритм, придется дополнительно подумать головой. Алсо, про "сравнение в реальных условиях" - бред, по времени этот алгоритм в несколько раз медленнее std::sort. ~Yurik~, 2017


На вход алгоритм получает массив, который состоит из двух отсортированных частей. Нам необходимо за [math]O(1)[/math] дополнительной памяти и [math]O(n)[/math] времени получить отсортированный массив.
В реализации алгоритм весьма громоздкий. Но сравнение в реальных условиях реализации на C++ (на массивах длиной до [math]10^8[/math]) показало, что по числу сравнений алгоритм выигрывает у qsort примерно 10%, а по общему времени работы – от [math]1.2[/math] до [math]1.3[/math] раз.

Алгоритм

У нас есть массив, который состоит из двух отсортированных частей:

Merge O(1) 1.png

Разобьем наш массив на [math]cnt[/math] подряд идущих блоков длиной [math]len = \lfloor \sqrt{n} \rfloor [/math]. Остаток трогать не будем.

Merge O(1) 2.png

Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.

Merge O(1) 3.png

Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему).

Merge O(1) 4.png

Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует [math] O (1) [/math] дополнительной памяти. Для сохранения линейной асимптотики надо использовать алгоритм, линейный по числу обменов, т.е. подходит сортировка выбором. Так как блоков [math] \sqrt{n} [/math], то количество операций на этом шаге [math] O(n) [/math].

Следует заметить, что, после сортировки этих блоков, элементы, которые стоят левее заданного и больше его, находились в противоположной части отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше [math]\sqrt{n}[/math].

Пользуясь буфером обмена, последовательно сольем пары соседних блоков [math]([0, ~ len - 1][/math] и [math][len, ~ 2 ~ len - 1],[/math] потом [math][len, ~ 2 ~ len - 1][/math] и [math][2 ~ len, ~ 3 ~ len - 1],[/math] и т.д.[math])[/math].

Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно (пример использования буфера обмена приведен ниже).

Merge O(1) 5.png

Так как после предыдущего шага количество инверсий для каждого элемента не больше [math]\sqrt{n}[/math], то ему надо сдвинуться влево не больше, чем на [math]\sqrt{n}[/math] элементов, поэтому в результате мы получим, что первые [math]len \cdot (cnt - 1)[/math] элементов исходного массива отсортированы. Количество блоков [math] \sqrt{n} [/math] и каждое слияние работает за [math] О O(\sqrt{n}) [/math] , поэтому количество операций на этом шаге [math] O(n) [/math].

[math]S[/math] — размер остатка вместе с буфером. Используя квадратичную или более быструю сортировку, которая требует [math] O(1) [/math] дополнительной памяти, отсортируем подмассив длиной [math] 2S [/math], который находится в конце.

Так как [math]S \lt 2 \sqrt{n}[/math], то сортировка пройдет за [math]O(n)[/math].

Merge O(1) 6.png

Теперь на последних [math] S [/math] местах будут находиться [math] S [/math] максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен [math] S [/math]. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной [math]S[/math], используя последние [math]S[/math] как буфер обмена. Не забудем после отсортировать буфер обмена.

Merge O(1) 7.png

В результате мы получили отсортированный исходный массив.

Пример использования буфера обмена

Merge O(1) buffer.png

Источники информации