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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Исходное
состояние
массива
изображено
на
рис.
15.
Неопредепенная
часть
р
?
fiгst
fiгstUnknown
last
lastS1
Рисунок
15.
Исходное
состояние
массива
На
каждом
шаге
алгоритма
разбиения
проверяется
один
элемент
из
неопределенной
части.
В
зависимости
от
его
значения
он
помещается
в
множество
8]
или
82.
Таким
образом, на
каждом
шаге
размер
неопределенной
части
уменьшается
на
единицу.
Алгоритм
останавливается,
когда
размер
неопределенной
части
становится
равным
нулю,
т.е.
выполняется
условие
firstVnknown
> last.
Рассмотрим
псевдокод
этого
алгоритма.
partition
(inоиt
theArray:ltemArray,
in
first:
integer,
in
last:
infegel",
оиt
pivotlndex:
integer)
//
Разделяет
массив
theArray[first
..
last}
//
Инициализация
Выбрать
опорный
элемент
и
поменять
его
местами
с
элементом
theArray[first}
р
=
theArray[fir5.~t}
//
р
-
опорный
элемент
//
Задаем
пустые
множества
8
}
и
82.,
а
неопределенную
//
часть
массива
инициализируем
отрезком
//
theArray[fir,st+
1 ..
Газ«]
Za"f)tSZ
==
./ir,st
firstUnknown
==
first
+ 1
//
Определяем
множества
8]и
S2.
while
(firstUnknown
< =
last)
(
//
Вычисляем
индекс
самого
левого
элемента
//
неопределенной
части
массива
if
(theArray[firstUnknown)
<
р)
Поместить
элемент
theArray[firstUnknown}
в
S].
else
Поместить
элемент
theArray[fir,-~;tUnknоwnJ
в
S2.
}
//
Конец
оператора
while
34

Страницы