Быстрая сортировка.
Теоретические основы информатики
Сравнить оставшиеся элементы из, А с опорным и разместить меньшие (или равные) слева от него, а большие (или равные) — справа. Пусть L и R — номера первого и последнего элементов разделяемого множества соответственно. Изначально принимается L = 1, R = п. Среди элементов сортируемого множества, А = {аь а2, ап} выбрать некоторый элемент, называемый опорным. Решение. В табл. 11.7 приведены состояния… Читать ещё >
Быстрая сортировка. Теоретические основы информатики (реферат, курсовая, диплом, контрольная)
Алгоритм быстрой сортировки (англ. Quicksort) является одним из самых часто используемых на практике для упорядочивания больших объемов данных. Он был предложен в 1960 г. Ч.Хоаром.
Шаги укрупненного алгоритма быстрой сортировки:
- 1. Среди элементов сортируемого множества А = {аь а2, ап} выбрать некоторый элемент, называемый опорным.
- 2. Сравнить оставшиеся элементы из А с опорным и разместить меньшие (или равные) слева от него, а большие (или равные) — справа.
- 3. Повторить рекурсивно шаги 1−2 для каждой части до и после опорного элемента.
Рассмотрим каждый шаг более подробно.
Выбор опорного элемента может осуществляться по-разному. Для простоты будем считать опорным элементом а и обозначать Ь. Размещение элементов перед и после опорного элемента выполняется следующим образом.
- 1. Пусть L и R — номера первого и последнего элементов разделяемого множества соответственно. Изначально принимается L = 1, R = п.
- 2. Будем последовательно увеличивать L на 1, пока не встретим первый с начала множества элемент al ^ Ь. После этого аналогичным образом будем уменьшать R на 1, пока не встретим первый элемент с конца множества aR < 6.
- 3. Если L ^ Я, то выполняем перестановку cll и aR и переходим снова к шагу 2.
- 4. Если L > R, то процесс размещения элементов окончен.
В результате выполнения шагов 1 4 элементы, меньшие или равные опорного, окажутся слева, а большие или равные — справа от него.
Деление каждой части элементов справа и слева от опорного осуществляется по аналогичной схеме. Процесс останавливается, когда дальнейшее разделение выполнить будет невозможно.
Пример 11.9. Разместить элементы множества А = {5,3,12,1,8,9, 6, 4,2,7} до и после опорного элемента.
Решение. В табл. 11.7 приведены состояния множества А. В квадратных скобках указан опорный элемент.
Таблица 11.7
Разделение относительно опорного элемента
Состояние. | L | R | Действие. |
*о = {[5]Д 12,1,8,9,6,4,2,7}. | Установить R = 9. | ||
s0 = {[5], 3,12,1,8,9,6,4,2,7}. | Перестановка = Ь и aR = 2 | ||
«а = {2,3,12,1,8,9,6,4, [5], 7}. | Перестановка = 12 и aR = 5. | ||
s3 = {2,3, [5], 1,8,9,6.4,12,7}. | Перестановка а*, = 5 и aR — 4. | ||
s4 = {2,3,4,1,8,9.6, [5], 12,7}. | Перестановка аь = 8 и aR = 5. | ||
s8 = {2,3,4,1, [5], 9,6,8,12,7}. |
Применяя аналогичным образом алгоритм разделения рекурсивно к неупорядоченным множествам 
получим б итоге упорядоченное множество А.
Алгоритм быстрой сортировки имеет следующие особенности.
- 1. Считается, что он становится эффективнее других рассмотренных ранее алгоритмов при п > 40. Когда количество элементов, которые необходимо упорядочить, становится меньше 40, применяют отличные от быстрой сортировки алгоритмы.
- 2. Если в качестве опорного элемента выбирается наибольший (наименьший) элемент множества А, то одно из разделяемых множеств оказывается пустым, что увеличивает временную сложность. Чтобы такая ситуация повторялась нечасто, опорный элемент можно выбирать случайным образом.
Алгоритм быстрой сортировки имеет сложность порядка 0(nlog2rc).