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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
  
  
Разобьем наш массив на блоки подряд идущих элементов длиной <tex> \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|center|525px]]
Строка 15: Строка 15:
  
  
Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует дополнительной памяти <tex> O (1) </tex>. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором (selection sort)]].  
+
Отсортируем блоки по возрастанию по первому элементу (если первые элементы равны, тогда по последнему). Для этого подойдет любая квадратичная или более быстрая сортировка, которая требует <tex> O (1) </tex> дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит [[Сортировка выбором|сортировка выбором (selection sort)]].  
  
 
Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом  шаге <tex> O(n) </tex>.
 
Так как блоков <tex> \sqrt{n} </tex>, то количество операций на этом  шаге <tex> O(n) </tex>.
Строка 21: Строка 21:
 
[[Файл:Merge_O(1)_4.png|center|525px]]
 
[[Файл:Merge_O(1)_4.png|center|525px]]
  
 +
 +
Пользуясь буфером обмена, последовательно сольем пары соседних блоков. В результате мы получим, что первые <tex>len \cdot (cnt - 1)</tex> элементов исходного массива отсортированы.
 +
 +
[[Файл:Merge_O(1)_5.png|center|525px]]
 +
 +
 +
== Использование буфера обмена ==
 +
Попытаемся слить первый и второй блок. Поменяем местами первый блок с буфером обмена. И, как в обычном слиянии, пользуясь двумя указателями, сливаем вторую группу и только что измененный буфер. Результат начинаем записывать с начала первой группы. Чтобы не потерять данные, вместо записи используем обмен элементов. Так как блоки имеют одинаковую длину, и между указателем на второй блок и указателем на запись расстояние равно длине блока, то слияние произойдет корректно.
 +
 +
[[Файл:Merge_O(1)_buffer.png|center|355px]]
  
 
=== Шаг 3 ===
 
=== Шаг 3 ===

Версия 01:49, 29 мая 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] дополнительной памяти. Здесь нам выгодно использовать алгоритм, линейный по числу обменов, т.е. подходит сортировка выбором (selection sort).

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

Merge O(1) 4.png


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

Merge O(1) 5.png


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

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

Merge O(1) buffer.png

Шаг 3

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

Пример : Пусть длины групп равны трем и [math] x_1\lt y_1\lt x_2\lt x_3\lt y_3 [/math], где первая группа [math] x_1,x_2,x_3 [/math] , а вторая [math] y_1,y_2,y_3. [/math]

Номер операции Массив до выполнения операции Массив после выполнения операции
1 [math][x_1,x_2,x_3,y_1,y_2,y_3,a_1,a_2,a_3] [/math] [math][a_1,a_2,a_3,y_1,y_2,y_3,x_1,x_2,x_3] [/math]
2 [math][a_1,a_2,a_3,y_1,y_2,y_3,x_1,x_2,x_3] [/math] [math][x_1,a_2,a_3,y_1,y_2,y_3,a_1,x_2,x_3] [/math]
3 [math][x_1,a_2,a_3,y_1,y_2,y_3,a_1,x_2,x_3] [/math] [math][x_1,y_1,a_3,a_2,y_2,y_3,a_1,x_2,x_3] [/math]
4 [math][x_1,y_1,a_3,a_2,y_2,y_3,a_1,x_2,x_3] [/math] [math][x_1,y_1,x_2,a_2,y_2,y_3,a_1,a_3,x_3] [/math]
5 [math][x_1,y_1,x_2,a_2,y_2,y_3,a_1,a_3,x_3] [/math] [math][x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3] [/math]
6 [math][x_1,y_1,x_2,y_2,a_2,y_3,a_1,a_3,x_3] [/math] [math][x_1,y_1,x_2,y_2,x_3,y_3,a_1,a_3,a_2] [/math]

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

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

Шаг 4

Пусть размер остатка [math] s [/math]. Начиная с конца, разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти [math] O(1) [/math], отсортируем подмассив длиной [math] 2s [/math], который находится в конце. На последних [math] s [/math] местах будут находиться s максимальных элементов. Оставшаяся часть представляет собой массив, содержащий две отсортированные части, причем размер второй равен [math] s [/math]. По аналогии с шагом 3 в обратном порядке сливаем группы длиной [math] s [/math].

Количество операций на этом шаге [math] O(n) [/math].

Шаг 5

Опять, используя экономную по памяти, хотя и квадратичную, сортировку, отсортируем:

  1. остаток и первую группу.
  2. последнюю группу.

Не стоит забывать, что после новой разметки остаток находится в начале, а не в конце.

В результате массив будет отсортированным

Количество операций на этом шаге [math] O(n) [/math].

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