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

UptoLike

ВУЗ: 

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

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

Рубрика: 

а
множество
S2=theArray [pivotlndex+ 1. . .last]
состоит
из
элементов,
больших
или
равных
опорному.
Хотя
из
этого
свойства
не
следует,
что
массив
упорядочен,
из
него
вытекает
чрезвычайно
полезный
факт:
если
массив
упорядочен,
элементы,
стоящие
на
позициях
от
first
до
pivotlndex-l,
остаются
на
своих
местах,
хотя
их
позиции
относительно
друг
друга
могут
измениться.
Аналогичное
утверждение
выполняется
и
для
элементов,
стоящих
на
позициях
от
pivotlndex+ 1
до
last.
Опорный
элемент
в
полученном
упорядоченном
массиве
останется
на
своем
месте.
Такое
разбиение
массива
определяет
рекурсивный
характер
алгоритма.
Разбиение
массива
относительно
опорного
элемента
р
порождает
две
задачи
сортировки
меньшего
размера-
сортировка
леВОЙ(Sl)
и
правой/Б-)
частей
массива.
Решив
эти
две
задачи,
мы
получим
решение
исходной
задачи.
<р
>=
Р
82
fiгst
pivotlndex last
РИСУНОК
12.
Разбиение
относительно
опорного
элемента
Иными
словами,
разбиение
массива
перед
рекурсивными
вызовами
оставляет
опорный
элемент
на
своем
месте
и
гарантирует,
что
левый
и
правый
отрезки
массива
окажутся
упорядоченными.
Кроме
того,
алгоритм
быстрой
сортировки
конечен:
размеры
левого
и
правого
отрезка
массива
меньше
размера
исходного
массива,
причем
каждый
шаг
рекурсии
приближает
нас
к
базису,
когда
массив
состоит
из
одного
элемента.
Это
следует
из
того
факта,
что
опорный
элемент
р
не
принадлежит
ни
одному
из
массивов
8
!
и
82.
Псевдокод
алгоритма
быстрой
сортировки
выглядит
следующим
образом.
qиiсksоrt(inоиt
theArray.·ltemArray,
in
first:
integer,
in
last:
integer)
//
Упорядочивает
массив
theArray[first
..
Zast]
If
(first
<
last)
Выбрать
опорный
элемент
р
из
массива
theArray[first
..
Zast]
Разбить
массив
theArray[first
..Zast]
относительно
опорного
элемента
р
//
Разбиение
имет
вид
theArray[fir.st
..
pivotlndex
. .
Zast]
//
Упорядочиваем
массив
81
qиiсksоrt(thеАl/8rау,
first,
pivot
Index-1)
//
Упорядочиваем
массив
82
qиiсksоrt
(theArray,
pivotZndex+l,
Zast)
31

Страницы