Cортировка слиянием с использованием O(1) дополнительной памяти — различия между версиями
(→Слияние) |
|||
| Строка 1: | Строка 1: | ||
Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. | Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. | ||
| − | == | + | ==Алгоритм слияние == |
| + | На вход алгоритм получает массив который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Он состоит из нескольких шагов. | ||
=== Шаг 1 === | === Шаг 1 === | ||
| − | Разобьем наш массив на группы | + | Разобьем наш массив на группы подряд идущих элементов длиной <tex> \sqrt{n} </tex>. Остаток трогать не будем. Найдем группу содержащую конец первого отсортированного куска. Поменяем ее с последней. Добавим последнюю группу в остаток. |
| + | |||
| + | Количество операций на этом шаге <tex> O(n) </tex> | ||
=== Шаг 2 === | === Шаг 2 === | ||
| + | Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой которая требует дополнительной памяти не больше чем О(1), например сортировка выбором. | ||
| + | |||
| + | Так как кусков <tex> \sqrt{n} </tex> количество операций на этом шаге <tex> O(n) </tex> | ||
=Ссылки и литература= | =Ссылки и литература= | ||
*[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4] | *[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4] | ||
*[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA] | *[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA] | ||
Версия 06:19, 7 июня 2011
Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером (за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем.
Алгоритм слияние
На вход алгоритм получает массив который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Он состоит из нескольких шагов.
Шаг 1
Разобьем наш массив на группы подряд идущих элементов длиной . Остаток трогать не будем. Найдем группу содержащую конец первого отсортированного куска. Поменяем ее с последней. Добавим последнюю группу в остаток.
Количество операций на этом шаге
Шаг 2
Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой которая требует дополнительной памяти не больше чем О(1), например сортировка выбором.
Так как кусков количество операций на этом шаге
