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

UptoLike

ВУЗ: 

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

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

Рубрика: 

}
//
Конец
функции
ратпоп
void
qиiсksоrt
(DataType theArray {),
int
jirst,
int
last)
!/
-----------------------------------------------------------------------------
1/
Упорядочивает
элементы
массива
в
возрастающем
порядке.
//
Предусловие:
отрезок
theArray [first.. last} -
массив.
//
Постусловие:
массив
theArray[first..last}
упорядочен.
//
Вызываемая
функция:
partition.
!/
-----------------------------------------------------------------------------
{
int
pivotlndex;
if
(first < last)
(
//
Создаем
разбиение:
8L
опорный
элемент.
S2
partition(theArray,
Lfirst,
last, pivotlndex):
//
Упорядочиваем
множества
8/
и
82
qиiсksогt(thеАrrау,
jirst, pivotlndex-l):
qиiсksоrt(thеАrгау,
pivotlndex+l, last):
}
//
Конец
оператора
~r
}//
Конец
функции
qиiсksоrt
Дальнейший
анализ
покажет,
что
желательно
избегать
такого
выбора
опорного
элемента,
при
котором
множество
Sj
или
S2
оказываются
пустыми.
Лучше
всего
выбирать
опорный
элемент
поближе
к
медиане
массива.
Алгоритмы
guickSort
и
mergeSort
«близки
по
духу»,
хотя
в
алгоритме
guickSort
основная
работа
выполняется
до
рекурсивных
вызовов,
а
в
алгоритме
mergeSort
-
после.
Схему
псевдокода
алгоритма
guickSort
можно
записать
так.
qиiсksоrt
(inout theArray: ItemArray,
injirst
.-integer,
т
last: integer)
if
(first
<
last)
{
Подготовить
массив
theArray
к
рекурсивным
вызовам
qиiсksогt
(отрезок
..
Sl
массива
theArray)
qиiсksогt
(отрезок
82
массива
theArray)
}
//
Конец
оператора
ij'
В
то
же
время
общая
схема
алгоритма
mergeSol-еt
выглядит
следующим
образом.
•
mergesort
(inout
theA1
Aray:
ItemArray,
[п
jirst:
integer,
in
Zast:
integer)
If
(first
< Zast,·
{
mergesort
(левая
часть
массива
(пе
Апау)
тепгезоп
(правая
часть
массива
(пе
Ап
ау)
Собрать
массив,
полученный
после
рекурсивных
вызовов
}
//
Конец
оператора
~f·
Перед
вызовом
функции
quicksort
выполняется
разбиение
массива
на
части
8/
и
S2.
Затем
алгоритм
упорядочивает
отрезки
8/
и
82
независимо
друг
от
друга,
поскольку
любой
элемент
отрезка
8/
находится
левее
любого
40

Страницы