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