Инвариант цикла сканирования в алгоритме быстрой сортировки
Когда проверяется i-й элемент, необходимо рассмотреть две ситуации. Если x[i] >= t, то инвариант остается истинным. Если же x[i] < t, то восстановить инвариант можно, увеличив индекс m (который указывает новое местоположение меньшего элемента) и поменяв местами x[i] и х[т]. В итоге получаем код, осуществляющий разбиение массива:
m = а -1
for 1 = [а. Ь] if x[i] < t swapO+m. i )
В алгоритме Quicksort нам нужно разбить массив x[l..u] относительно значения Ых[1], так что а = 1+ 1, а b = и. Инвариант цикла разбиения можно будет изобразить следующим образом (рис. 11,4),
Рис. 11.4. Инвариант цикла разбиения массива После завершения цикла получим картину, изображенную на рис. 11.5.
Рис. 11.5. Состояние массива после завершения цикла разбиения
Затем мы поменяем местами х[1] и х[т], что даст рис. 11.61.
Рис. 11.6. Состояние после перестановки элементов
Теперь можно рекурсивно вызвать функцию с параметрами (I, т-1) и (т+1, и).
Получившийся код дает первую завершенную версию быстрой сортировки. Он приведен в листинге 11.4. Для сортировки массива х[п] функцию следует вызвать как qsort (0, п-1).
Опубликовал vovan666
April 17 2013 00:02:35 ·
0 Комментариев ·
4496 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
