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

UptoLike

ВУЗ: 

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

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

Рубрика: 

void
partition
(Data
Туре
theArray[},
intjirst,
int last, int& pivotlndex)
hI
-----------------------------------------------------------------------------
//
Разбивает
массив
для
быстрой
сортировки.
//
Предусловие:
отрезок
theArray[first..last}
-)\1ассив;
//
jirst
<
==
last.
//
Постусловие:
массив
theArray[first..last}
разбит
//
следующим
образом:
//
S1
==
theArray[{irst..
pivotlndex-l]
<
pivot
//
theArray
[pivotlndex]
====
pivot
// 82
==
theArray
{pivotlndex +1.. last] >=
pivot
//
Вызываемые
функции:
choosePivot
и
swap.
/
!/ -----------------------------------------------------------------------------
{
//
Помещаем
опорный
элемент
в
ячейку
theArray[first}
choosePivot(theArray, jirst, last);
Гииа'Гуре
pivot
== theArray[first};
//
Копируем
//
опорный
элемент
//
В
исходном
положении
все
элементы,
кроме
опорного,
//
принадлежат
неопределенной
части
массива
int
lastSl
==
jirst;
//
Индекс
последнего
элемента
//Jwножесmва
k-')l
int
jirstlJnknown
==
jirst
+ 1
,.
//
Индекс
первого
элемента
//
неопределенной
части
//
Переносим
элементы
один
за
другим.
//
пока
неопределенная
часть
массива
не
станет
пустой
/о,
(:
.firstUnknown <
==
last; + +
jirst
Unknown)
{
//
Инвариант:
theArray[first+ 1..last81] <
pivot
//
theArray[lastSl
+ 1
...
firstUnknОИJn-l}
> =
pivot
//
Переносим
элемент
из
неопределенной
части
//
в
множество
~S1
или
S2
if
(theArray[firstUnknown] <
pi1t'of)
f
l
//
Элемент
принадлежит
множеству
81
++lastSI;
swap(theArray[firstUnknown}, theArray[lastSZ]) ;
~}
//
Конец
оператора
if
//
Иначе
элемент
принадлежит
множеству
82
}
//
Конец
оператора
.fOr
//
Поставить
опорный
элемент на
соответствующее
место
//
и
запомнить
его
индекс
swap
(theArray[first) , theArray[la\,t8l]);
pivotZndex =
ZastS
1,.
39

Страницы