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

UptoLike

ВУЗ: 

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

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

Рубрика: 

}
//
Конец
оператора
if
//
еслиfirst
>=
Таз»,
ничего
не
делаем
kSmaZZ(in
k:integer~
in
theArray:/temArray,
in
first:
integer~
in
Zast:
integer):
Item
Туре
//
Возвращает
значение
k-го
наименьшего
элемента
массива
//
theArray{first
..
Zast}.
Выбрать
в
массиве
theArray[first
..
last}
опорный
элемент
р
Разбить
массив
theArray[first
..Zast}
относительно
элемента
р
If
(k
<
pivotZndex
-
first
+
1)
return
kSmaZZ(k~
theArray~
first,
pivotZndex-Z)
else
if
(k
= =
pivotZndex
-
.first
+
1)
return
р
else
return
kSmaZZ(k-(рivоtZndех-:fir
спе.Ат-ау.
..
s,t+I},
pivotlndex+l,
last)
Функция
kSmall
вызывается
рекурсивно,
только
если
одна
из
частей
массива
содержит
искомый
элемент.
Если
этим
элементом
является
опорный,
функция
не
вызывается
вообще.
В
то
же
время
функция
quicksort
вызывается
рекурсивно
для
обеих
частей
массива.
Различия
между
этими
двумя
функциями
проиллюстрировано
на
рис.13
kSmall(k, theArray, first, last)
или
kSmall(k, theArray, first, pivotlndex-1)
kSmall(k-(рivоtl
ndex-first+1),
theArray, pivotl ndex+ 1, last)
quicksort(theArray, first, last)
quicksort(theArray, first, pivotlndex-1)
quicksort(theArray, first, pivotlndex+1,last)
РИСУНОК
13.
Сравнение
фУНКЦИЙ
k~Sтall
и
qиiсkSО1~t
Использование
инварианта
в
алгоритме
разбиения.
Рассмотрим
функцию
разбиения
массива,
которая
должна
вызываться
функциями
kSmall
и
quickSort.
В
обоих
алгоритмах
именно
разбиение
массива
представляет
собой
наиболее
трудную
задачу.
32

Страницы