ВУЗ:
Составители:
Рубрика:
Функция,
предназначенная
для
разбиения
массива,
получает
в
качестве
аргумента
отрезок
theArray[first.
.last}.
Функция
должна
распределить
элементы
массива,
руководствуясь
следующим
правилом:
в
множество
Stвключаются
элементы,
меньшие
опорного,
а
в
множество
S2
-
остальные.
Как
показано на
рис.12,
множество
S1
является
отрезком
массива
theArray
[first.
.pivot
Index-l},
а
множество
S2
-
отрезком
массива
theArray
[pivotlndex+l
. . last}.
Как
выбрать
опорный
элемент?
Если
элементы
массива
записаны
в
произвольном
порядке,
в
качестве
опорного
можно
выбрать
любой
элемент,
например
theArray [first}.
(Более
детально
процедура
выбора
опорного
элемента
будет
рассмотрена
позднее.)
При
разбиении
массива
опорный
элемент
удобно
помещать
в
ячейку
theArray
[first},
независимо
от
того,
какой
именно
элемент
выбран
в
качестве
опорного.
Часть
массива,
в
которой
находятся
элементы,
еще
не
распределенные
по
отрезкам
81
и
82,
называется
неопределенноЙ.
Итак,
рассмотрим
массив,
изображенный
на
рис.14.
Индексы
first,
lastS
1,
firstUnknown
и
last
разделяют
массив
на
три
части.
Отношения
между
опорным
элементом
и
элементами
неопределенной
части
theArray
{firstUnknown
..
last]
неизвестны.
Опорный
элемент
82
Неопределенная
часть
р
<р
>=р
?
first
Last8
1
firstUrlknown last
РИСУНОК
14.
Инвариант
алголритма
разбиения
в
процессе
разбиения
массива
должно
выполняться
следующее
условие.
Элементы
множества
81
должны
быть
меньше
опорного
элемента,
а
элементы
множества
82
-
больше
или
равны
ему.
Это
утверждение
является
инвариантом
алгоритма
разбиения.
Для
того
чтобы
в
начале
алгоритма
выполнялся
его
инвариант,
необходимо
проинициализировать
индексы
массива
так,
чтобы
весь
массив,
кроме
опорного
элемента,
считался
неопределенным.
1
а
s tS1
==
fi
r s t
first
Unknown
==
first
+ 1
33
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
