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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм слияние)
(Алгоритм слияния)
Строка 2: Строка 2:
  
 
==Алгоритм слияния ==
 
==Алгоритм слияния ==
[[Файл:Freememmerge.png|right|380px|thumb|Пример работы алгоритма слияния]]
+
[[Файл:Freememorymerge.png|right|380px|thumb|Пример работы алгоритма слияния]]
 
На вход алгоритм получает массив, который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Алгоритм состоит из нескольких шагов.
 
На вход алгоритм получает массив, который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Алгоритм состоит из нескольких шагов.
 
=== Шаг 1 ===
 
=== Шаг 1 ===

Версия 00:57, 16 июня 2011

После того, как мы научились сливать с использованием [math] O(1) [/math] дополнительной памяти и [math] O(n) [/math] операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером [math] 2^i [/math](за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пары, то просто ничего не делаем. Выполняем это для всех i от [math] 2 [/math] до [math] \lceil ln(n) \rceil [/math]

Алгоритм слияния

Файл:Freememorymerge.png
Пример работы алгоритма слияния

На вход алгоритм получает массив, который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Алгоритм состоит из нескольких шагов.

Шаг 1

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

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

Шаг 2

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

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

Шаг 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].

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