Методы сортировок и их реализации. Беляева И.В - 26 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Мы
рассмотрим
сортировку
массивов
методом
слияний.
Формулируя
алгоритм,
будем
пользоваться
обозначением
отрезка
массива
theArray{firat
...last}.
Алгоритм
сортировки
методом
слияний
является
рекурсивным.
Его
эффективность
не
зависит
от
порядка
следования
элементов
в
исходном
массиве.
Допустим,
что
мы
разделили
массив
пополам,
рекурсивно
упорядочили
обе
половины,
а
затем
объединили
их
в
одно
целое,
как
показано
на
рис.
8.
На
рисунке
показано,
что
части
массива
<1, 4, 8>
и
<2,
3>
объединяются
в
массив
<1, 2, 3, 4, 8>.
В
ходе
слияния
элементы,
стоящие
в
разных
частях
массива,
попарно
сравниваются
друг
с
другом,
и
меньший
элемент
отправляется
во
временный
массив.
Этот
процесс
продолжается
до
тех
пор,
пока
не
будет
использована
одна
из
двух
частей
массива.
Теперь
достаточно
просто
скопировать
оставшиеся
элементы
во
временный
массив.
В
заключение
содержимое
временного
массива
копируется обратно
в
исходный
массив.
theArray:
'----_----'---_------'-
__
....L..--_----'--_------'
Делим
массив
пополам
Исходный
массив
'-------7---'---------'
Упорядочиваем
половины
массива
а
Объединяем
половины
а)]
<2.
поэтому
копируем
]
из
левой
половины
в
массив
theArray
б)4>2.по')'гому
копируем
2
из
правой
половины
в
массив
тпс
Аггау
в)4>3,поэтому
копируем
3
из
правой
половины
в
массив
theArray
г)Правая
половина
исчерпана.
остаток
левой
половины
копируем
А
.---_--.----L-----,-_=-------.-----:г
__
т--
__
'\=--,в
масси
в
tempArray
Временный
массив
тегпр
Аггау
Копируем
содержимое
временного
массива
назад
в
исходный
массив
theArray:
РИСУНОК
8.
Сортировка
методом
слияния
с
помощью
вспомагательного
массива
Хотя
в
результате
слияния
возникает
упорядоченный
массив,
остается
неясным,
как
выполняется
сортировка
на
предыдущих
этапах.
Сортировка
слиянием
выполняется
рекурсивно.
Ее
псевдокод
имеет
следующий
вид.
merge
..
чопи
тош
theArrcly.·lte}n./:l}·l·(l.~'.
in
./zrsl:
i11te~er,
i71
Ган),
il1Iep;er)
,//
Упорндоч
иеает
отрез
ок
1/
tJ1с1'4}··ГСl..-V
[fir.\'t
..
Га
..
\'I),
25

Страницы