1. Применять сортировку для поиска минимального или максимального из п вещественных чисел обычно неразумно. В решении задачи 9 показано, как можно иай ги медиану без сортировки, но в некоторых системах может оказаться проще сначала отсортировать данные. Сортировка удобна при поиске моды распределения, по хэширование может решить эту задачу быстрее. Очевидный алгоритм нахождения среднего значения работает за время, пропорциональное п, по предварительная сортировка таблицы помогает достичь большей численной точности (см. задачу 14.4Ь).
2. Боб Седжвик показал, что схему разбиения Ломуто можно изменить так, чтобы она работала справа налево, если использовать приведенный на рисунке инвариант.
Код, осуществляющий разбиение, будет выглядеть следующим образом:
m = и + 1
for (1 = и. 1 >= 1 : 1++) if х[i] >= t swap(--m, i)
Когда цикл завершается, мы знаем, что x[m]—t, поэтому можно делать рекурсивный вызов с параметрами (I, т-1) и (т+1, и). При этом никаких дополнительных перестановок не требуется. Седжвик использовал элемент х[1] в качестве маркера, чтобы избавиться от одной из проверок во внутреннем цикле.
171 = 1 = U+1
d о
while х[ - -1 ] < t
swap(--m. i ) whi1е i = 1
Опубликовал vovan666
April 17 2013 00:06:51 ·
0 Комментариев ·
3644 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
