Сортировка слиянием — различия между версиями
Tiss93 (обсуждение | вклад) (→Восходящая сортировка слиянием) |
Tiss93 (обсуждение | вклад) (→Слияние двух массивов) |
||
Строка 15: | Строка 15: | ||
===Слияние двух массивов=== | ===Слияние двух массивов=== | ||
− | + | У нас есть два массива <tex>A</tex> и <tex>B</tex>. Нам надо получить массив <tex>C</tex> размером <tex>sizeof(A) + sizeof(B)</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок. | |
[[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]] | [[Файл:Mergearr.png|right|300px|thumb|Пример работы процедуры слияния.]] | ||
Версия 19:55, 31 мая 2012
Содержание
Описание
Сортировка слиянием — алгоритм сортировки. Он был предложен Джоном фон Нейманом в 1945 году.
Это стабильный алгоритм, использующий
дополнительной памяти и времени.Принцип работы
Этот алгоритм использует принцип «разделяй и властвуй». Этот принцип заключается в том, что исходная задача разбивается на подзадачи меньшего размера, а потом они решаются рекурсивным методом или же конкретно, если их размер мал. Потом из решения объединяются и получается решение основной (исходной) задачи.
Для процедуры слияния требуется два отсортированных массива. Зная, что массив из одного элемента по определению отсортирован, мы можем разработать такой алгоритм:
- Массив разбивается на половинки до тех пор, пока размер "половинки" не станет равным единице.
- Каждая из получившихся частей сортируется отдельно. Или же это просто одиночный элемент.
- "Сливаем" два упорядоченных массива в один.
Слияние двух массивов
У нас есть два массива
и . Нам надо получить массив размером . Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.Алгоритм слияния формально можно записать следующим образом:
// слияние двух массивов с помощью временного merge(array a, int left, int middle, int right) // left - левая граница, right - правая, middle - середина array b = a[middle + 1, right]; i = left, j = middle + 1, k = 0; array temp; while i <= middle and j <= right temp[k++] = (a[j] < b[i]) ? a[j++] : b[i++]; while i <= middle temp[k++] = b[i++]; while j <= right temp[k++] = a[j++]; for (int t = 0; t != k; t++) a[t] = temp[t] // в конце a[1..k] это будет отсортированный массив
Рекурсивный алгоритм
Функция сортирует участок массива от элемента с номером left до элемента с номером right:
right и left — правая и левая граница массива, middle — середина.
Условие выхода — если массив стал состоять из 1 элемента.
sort(array a, int left, int right) middle = right / 2 if middle == right return sort(a, left, middle) sort (a, middle + 1, right) merge(array a, left, middle, right)
Пример работы алгоритма показан на рисунке:
Восходящая сортировка слиянием
Помимо рекурсивного алгоритма существует и альтернативный. Пример работы алгоритма показан на рисунке:
- Выделим память размером с занимаемой памяти исходного массива.
- Попарно сравним элементы, записывая во временную память.
- Поменяем указатели временного и исходного массива.
- Выполним слияние "кусочков" размером два.
- Повторяем до тех пор, пока не сделаем единый кусок.
Процедуру слияния надо будет изменить, так, что-бы она записывала результат в результирующий массив (mas1)
sort(array mas, int elementsAmount) array mas1 = new array[elementsAmount]; for(int size = 1; size < elementsAmount; size *= 2) int start = 0; while ((start + size) < elementsAmount) merge(mas + start, mas + start, mas + start + size, mas + start + size + min(size, elementsAmount - start - size)); start += size * 2; while (start < elementsAmount) mas1[start] = mas[start]; ++start; array temp = mas1; mas1 = mas; mas = temp;
Время работы
Чтобы оценить время работы этого алгоритма, составим рекуррентное соотношение. Пускай
( — это время, необходимое на то, чтобы слить два массива). Распишем это соотношение:
Осталось оценить
. Мы знаем, что , а значит . Уравнение примет вид . Так как — константа, то .