Cортировка слиянием с использованием O(1) дополнительной памяти — различия между версиями
| Строка 1: | Строка 1: | ||
| − | Научившись сливать с использованием <tex> O(1) </tex> дополнительной памяти и <tex> O(n) </tex> операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. | + | Научившись сливать с использованием <tex> O(1) </tex> дополнительной памяти и <tex> O(n) </tex> операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. Выполняем это для всех i от 2 до <tex> \lceil ln(n) \rceil </tex> |
==Алгоритм слияние == | ==Алгоритм слияние == | ||
| Строка 9: | Строка 9: | ||
=== Шаг 2 === | === Шаг 2 === | ||
| − | Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой, которая требует дополнительной памяти <tex> | + | Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой, которая требует дополнительной памяти <tex> O (1) </tex>, например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его, находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше |
<tex> \sqrt{n} </tex>. | <tex> \sqrt{n} </tex>. | ||
| Строка 50: | Строка 50: | ||
|} | |} | ||
| − | Потом, аналогично сольем вторую и | + | Потом, аналогично сольем вторую и третью группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента не больше <tex> \sqrt{n} </tex> то ему надо сдвинутся влево не больше чем на <tex> \sqrt{n} </tex> элементов, поэтому в конце не учитывая остаток массив будет отсортированный. |
Количество групп <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> . | ||
=== Шаг 4 === | === Шаг 4 === | ||
| − | Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> | + | Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти <tex> O(1) </tex> отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 сливаем задом на перед группы длиной s. |
Количество операций на этом шаге <tex> O(n) </tex>. | Количество операций на этом шаге <tex> O(n) </tex>. | ||
=== Шаг 5 === | === Шаг 5 === | ||
| − | + | Опять используя экономную по памяти, хотя и квадратичную сортировку отсортируем: | |
| − | + | ||
| + | 1. остаток и первую группу(после новой разметки на группы). | ||
| + | |||
| + | 2.последнюю группу. | ||
| + | |||
В результате массив будет отсортированным | В результате массив будет отсортированным | ||
Версия 07:52, 7 июня 2011
Научившись сливать с использованием дополнительной памяти и операций , оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером (за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. Выполняем это для всех i от 2 до
Содержание
Алгоритм слияние
На вход алгоритм получает массив который состоит из двух отсортированных кусков. На выходе алгоритм возвращает отсортированный массив. Он состоит из нескольких шагов.
Шаг 1
Разобьем наш массив на группы подряд идущих элементов длиной . Остаток трогать не будем. Найдем группу содержащую конец первого отсортированного куска. Поменяем ее с последней. Добавим последнюю группу в остаток.
Количество операций на этом шаге .
Шаг 2
Возьмем и отсортируем группы по первому элементу(в случае равенства по последнему). Это можно сделать любой квадратичной или более быстрой сортировкой, которая требует дополнительной памяти , например сортировка выбором. Следует заметить что после сортировки этих групп элементы которые стоять левее заданного и больше его, находились в противоположном куске отсортированного массива, также они находятся в пределах одной группы, поэтому количество инверсий для каждого элемента не больше .
Так как кусков количество операций на этом шаге .
Шаг 3
Попытаемся слить первую и вторую группу. Поменяем местами первую группу и часть остатка. И как в обычном слиянии пользуясь двумя указателями сливаем вторую группу и только что измененную часть остатка. Результат начинаем записывать с начала первой группы. Чтобы ничего не перетерлось вместо записи используем обмен элементов. Так как группы имеют одинаковую длину и между указателем на вторую группу и указателем на запись расстояние равно длине группы, то слияние произойдет корректно.
Пример : Пусть длины групп = 3 и x1<y1<x2<x3<y3, где первая группа x1,x2,x3 , а вторая y1,y2,y3.
| Номер операции | Массив до выполнения операции | Массив после выполнения операции |
|---|---|---|
| 1 | [x1,x2,x3,y1,y2,y3,a1,a2,a3] | [a1,a2,a3,y1,y2,y3,x1,x2,x3] |
| 2 | [a1,a2,a3,y1,y2,y3,x1,x2,x3] | [x1,a2,a3,y1,y2,y3,a1,x2,x3] |
| 3 | [x1,a2,a3,y1,y2,y3,a1,x2,x3] | [x1,y1,a3,a2,y2,y3,a1,x2,x3] |
| 4 | [x1,y1,a3,a2,y2,y3,a1,x2,x3] | [x1,y1,x2,a2,y2,y3,a1,a3,x3] |
| 5 | [x1,y1,x2,a2,y2,y3,a1,a3,x3] | [x1,y1,x2,y2,a2,y3,a1,a3,x3] |
| 6 | [x1,y1,x2,y2,a2,y3,a1,a3,x3] | [x1,y1,x2,y2,x3,y3,a1,a3,a2] |
Потом, аналогично сольем вторую и третью группу и так до последней группы. Так как после второго шага количество инверсий для каждого элемента не больше то ему надо сдвинутся влево не больше чем на элементов, поэтому в конце не учитывая остаток массив будет отсортированный.
Количество групп и каждое слияние работает за , поэтому количество операций на этом шаге .
Шаг 4
Пусть размер остатка s. Начиная с конца разобьем наш массив на подряд идущие группы длиной s. Используя квадратичную или более быструю сортировку, которая требует дополнительной памяти отсортируем подмассив длиной 2s, который находится в конце. На последних s местах будут находится s максимальных элементов. Оставшаяся часть представляет собой массив содержащий две отсортированные части, причем размер второй равен s. По аналогии с шагом 3 сливаем задом на перед группы длиной s.
Количество операций на этом шаге .
Шаг 5
Опять используя экономную по памяти, хотя и квадратичную сортировку отсортируем:
1. остаток и первую группу(после новой разметки на группы).
2.последнюю группу.
В результате массив будет отсортированным
Количество операций на этом шаге .
