УДК 681.142.2(075.8)
А. Ф. Д е о н
D
-
ПОСЛЕДОВАТЕЛЬНОСТИ В БЫСТРОЙ
СОРТИРОВКЕ ХОАРА
Рассмотрены вопросы формирования длительных по количеству
компьютерных операций
D
-
последовательностей для определения
скоростных свойств быстрой сортировки Хоара на одномерных
массивах целочисленной информации.
E-mail:
Ключевые слова
:
быстродействие, алгоритм, числа, размерность.
Алгоритм быстрой сортировки Хоара относится к группе слож-
ных методов упорядочивания массивов вместе с методом слияния,
алгоритмом Шелла, методами древовидных сортировок. Для больших
массивов все они превосходят по быстродействию простые методы
минимакса, перестановки, парных сравнений, сдвига и вставки. Фор-
мульный анализ количества выполняемых операций включает мини-
мальные и максимальные оценки. Максимальное количество опера-
ций в быстрой сортировке Хоара дают длительные по числу операций
D
-
последовательности исходных данных, подлежащих сортировке.
Разделяющий элемент Хоара.
Пусть имеется упорядоченный мас-
сив, например по возрастанию. Назовем элемент массива
разделяю-
щим
,
если слева от него находятся элементы с меньшими или равны-
ми значениями. Тогда справа будут находиться элементы с большими
или равными значениями. В упорядоченном массиве любой элемент
является разделяющим. Но могут существовать массивы, когда левые
и правые части относительно разделяющего элемента неупорядоче-
ны. В этом случае разделяющий элемент точно находится на том же
месте в целиком упорядоченном массиве. Это следствие несложной
теоремы, доказательство которой начинается с утверждения, что лю-
бая непрерывная часть упорядоченного массива упорядочена. Хоар
(
Hoare) предложил алгоритм поиска такого разделяющего элемента в
произвольном массиве. Это означает, что появилась возможность сразу
определить место разделяющего элемента в будущем упорядоченном
массиве.
Ниже представлена программа
DH01
,
в которой функция
Hoare-
PosPrint
( )
определяет позицию разделяющего элемента и предоста-
вляет распечатки дополнительной информации по ходу поиска:
//
Program DH01 (Win32)
//
Разделяющий элемент в быстрой сортировке Хоара
#
include
<
conio.h
>
// _
getch
92
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
