|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выполнять сортировку, чтобы найти минимум или максимум среди N действительных чисел, все равно, что стрелять из пушки по воробьям. В решении задачи 9 показано, как медиану можно найти быстрее и без сортировки, но в некоторых системах может оказаться проще осуществить сортировку. Сортировка обычно вполне пригодна для нахождения моды. Хотя для вычисления среднего с помощью очевидной программы требуется время, пропорциональное N, при подходе, сначала предполагающем сортировку, можно выполнить эту работу с большей точностью (см. задачу З.Б гл. 12). Данная программа приводит к ошибке, если операционная система обеспечивает проверку границ массивов и проверяется выполнение обоих условий в логическом операторе, даже когда первое имеет значение "ложь". Аналогичная ситуация возникает в программе сортировки методом вставок из разд. 10.1, если J = 1. Ошибки могут быть устранены несколькими способами, такими как использование условного оператора and, задание элемента X [0] (и, возможно, использование его в качестве ячейки для сигнальной метки), засылка минимального значения в элемент X [1] перед вызовом основной сортировки, или использованием булевой переменной.
Если все элементы равны, программа быстрой сортировки, приведенная в этой главе, удаляет только один элемент при каждом из N рекурсивных обращений. Программа Сед-жуика имеет следующий инвариант:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
При "лишних" взаимных перестановках одинаковых элементов она сокращает ровно в 2 раза подмассив дубликатов ключей.
Седжуик отметил, что метод Ломуто может быть модифицирован для работы справа налево при использовании следующего инварианта:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Тогда программа разбиения выглядит так:
U := U+i
for I := U downto L do if XCI] >= T then
M := M-l
SwapttHO, ХПЗ)
При завершении программы мы зиаем, что X [М] ■ Т, так что можно организовать рекурсию с параметрами (L, М — 1) и (М + 1, U); дополнительной процедуры Swap ие требуется. Седжуик использовал также элемент X [L] в качестве сигнальной метки, чтобы исключить из внутреннего цикла одну проверку:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
