46
правок
Изменения
Новая страница: «=Сортировка слиянием= [[Файл:Merge sort animation2.gif|right|380px|thumb|Действие алгоритма на примере сортиро…»
=Сортировка слиянием=
[[Файл:Merge sort animation2.gif|right|380px|thumb|Действие алгоритма на примере сортировки случайных точек.]]
'''Сортировка слиянием''' — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов).Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно. Этот алгоритм был предложен Джоном фон Нейманом в 1945 году.
=Принцип работы=
Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
*Сортируемый массив разбивается на две части примерно одинакового размера;
*Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
*Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
=Слияние 2-х массивов=
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|center|380px|thumb|Пример работы процедуры слияния.]]
<br>
Алгоритм слияния формально можно записать следующим образом:
[[Файл:Merge1.png|left|380px|thumb]]
<tex>a\leftarrow 0; b\leftarrow 0 </tex> <br>
<tex>While</tex> <tex>a < N_a</tex> <tex>and</tex> <tex> b < N_b</tex> <br>
<tex>if</tex> <tex>A[a] <B[b]</tex>
[[Файл:Merge sort animation2.gif|right|380px|thumb|Действие алгоритма на примере сортировки случайных точек.]]
'''Сортировка слиянием''' — вероятно, один из самых простых алгоритмов сортировки (среди «быстрых» алгоритмов).Сортировка слиянием — стабильный алгоритм сортировки. Это означает, что порядок «равных» элементов не изменяется в результате работы алгоритма. В некоторых задачах это свойство достаточно важно. Этот алгоритм был предложен Джоном фон Нейманом в 1945 году.
=Принцип работы=
Эта сортировка — хороший пример использования принципа «разделяй и властвуй». Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
Для решения задачи сортировки эти три этапа выглядят так:
*Сортируемый массив разбивается на две части примерно одинакового размера;
*Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;
*Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
=Слияние 2-х массивов=
Допустим, у нас есть два отсортированных массива А и B размерами <tex>N_a </tex> и <tex>N_b </tex> соответственно, и мы хотим объединить их элементы в один большой отсортированный массив C размером <tex>N_a + N_b </tex> . Для этого можно применить процедуру слияния, суть которой заключается в повторяющемся «отделении» элемента, наименьшего из двух имеющихся в началах исходных массивов, и присоединении этого элемента к концу результирующего массива. Элементы мы переносим до тех пор, пока один из исходных массивов не закончится. После этого оставшийся «хвост» одного из входных массивов дописывается в конец результирующего массива. Пример работы процедуры показан на рисунке:
[[Файл:Mergearr.png|center|380px|thumb|Пример работы процедуры слияния.]]
<br>
Алгоритм слияния формально можно записать следующим образом:
[[Файл:Merge1.png|left|380px|thumb]]
<tex>a\leftarrow 0; b\leftarrow 0 </tex> <br>
<tex>While</tex> <tex>a < N_a</tex> <tex>and</tex> <tex> b < N_b</tex> <br>
<tex>if</tex> <tex>A[a] <B[b]</tex>
