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

UptoLike

ВУЗ: 

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

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

Рубрика: 

//
Ставим
опорный
элемент
между
множествами
8/
и
82.
//
и
запоминаем
его
новый
индекс
Поменять
местами
theArray
[first}
и
theArray
[lastSZ}
pivotZndex
==
ZastSl
Алгоритм
достаточно
прост,
но
операция
перемещения
требует
разъяснения.
Рассмотрим
два
возможных
действия,
которые
необходимо
выполнить
на
каждой
итерации
цикла
while.
Поместить
элемент
theArray [firstUnknown}
в
множество
8/.
Множество
8/
И
неопределенная
часть,
как
правило,
не
являются
смежными.Обычно
между
ними
располагается
множество
82.
Однако
эту
операцию
можно
выполнить
более
эффективно.
Элемент
thеАrrау[firstVnknоwn}можно
поменять
местами
с
первым
элементом
множества
S2.,
т.е.
с
элементом
theArray[lastSI+
l},
как
показано
на
рис.
16.
Как
быть
с
элементом
множества
52,
который
был
помещен
в
ячейку
theArray[firstVnknown}?
Если
увеличить
индекс
firstVnknown
на
единицу,
этот
элемент
становится
самым
правым
в
множестве
82.
Таким
образом,
для
переноса
элемента
theArray [firstUnknown}
в
массив
8/
необходимо
выполнить
следующие
шаги.
Поменять
местами
элементы
theArray[firstlnknown}
и
theArray[lastSl+
1]
Увеличить
индекс
ZastSZ
на
единицу
Увеличить
индекс
firstUnknown
на
единицу
Эта
стратегия
остается
верной,
даже
если
множество
S2
пусто.
В
этом
случае
величина
last81+1
равна
индексу
firstUnknown,
и
элемент
просто
остается
на
своем
месте.
Инвариант
при
этом
не
нарушается.
Поместить
элемент
theArray[firstUnknown}
в
множество
82.
Эту
операцию
легко
выполнить.
Напомним,
что
индекс
крайнего
правого
элемента
множества
82 pabehfirstUnknown-l,
т.е.
множество
S2
инеизвестная
часть
являются
смежными
(рис.
17).
Таким
образом,
чтобы
переместить
элемент
theArray [firstUnknown}
в
множество
82,
нужно
просто
увеличить
индекс
firstUnknown
на единицу,
расширяя
множество
8
2вправо.Инвариант
при
этом
не
нарушается.
После
переноса
всех
элементов
из
неопределенной
части
в
множества
S1
И
82
остается
решить
последнюю
задачу.
Нужно
поместить
опорный
элемент
между
множествами
8/
и
82.
Обратите
внимание,
что
элемент
theArray [last81}
является
крайним
правым
элементом
множества
S/.
35

Страницы