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

UptoLike

ВУЗ: 

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

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

Рубрика: 

first
mid
last
l-t-h-еА-гг-а-у:-~Г--с-л-и-я-н-и-:е-п-о-л-о-в-и-н-:
----'1
а б
а)
1
<4"\
поэтому
копируем
1
из
подмассива
theArray[first..mid]
в
массив
tempArray
б)
2<4~
поэтому
копируем
2
из
подмассива
theArray[first..mid]
в
массив
tempArray
в)
8>4.,
поэтому
копируем
4
из
подмассива
theArray[mid+l ..last]
в
массив
tempArray
г)
8>5,
поэтому
копируем
5
из
подмассива
theArray[mid+l ..last]
в
массив
tempArray
tempArray:
д)
8>6"\
поэтому
копируем
6
из
подмассива
theArray[mid+l ..last]
в
массив
tempArray
ж)
Подмассив
theArray[mid+1..last]
исчерпан,
поэтому
копируем
8
в
массив
tempArray
РИСУНОК
10.
Наихудший
случай
на
этапе
слияния
в
ФУНКЦИИ
mergesort
выполняются
два
рекурсивных
вызова.
Как
показано
на
рис.П,
если
исходный
вызов
функции
mergesort
принадлежит
нулевому
уровню,
то
на
первом
уровне
возникают
два
рекурсивных
вызова.
Затем
каждый
из
этих
вызовов
порождает
еще
два
рекурсивных
вызова
второго
уровня
и
т.д.
Сколько
уровней
рекурсии
возникнет?
Попробуем
их
подсчитать.
8
Уровень
О
4
Уровень
1
Уровень
О
Уровень
О
1 1
Уровень
О:
вызов
функции
mergesort
для
8
элементов
Уровень
1:
вызов
функции
mergesort
для
4
элементов
Уровень
О:
вызов
функции
mergesort
для
2
элементов
Уровень
О:
вызов
функции
mergesort
для
1
элемента
Рисунок
11.
Уровни
рекурсивных
вызовов
функции
mergesort
при
сортировки
массива,
состоящего
из
восьми
элементов
Каждый
вызов
функции
mergesort
делит
массив
пополам.
На
первом
этапе
исходный
массив
оказывается
разделенным
на
две
части.
При
29

Страницы