Этот алгоритм был впервые описан К. А. Р. Хоаром в его классической статье «Быстрая сортировка» (С. A. R. Hoare, Quicksort. Computer Journal, 5, 1, April 1962, p. 10-15). В этом алгоритме используется подход «разделяй и властвуй», уже упоминавшийся в разделе 8.3: чтобы отсортировать массив, мы разделяем его па два подмассива и сортируем каждый из них рекурсивно. Например, для сортировки массива из восьми элементов
Рис. 11.1. Сортируемый массив
мы разбиваем его первым элементом (55), так чтобы все элементы, меньшие 55, расположились слева от него, а все большие — справа.
Рис. 11.2. Разбиение массива
Если затем рекурсивно отсортировать подмножества х[0. .2] и х[4. .7] по отдельности, весь массив окажется отсортирован.
Среднее время работы этого алгоритма оказывается существенно меньшим 0(п2) сортировки вставкой, поскольку операция разбиения дает гораздо больше для достижения цели. После разбиения п элементов примерно половина из них окажется ниже выделенного элемента, а половина — выше. За то же самое время
в программе сортировки вставкой на свое место устанавливается один-единствен- ный элемент.
Итак, у нас есть набросок рекурсивной функции. Опишем рабочую часть массива с помощью индексов I, и (нижняя и верхняя границы). Рекурсия останавливается, когда мы добираемся до массива с числом элементов, меньшим двух. Код программы приведен на листинге 11.3.
Листинг 11.3. Быстрая сортировка (набросок)
void qsort(1. u) if 1 >= u then
/* не более одного элемента - ничего не делаем */ return
/* цель, разбить массив относительно какого-либо элемента, который
оказывается на правильном месте */ qsort(1 . р-1) qsort(р+1, и )
Для разбиения массива относительно значения t мы начнем с простой схемы,
о которой я узнал от Нико Ломуто. Более быстрый вариант программы, выполняющий эту задачу, будет приведен в следующем разделе , но эта функция так проста, что в ней трудно ошибиться, и она ни в коем случае не может быть названа медленной. Пусть дано значение t, нужно упорядочить массив х[а. .Ь] и вычислить индекс m такой, что все элементы, меньшие t, находятся слева от элемента х[т], а все большие — справа. Мы решим эту задачу с помощью простого цикла for, сканирующего массив слева направо, используя переменные i и m для сохранения инварианта (рис. 11.3).
Опубликовал vovan666
April 17 2013 00:02:33 ·
0 Комментариев ·
5480 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
