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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 
На вход алгоритм получает массив, который состоит из двух отсортированных частей:
 
На вход алгоритм получает массив, который состоит из двух отсортированных частей:
  
[[Файл:Merge_O(1)_1.png|center|525px]]
+
[[Файл:Merge_O(1)_1.png|left|525px]]
 +
 
 +
 
  
  
 
Разобьем наш массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем.  
 
Разобьем наш массив на <tex>cnt</tex> подряд идущих блоков длиной <tex>len = \lfloor \sqrt{n} \rfloor </tex>. Остаток трогать не будем.  
  
[[Файл:Merge_O(1)_2.png|center|525px]]
+
[[Файл:Merge_O(1)_2.png|left|525px]]
 +
 
 +
 
  
  
 
Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.  
 
Найдем блок, содержащий конец первой отсортированной части. Поменяем его с последним блоком. В дальнейшем будем использовать его как буфер обмена.  
  
[[Файл:Merge_O(1)_3.png|center|525px]]
+
[[Файл:Merge_O(1)_3.png|left|525px]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
Строка 18: Строка 31:
 
Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом  шаге <tex> O(n) </tex>.
 
Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом  шаге <tex> O(n) </tex>.
  
[[Файл:Merge_O(1)_4.png|center|525px]]
+
[[Файл:Merge_O(1)_4.png|left|525px]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
Строка 25: Строка 47:
 
Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.
 
Количество блоков <tex> \sqrt{n} </tex> и каждое слияние работает за <tex> О O(\sqrt{n}) </tex> , поэтому количество операций на этом шаге <tex> O(n) </tex>.
  
[[Файл:Merge_O(1)_5.png|center|525px]]
+
[[Файл:Merge_O(1)_5.png|left|525px]]
 +
 
 +
 
  
  
Строка 32: Строка 56:
 
Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>.
 
Так как <tex>S < 2 \sqrt{n}</tex>, то сортировка пройдет за <tex>O(n)</tex>.
  
[[Файл:Merge_O(1)_6.png|center|525px]]
+
[[Файл:Merge_O(1)_6.png|left|525px]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
 
Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.
 
Теперь на последних <tex> S </tex> местах будут находиться <tex> S </tex> максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен <tex> S </tex>. По аналогии с тем что делали раньше, только в обратную сторону, отсортируем оставшуюся часть, разделив ее на блоки длиной <tex>S</tex>, используя последние <tex>S</tex> как буфер обмена. Не забудем после отсортировать буфер обмена.
  
[[Файл:Merge_O(1)_7.png|center|525px]]
+
[[Файл:Merge_O(1)_7.png|left|525px]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
  
Строка 45: Строка 84:
 
Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.
 
Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем второй блок и только что измененный буфер. Результат начинаем записывать с начала первого блока. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.
  
[[Файл:Merge_O(1)_buffer.png|center|355px]]
+
[[Файл:Merge_O(1)_buffer.png|left|355px]]
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
 +
 
  
 
== Ссылки и литература ==
 
== Ссылки и литература ==

Версия 20:38, 31 мая 2012

На вход алгоритм получает массив, который состоит из двух отсортированных частей:

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






Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует [math] O (1) [/math] дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит сортировка выбором.

Так как блоков [math] \sqrt{n} [/math], то количество операций на этом шаге [math] O(n) [/math].

Merge O(1) 4.png






Пользуясь буфером обмена, последовательно сольем пары соседних блоков (процесс слияния блоков описан ниже) [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]. В результате мы получим, что первые [math]len \cdot (cnt - 1)[/math] элементов исходного массива отсортированы.

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

Merge O(1) 5.png



[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















Ссылки и литература