Qsort си реализация - IT Справочник
Llscompany.ru

IT Справочник
17 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Qsort си реализация

Быстрая сортировка

Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой.

Для достижения наибольшей эффективности желательно производить обмен элементов на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим . Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от них находятся элементы, меньшие разрешающего, и справа — большие (предполагается, что массив сортируется по возрастанию).

Тем самым массив разбивается на две части:

  • не отсортированные элементы слева от разрешающего элемента;
  • не отсортированные элементы справа от разрешающего элемента.

Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя.

Если требуется сортировать больше одного элемента, то нужно

  • выбрать в массиве разрешающий элемент;
  • переупорядочить массив, помещая элемент на его окончательное место;
  • отсортировать рекурсивно элементы слева от разрешающего;
  • отсортировать рекурсивно элементы справа от разрешающего.

Ключевым элементом быстрой сортировки является алгоритм переупорядочения .

Рассмотрим сортировку на примере массива:

10, 4, 2, 14, 67, 2, 11, 33, 1, 15.

Для реализации алгоритма переупорядочения используем указатель left на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right поставим на крайний правый элемент массива, и он движется влево, пока элементы, на которые он показывает, остаются больше разрешающего.

Пусть крайний левый элемент — разрешающий pivot . Установим указатель left на следующий за ним элемент; right — на последний. Алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы.

Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего элемента неправильный.

Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10.


Эти элементы меняются местами и движение указателей возобновляется.


Процесс продолжается до тех пор, пока right не окажется слева от left .


Тем самым будет определено правильное место разрешающего элемента.

Осуществляется перестановка разрешающего элемента с элементом, на который указывает right .

Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа — большие. Алгоритм рекурсивно вызывается для сортировки подмассивов слева от разрешающего и справа от него.

Реализация алгоритма быстрой сортировки на Си

Быстрая сортировка.

Выбирая алгоритм сортировки для практических целей, программист, вполне вероятно, остановиться на методе, называемом «Быстрая сортировка» (также «qsort» от англ. quick sort). Его разработал в 1960 году английский ученый Чарльз Хоар, занимавшийся тогда в МГУ машинным переводом. Алгоритм, по принципу функционирования, входит в класс обменных сортировок (сортировка перемешиванием, пузырьковая сортировка и др.), выделяясь при этом высокой скоростью работы.

Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному.

Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

  • разбиение массива относительно опорного элемента;
  • рекурсивная сортировка каждой части массива.

Разбиение массива.

Еще раз об опорном элементе. Его выбор не влияет на результат, и поэтому может пасть на произвольный элемент. Тем не менее, как было замечено выше, наибольшая эффективность алгоритма достигается при выборе опорного элемента, делящего последовательность на равные или примерно равные части. Но, как правило, из-за нехватки информации не представляется возможности наверняка определить такой элемент, поэтому зачастую приходиться выбирать опорный элемент случайным образом.

В следующих пяти пунктах описана общая схема разбиения массива (сортировка по возрастанию):

  1. вводятся указатели first и last для обозначения начального и конечного элементов последовательности, а также опорный элемент mid;
  2. вычисляется значение опорного элемента (first+last)/2, и заноситься в переменную mid;
  3. указатель first смещается с шагом в 1 элемент к концу массива до тех пор, пока Mas[first]>mid. А указатель last смещается от конца массива к его началу, пока Mas[last] mid, следовательно firstостается равным 1. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 8 и значением 8. Mas[8]>mid, следовательно last смещается на одну позицию влево. Mas[7] mid, следовательно first остается равным 2. Далее, элементы правой части сравниваются с mid. Проверяется элемент с индексом 6 и значением 1: Mas[6] mid, следовательно last смещается на одну позицию влево. Теперь first=last=4, а значит, условие first 1», нужно действовать примерно по следующей схеме:

Имеется массив Mas[L..R], где L и R – индексы крайних элементов этого массива. По окончанию разбиения, указатели first и last оказались примерно в середине последовательности, тем самым образуя два отрезка: левый от L до last и правый от first до R. Выполнить рекурсивное упорядочивание левой части нужно в том случае, если выполняется условие L

Qsort си реализация

Быстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.

Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.

Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:

  • разбиение массива относительно опорного элемента;
  • рекурсивная сортировка каждой части массива.

O(n log n) (обычное разделение)
или O(n) (разделение на 3 части)

O(n) вспомогательных
O(log n) вспомогательных

Реализация алгоритма на различных языках программирования:

Работает для произвольного массива из n целых чисел.

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

Java/C#

C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable

C# с использованием лямбда-выражений

Быстрая сортировка на основе библиотеки STL.

Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)

JavaScript

Python

С использованием генераторов:

Haskell

Математическая версия — с использованием генераторов:

Common Lisp

В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является «честной» — она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, «на том же месте». При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует «императивные» макросы Common Lisp’а.

Pascal

В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.

Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.

Устойчивый вариант (требует дополнительно O(n)памяти)

Быстрая сортировка, нерекурсивный вариант

Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных.

Qsort си реализация

«Быстрая сортировка», хоть и была разработана более 40 лет назад, является наиболее широко применяемым и одним их самых эффективных алгоритмов.

Метод основан на подходе «разделяй-и-властвуй». Общая схема такова:

  1. из массива выбирается некоторый опорный элемент a[i],
  2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] — вправо,
  3. теперь массив состоит из двух подмножеств, причем левое меньше, либо равно правого,
  4. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

В конце получится полностью отсортированная последовательность.

Рассмотрим алгоритм подробнее.

На входе массив a[0]. a[N] и опорный элемент p, по которому будет производиться разделение.

  1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
  2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] >= p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] 2 ) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге. Вообще говоря, малореальная ситуация.

Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части.

Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.

Модификации кода и метода

Из-за рекурсии и других «накладных расходов» Quicksort может оказаться не столь уж быстрой для коротких массивов. Поэтому, если в массиве меньше CUTOFF элементов (константа зависит от реализации, обычно равна от 3 до 40), вызывается сортировка вставками. Увеличение скорости может составлять до 15%.

Для проведения метода в жизнь можно модифицировать функцию quickSortR, заменив последние 2 строки на

Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из -50 , так что интерес скорее теоретический, нежели практический. Однако, поведение «быстрой сортировки» является «эталоном» для аналогично реализованных алгоритмов типа «разделяй-и-властвуй». Не везде можно свести вероятность худшего случая практически к нулю, поэтому такая ситуация заслуживает изучения.

Пусть, для определенности, каждый раз выбирается наименьший элемент amin . Тогда процедура разделения переместит этот элемент в начало массива и на следующий уровень рекурсии отправятся две части: одна из единственного элемента amin, другая содержит остальные n-1 элемента массива. Затем процесс повторится для части из (n-1) элементов.. И так далее..
При использовании рекурсивного кода, подобного написанному выше, это будет означать n вложенных рекурсивных вызовов функции quickSort.
Каждый рекурсивный вызов означает сохранение информации о текущем положении дел. Таким образом, сортировка требует O(n) дополнительной памяти.. И не где-нибудь, а в стеке. При достаточно большом n такое требование может привести к непредсказуемым последствиям.

Для исключения подобной ситуации можно заменить рекурсию на итерации, реализовав стек на основе массива. Процедура разделения будет выполняться в виде цикла.
Каждый раз, когда массив делится на две части, в стек будет направляться запрос на сортировку большей из них, а меньшая будет обрабатываться на следующей итерации. Запросы будут выбираться из стека по мере освобождения процедуры разделения от текущих задач. Сортировка заканчивает свою работу, когда запросы кончаются.

Псевдокод.
Реализация на Си.

Размер стека при такой реализации всегда имеет порядок O(log n), так что указанного в MAXSTACK значения хватает с лихвой.

Быстрая сортировка

Быстрая сортировка (англ. quick sort, сортировка Хоара) — один из самых известных и широко используемых алгоритмов сортировки. Среднее время работы [math]O(nlog)[/math] , что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении. Хотя время работы алгоритма для массива из [math]n[/math] элементов в худшем случае может составить [math]Theta(n^2)[/math] , на практике этот алгоритм является одним из самых быстрых.

Быстрый метод сортировки функционирует по принципу «разделяй и властвуй».

  • Массив [math] a[l ldots r][/math] типа [math] T [/math] разбивается на два (возможно пустых) подмассива [math] a[l ldots q][/math] и [math] a[q+1 ldots r][/math] , таких, что каждый элемент [math] a[l ldots q][/math] меньше или равен [math] a[q][/math] , который в свою очередь, не превышает любой элемент подмассива [math] a[q+1 ldots r][/math] . Индекс вычисляется в ходе процедуры разбиения.
  • Подмассивы [math] a[l ldots q][/math] и [math] a[q+1 ldots r][/math] сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
  • Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив [math] a[l ldots r][/math] оказывается отсортированным.

Для сортировки всего массива необходимо выполнить процедуру [math]mathrm[/math] .

Разбиение массива [ править ]

Основной шаг алгоритма сортировки — процедура [math]mathrm[/math] , которая переставляет элементы массива [math]a[l ldots r][/math] типа [math] T [/math] нужным образом. Разбиение осуществляется с использованием следующей стратегии. Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент [math] a[(l + r) / 2] [/math] . Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент, затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Так продолжаем дальше, пока не убедимся в том, что слева от левого указателя не осталось ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

Переменная [math] v [/math] сохраняет значение разделяющего элемента [math] a[(l + r) / 2] [/math] , a [math] i [/math] и [math] j [/math] представляет собой, соответственно, указатели левого и правого просмотра. Цикл разделения увеличивает значение [math] i [/math] и уменьшает значение [math] j [/math] на [math] 1 [/math] , причем условие, что ни один элемент слева от [math] i [/math] не больше [math] v [/math] и ни один элемент справа от [math] j [/math] не меньше [math] v [/math] , не нарушается. Как только значения указателей пересекаются, процедура разбиения завершается.

Худшее время работы [ править ]

Предположим, что мы разбиваем массив так, что одна часть содержит [math]n — 1[/math] элементов, а вторая — [math]1[/math] . Поскольку процедура разбиения занимает время [math]Theta(n)[/math] , для времени работы [math]T(n)[/math] получаем соотношение:

[math]T(n) = T(n — 1) + Theta(n) = sumlimits_^ Theta(k) = Theta(sumlimits_^ k) = Theta(n^2)[/math] .

Мы видим, что при максимально несбалансированном разбиении время работы составляет [math]Theta(n^2)[/math] . В частности, это происходит, если массив изначально отсортирован.

Способ построить массив с максимальным количеством сравнений при выборе среднего элемента в качестве опорного [ править ]

В некоторых алгоритмах быстрой сортировки в качестве опорного выбирается элемент, который стоит в середине рассматриваемого массива. Рассмотрим массив, на котором быстрая сортировка с выбором среднего элемента в качестве опорного сделает [math]Theta(n^2)[/math] сравнений. Очевидно, что это будет достигаться при худшем случае (когда при каждом разбиении в одном массиве будет оказываться [math]1[/math] , а в другом [math] n — 1 [/math] элемент).

Заполним сначала массив [math]a[/math] длины [math]n[/math] элементами от [math]1[/math] до [math] n [/math] , затем применим следующий алгоритм (нумерация с нуля):

Тогда на каждом шаге в качестве среднего элемента будет ставиться самый крупный элемент.

При выполнении [math]mathrm[/math] делается [math]Theta(n)[/math] сравнений из-за того, что с помощью индексов [math]i[/math] и [math]j[/math] мы проходим в лучшем случае [math]Omega(n)[/math] элементов (если функция прекращает свою работу, как только индексы встречаются), в худшем случае [math]O(2n)[/math] элементов (если оба индекса полностью проходят массив). При каждом изменении индекса делается сравнение, значит, процедура [math]mathrm[/math] делает [math]Theta(n)[/math] сравнений с точностью до константы.

Рассмотрим, какой элемент будет выбираться опорным на каждом шаге. [math]mathrm[/math] на каждом шаге меняет местами последний и центральный элементы, поэтому в центре оказывается самый крупный элемент. А [math]mathrm[/math] делает абсолютно симметричные этой процедуре операции, но в другую сторону: меняет местами центральный элемент с последним, так что самый крупный элемент становится последним, а затем выполняет на массиве длины на один меньшей ту же операцию. Получается, что опорным всегда будет выбираться самый крупный элемент, так как [math] mathrm [/math] на массиве любой длины будет выполнять операции, обратные [math]mathrm[/math] . Фактически, [math]mathrm[/math] — это [math]mathrm[/math] , запущенная в другую сторону. Также стоит отметить, что процедура разбиения будет делать на каждом шаге только одну смену элементов местами. Сначала [math]i[/math] дойдет до середины массива, до опорного элемента, [math]j[/math] останется равным индексу последнего элемента. Затем произойдет [math]mathrm[/math] и [math]i[/math] снова начнет увеличиваться, пока не дойдет до последнего элемента, [math]j[/math] опять не изменит свою позицию. Потом произойдет выход из [math]mathrm[/math] .

Разбиение массива будет произведено [math]Theta(n)[/math] раз, потому что разбиение производится на массивы длины [math]1[/math] и [math] n — 1 [/math] из-за того, что на каждом шаге разбиения в качестве опорного будет выбираться самый крупный элемент (оценка на худшее время работы доказана выше). Следовательно, на массиве, который строится описанным выше способом, выполняется [math]Theta(n)[/math] [math]mathrm[/math] и [math]Theta(n)[/math] сравнений для каждого выполнения [math]mathrm[/math] . Тогда быстрая сортировка выполнит [math]Theta(n^2)[/math] сравнений для массива, построенного таким способом.

Способ построить массив с максимальным количеством сравнений при детерминированном выборе опорного элемента [ править ]

Рассмотрим алгоритм построения массива, на котором быстрая сортировка с детерминированным выбором опорного элемента будет делать максимальное (в данном случае — [math]Theta(n^2)[/math] ) количество сравнений. Такое число сравнений достигается при разбиении на массивы длиной [math]1[/math] и [math]n-1[/math] на каждой итерации. Создадим массив [math]a[/math] длины [math]n[/math] , заполненный элементами типа [math]pair[/math] . Такой элемент хранит пару значений [math](val, key)[/math] , где [math]val[/math] — элемент массива, а [math]key[/math] — индекс. Изначально [math]a[i][/math] элемент имеет вид [math](0, i)[/math] .

Далее, запустим для данного массива алгоритм быстрой сортировки. Сравниваем два элемента типа [math]pair[/math] по их значениям [math]val[/math] . На каждом шаге будем выполнять следующие действия: при обращении к [math]i[/math] -ому элементу в качестве опорного на шаге под номером [math]k[/math] , присвоим [math]val = n-k+1[/math] для элемента [math]a[i][/math] . Затем выполним шаг сортировки. После завершения работы алгоритма быстрой сортировки, дополнительно отсортируем получившиеся элементы [math]pair[/math] по значениям [math]key[/math] . Искомым будет являться массив элементов [math]val[/math] в соответствующей последовательности.

Пример для [math]n = 4[/math] , при последовательном выборе опорных элементов [math]2, 2, 1, 1[/math] .

Читать еще:  Matlab график функции
Ссылка на основную публикацию
ВсеИнструменты 220 Вольт
Adblock
detector