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

UptoLike

ВУЗ: 

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

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

Рубрика: 

элемента
отрезка
S2.
В
функции
mergeSort,
наоборот,
перед
рекурсивными
вызовами
никакая
работа
не
выполняется.
Алгоритм
упорядочивает
каждую
из
частей
массива,
постоянно
учитывая
отношения
между
элементами
обеих
частей.
По
этой
причине
алгоритм
должен
объединять
две
половины
массива
после
выполнения
рекурсивных
вызовов.
Анализ.
Основная
работа
в
алгоритме
quicksort
выполняется
на
этапе
разбиения
массива.
Анализируя
каждый
элемент,
принадлежащий
неопределенной
части,
необходимо
сравнивать
элемент
theArray
{firstunknown]
с
опорным
и
помещать
его
либо
в
отрезок
8/,
либо
в
отрезок
82.
Один
из
отрезков
8/,
или
S2
может
быть
пустым;
например,
если
опорным
элементом
является
наименьший
элемент
отрезка,
множество
SI
останется
пустым.
Это
происходит
в
наихудшем
случае,
поскольку
размер
отрезка
82
при
каждом
вызове
функции
quicksort
уменьшается
только на
единицу.
Таким
образом,
в
этой
ситуации
будет
выполнено
максимальное
количество
рекурсивных
вызовов
функции
quicksort.
Исходный
массив
Опорный
Неопределенная
часть
элемент
5
I\I~I
Опорный
элемент
82
Неопределенная
часть
Множество
81
пусто
5 6
.t;:i\~
Опорный
Неопределенная
часть
элемент
7
····:·····::~ill::I
...
:.:.:.:,:.·.i,:
..•.
:.:,.:!,:.'.;.:.I
:;.:::.:.:•..•.
...
i,.....•:.I.•.
:::!:;:
~~~(~{
. .
6
Множество
51
пусто
5
Опорный
5
6
6
5
Опорный
элемент
элемент
Первое
разбиение
Множество
81
пусто
Множество
51
пусто
4
сравнения,
Оперестановок
Рисунок
19
..
Разбиение
массива
в
алгоритме
qиiсksоrt
в
наихудшем
варианте
При
следующем
рекурсивном
вызове
функции
quicksort
функция
partition
просмотрит
n-l
элемент.
Чтобы
распределить
их
по
отрезкам,
понадобится
n-2
сравнений.
Поскольку
размер
отрезка,
рассматриваемого
функцией
quicksort,
на
каждом
уровне
рекурсии
уменьшается
только
на
41

Страницы