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

UptoLike

ВУЗ: 

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

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

Рубрика: 

1.
Инвариант
должен
быть
истинным
с
самого
начала,
до
выполнения
цикла.
В
алгоритме
разбиения
опорным
элементом
является
theArray
[first},неизвестной
частью
отрезок
массива
theArray
[first+l
..
last},
а
множества
8/
и
82.
пусты.
Очевидно,
что
при
этих
условиях
инвариант
является
истинным.
2.
Итерации
цикла
не
должны
нарушать
инвариант.
Иными
словами,
если
инвариант
был
истинным
перед
определенной
итерацией
цикла,
он
должен
оставаться
истинным
и
после
ее
выполнения.
В
алгоритме
разбиения
каждая
итерация
цикла
переносит
один
элемент
из
неизвестной
части
в
множество
8
]
или
82,
В
зависимости
от
его
значения
по
сравнению
с
опорным.
Итак,
если
до
переноса
инвариант
был
истинным,
он
должен
сохраняться
и
после
переноса.
3.
Инвариант
должен
определять
корректность
алгоритма.
Иными
словами,
из
истинности
инварианта
должна
следовать
корректность
алгоритма.
Выполнение
алгоритма
разбиения
прекраrцается,
когда
неопределенная
область
становится
пустой.
В
этом
случае
каждый
элемент
отрезка
theArray[first+ 1.
.last]
должен
принадлежать
либо
множеству
8
1
,
л
и
б
о
множеству
82.
В
любом
случае
из
корректности
инварианта
следует,
что
алгоритм
достиг
своей
цели.
4.
ЦИКЛ
должен
быть
конечным.
Иными
словами,
нужно
показать,
что
выполнение
цикла
завершится
после
конечного
числа
итераций.
В
алгоритме
разбиения
размер
неопределенной
части
на
каждой
итерации
уменьшается
на
единицу.
Следовательно,
после
выполнения
конечного
количества
итераций
неопределенная
часть
становится
пустой,
и
цикл
завершается.
Рассмотрим
функцию
на
языке
С++,
реализующую
алгоритм
quick8ort.B
ней
для
выбора
опорного
элемента
используется
функция
choosePivot,
а
функция
swap
работает,
как
и
раньше,
в
алгоритме
selection8ort.
Для
упор
ния
массива
theArray,
состоящего
из
n
элементов,
выполняется
вызов
quickSort(theArray,
О,
n-l).
void
cho()~\'ePivot(DataType
theArray[},
int..fir5;t,
int
ILМ·t)~·
;1;1
--------------------------------------------------------------------
//
Выбирает
опорный
элемент
для
алгоритма
быстрой
сортировки.
//
Меняет
его
местами
с
первым
элементом
массива.
//
Предусловие:
отрезок
theArray[first..last} -
массив;
//
first <
==
last.
//
Постусловие:
элемент
theArra})[first}
является
опорным.
//
-----------------------------------------------------------------------------
//
Реализация
этой
функции
предоставляется
читателям.
38

Страницы