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

Понятие быстрой сортировки

Быстрая сортировка - Quick Sort или qsort. По названию становится понятно, что это и для чего. Но если не понятно, то это алгоритм по быстрой сортировке массива, алгоритм имеет эффективность O(n log n) в среднем. Что это значит? Это значит, что среднее время работы алгоритма повышается по той же траектории, что и график данной функции. В некоторых популярных языках имеются встроенные библиотеки с этим алгоритмом, а это уже говорит о том, что он крайне эффективен. Это такие языки, как Java, C++, C#.

Алгоритм

Метод быстрой сортировки использует рекурсию и стратегию "Разделяй и властвуй".

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

2. Слева от опоры ищется элемент больший, чем опорный, справа - меньший, чем опорный, затем меняем их местами. Делаем это, пока максимальный справа не будет меньше, чем минимальный слева. Таким образом, все маленькие элементы кидаем в начало, большие - в конец.

3. Рекурсивно применяем данный алгоритм к левой и правой части нашего алгоритма отдельно, затем ещё и ещё, до достижения одного элемента или определённого количества элементов. Что же это за количество элементов? Есть ещё один способ оптимизировать данный алгоритм. Когда сортируемая часть становится примерно равной 8 или 16, то можно обработать её обычной сортировкой, например пузырьковой. Так мы повысим эффективность нашего алгоритма, т.к. маленькие массивы он обрабатывает не так быстро, как хотелось бы.

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

Эффективность быстрой сортировки

Является ли быстрая сортировка самым быстрым алгоритмом сортировки? Однозначно нет. Сейчас появляется всё больше и больше сортировок, на данный момент самая быстрая сортировка - это Timsort, она работает крайне быстро для массивов, изначально отсортированных по-разному. Но не стоит забывать, что метод быстрой сортировки является одним из самых простых в написании, это очень важно, ведь, как правило, для рядового проекта нужно именно простое написание, а не громадный алгоритм, который сам ты и не напишешь. Timsort - тоже не самый сложный алгоритм, но звание самого простого ему точно не светит.

Реализация алгоритма

Ну вот мы и дошли до самого "вкусного". Теперь разберём, как реализовывается данный алгоритм. Как говорилось ранее, он не слишком сложен в реализации, скорее, даже прост. Но мы всё равно полностью разберём каждое действие нашего кода, чтобы вы поняли, как работает быстрая сортировка.

Наш метод называется quickSort. В нём запускается основной алгоритм, в который мы передаём массив, первый и последний его элементы. Запоминаем в переменные i и k первый и последний элемент сортируемого отрезка, чтобы не изменять эти переменные, так как они нам нужны. Затем проверяем расстояние между первым и последним проверяемым: оно больше или равно единице? Если нет, значит, мы пришли к центру и нужно выйти из сортировки этого отрезка, а если да, то продолжаем сортировку.

Затем за опорный элемент берём первый элемент в сортируемом отрезке. Следующий цикл делаем до того момента, пока не дойдём до центра. В нём делаем ещё два цикла: первый - для левой части, а второй - для правой. Их мы выполняем, пока есть элементы, подходящие под условие, или пока не дойдём до опорного элемента. Затем, если минимальный элемент всё же справа, а максимальный - слева, меняем их местами. Когда цикл заканчивается, меняем первый элемент и опорный, если опорный меньше. Затем мы рекурсивно делаем наш алгоритм для правого и левого участка массива и так продолжаем, пока не дойдём до отрезка длиной в 1 элемент. Тогда все наши рекурсивные алгоритмы будут return, и мы полностью выйдем из сортировки. Также внизу имеется метод swap - вполне стандартный метод при сортировке массива заменами. Чтобы несколько раз не писать замену элементов, пишем один раз и меняем элементы в данном массиве.

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

До текущего момента единственной публикацией о сортировке в моем блоге была . Пора это исправлять! Строить грандиозных планов о покорении всех видов сортировки я не стану, а начну с одной из самых популярных — быстрая сортировка.

Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем , и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++.

Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма.

Как работает быстрая сортировка

Схему алгоритма можно описать таким образом:

1. Выбрать опорный элемент в массиве — часто встречается вариант с центральным элементом.
2. Разделить массив на две части следующим образом: все элементы из левой части, которые больше или равны опорному, перекидываем в правую , аналогично, все элементы из правой , которые меньше или равны опорному кидаем в левую часть.
3. В результате предыдущего шага в левой части массива останутся элементы, которые меньше или равны центральному, а в правой — больше либо равны.
   Наглядно это можно показать таким образом:
   |———————|—————————|———————|
   | mas[i] <= mid | mid = mas | mas[i] >= mid |
   |———————-|—————————|———————|
4. Рекурсивно повторяем действие для левой и правой части массива.

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

Иллюстрацию одного шага алгоритма я позаимствовал , больно уж она наглядная.

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

На вход функция принимает сам массив(указатель на начало) и его размер.

Void qsortRecursive(int *mas, int size) { //Указатели в начало и в конец массива int i = 0; int j = size - 1; //Центральный элемент массива int mid = mas; //Делим массив do { //Пробегаем элементы, ищем те, которые нужно перекинуть в другую часть //В левой части массива пропускаем(оставляем на месте) элементы, которые меньше центрального while(mas[i] < mid) { i++; } //В правой части пропускаем элементы, которые больше центрального while(mas[j] > mid) { j--; } //Меняем элементы местами if (i <= j) { int tmp = mas[i]; mas[i] = mas[j]; mas[j] = tmp; i++; j--; } } while (i <= j); //Рекурсивные вызовы, если осталось, что сортировать if(j > 0) { //"Левый кусок" qsortRecursive(mas, j + 1); } if (i < size) { //"Првый кусок" qsortRecursive(&mas[i], size - i); } }

Заключение

Это задание одновременно помогает понять, как работает рекурсия и учит прослеживать изменение данных во время исполнения алгоритма. Рекомендуется «дойти» и написать это самостоятельно, но все же вот моя реализация, мне и самому она может пригодиться. На этом у меня все, спасибо за внимание!

O(n ) вспомогательных
O(log n ) вспомогательных (Седжвик 1978)

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

algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p – 1) quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) is pivot:= A i:= lo - 1 for j:= lo to hi - 1 do if A[j] ≤ pivot then i:= i + 1 swap A[i] with A[j] swap A with A return i + 1

Сортировка всего массива может быть выполнена с помощью выполнения quicksort(A, 1, length(A)) .

Разбиение Хоара

Данная схема использует два индекса (один в начале массива, другой в конце), которые приближаются друг к другу, пока не найдётся пара элементов, где один больше опорного и расположен перед ним, а второй меньше и расположен после. Эти элементы меняются местами. Обмен происходит до тех пор, пока индексы не пересекутся. Алгоритм возвращает последний индекс. . Схема Хоара эффективнее схемы Ломуто, так как происходит в среднем в три раза меньше обменов (swap) элементов, и разбиение эффективнее, даже когда все элементы равны. Подобно схеме Ломуто, данная схема также показывает эффективность в O (n 2) , когда входной массив уже отсортирован. Сортировка с использованием данной схемы нестабильна. Следует заметить, что конечная позиция опорного элемента необязательно совпадает с возвращённым индексом. Псевдокод :

algorithm quicksort(A, lo, hi) is if lo < hi then p:= partition(A, lo, hi) quicksort(A, lo, p) quicksort(A, p + 1, hi) algorithm partition(A, lo, hi) is pivot:= A i:= lo - 1 j:= hi + 1 loop forever do i:= i + 1 while A[i] < pivot do j:= j - 1 while A[j] > pivot if i >= j then return j swap A[i] with A[j]

Повторяющиеся элементы

Для улучшения производительности при большом количестве одинаковых элементов в массиве может быть применена процедура разбиения массива на три группы: элементы меньшие опорного, равные ему и больше него. (Бентли и Макилрой называют это «толстым разбиением». Данное разбиение используется в функции qsort в седьмой версии Unix . ). Псевдокод:

algorithm quicksort(A, lo, hi) is if lo < hi then p:= pivot(A, lo, hi) left, right:= partition(A, p, lo, hi) // возвращается два значения quicksort(A, lo, left) quicksort(A, right, hi)

Оценка сложности алгоритма

Ясно, что операция разделения массива на две части относительно опорного элемента занимает время . Поскольку все операции разделения, проделываемые на одной глубине рекурсии, обрабатывают разные части исходного массива, размер которого постоянен, суммарно на каждом уровне рекурсии потребуется также O (n) {\displaystyle O(n)} операций. Следовательно, общая сложность алгоритма определяется лишь количеством разделений, то есть глубиной рекурсии. Глубина рекурсии, в свою очередь, зависит от сочетания входных данных и способа определения опорного элемента.

Лучший случай. В наиболее сбалансированном варианте при каждой операции разделения массив делится на две одинаковые (плюс-минус один элемент) части, следовательно, максимальная глубина рекурсии, при которой размеры обрабатываемых подмассивов достигнут 1, составит log 2 ⁡ n {\displaystyle \log _{2}n} . В результате количество сравнений, совершаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C n = 2 ⋅ C n / 2 + n {\displaystyle C_{n}=2\cdot C_{n/2}+n} , что даёт общую сложность алгоритма O (n ⋅ log 2 ⁡ n) {\displaystyle O(n\cdot \log _{2}n)} . Среднее. Среднюю сложность при случайном распределении входных данных можно оценить лишь вероятностно. Прежде всего необходимо заметить, что в действительности необязательно, чтобы опорный элемент всякий раз делил массив на две одинаковых части. Например, если на каждом этапе будет происходить разделение на массивы длиной 75 % и 25 % от исходного, глубина рекурсии будет равна , а это по-прежнему даёт сложность . Вообще, при любом фиксированном соотношении между левой и правой частями разделения сложность алгоритма будет той же, только с разными константами. Будем считать «удачным» разделением такое, при котором опорный элемент окажется среди центральных 50 % элементов разделяемой части массива; ясно, вероятность удачи при случайном распределении элементов составляет 0,5. При удачном разделении размеры выделенных подмассивов составят не менее 25 % и не более 75 % от исходного. Поскольку каждый выделенный подмассив также будет иметь случайное распределение, все эти рассуждения применимы к любому этапу сортировки и любому исходному фрагменту массива. Удачное разделение даёт глубину рекурсии не более log 4 / 3 ⁡ n {\displaystyle \log _{4/3}n} . Поскольку вероятность удачи равна 0,5, для получения k {\displaystyle k} удачных разделений в среднем потребуется 2 ⋅ k {\displaystyle 2\cdot k} рекурсивных вызовов, чтобы опорный элемент k раз оказался среди центральных 50 % массива. Применяя эти соображения, можно заключить, что в среднем глубина рекурсии не превысит 2 ⋅ log 4 / 3 ⁡ n {\displaystyle 2\cdot \log _{4/3}n} , что равно O (log ⁡ n) {\displaystyle O(\log n)} А поскольку на каждом уровне рекурсии по-прежнему выполняется не более O (n) {\displaystyle O(n)} операций, средняя сложность составит O (n log ⁡ n) {\displaystyle O(n\log n)} . Худший случай. В самом несбалансированном варианте каждое разделение даёт два подмассива размерами 1 и , то есть при каждом рекурсивном вызове больший массив будет на 1 короче, чем в предыдущий раз. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых. При простейшем выборе опорного элемента - первого или последнего в массиве, - такой эффект даст уже отсортированный (в прямом или обратном порядке) массив, для среднего или любого другого фиксированного элемента «массив худшего случая» также может быть специально подобран. В этом случае потребуется n − 1 {\displaystyle n-1} операций разделения, а общее время работы составит ∑ i = 0 n (n − i) = O (n 2) {\displaystyle \textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})} операций, то есть сортировка будет выполняться за квадратичное время. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти (переполнению стека) во время работы программы.

Достоинства и недостатки

Достоинства:

Недостатки:

Улучшения

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

• Проблема неустойчивости решается путём расширения ключа исходным индексом элемента в массиве. В случае равенства основных ключей сравнение производится по индексу, исключая, таким образом, возможность изменения взаимного положения равных элементов. Эта модификация не бесплатна - она требует дополнительно O(n) памяти и одного полного прохода по массиву для сохранения исходных индексов.

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

• Выбор среднего элемента. Устраняет деградацию для предварительно отсортированных данных, но оставляет возможность случайного появления или намеренного подбора «плохого» массива.
• Выбор медианы из трёх элементов: первого, среднего и последнего. Снижает вероятность возникновения худшего случая, по сравнению с выбором среднего элемента.
• Случайный выбор. Вероятность случайного возникновения худшего случая становится исчезающе малой, а намеренный подбор - практически неосуществимым. Ожидаемое время выполнения алгоритма сортировки составляет O(n lg n ).

Недостаток всех усложнённых методов выбора опорного элемента - дополнительные накладные расходы; впрочем, они не так велики.

• Во избежание отказа программы из-за большой глубины рекурсии могут применяться следующие методы:

	Имеется викиучебник по теме «Примеры реализации быстрой сортировки »

Псевдокод.
quickSort (массив a, верхняя граница N) { Выбрать опорный элемент p - середину массива Разделить массив по этому элементу Если подмассив слева от p содержит более одного элемента, вызвать quickSort для него. Если подмассив справа от p содержит более одного элемента, вызвать quickSort для него. } Реализация на Си.
template void quickSortR(T* a, long N) { // На входе - массив a, a[N] - его последний элемент. long i = 0, j = N-1; // поставить указатели на исходные места T temp, p; p = a[ N>>1 ]; // центральный элемент // процедура разделения do { while (a[i] < p) i++; while (a[j] > p) j--; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i<=j); // рекурсивные вызовы, если есть, что сортировать if (j > 0) quickSortR(a, j); if (N > i) quickSortR(a+i, N-i); }

Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.

Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n 2) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге... Вообще говоря, малореальная ситуация.

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

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

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

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

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

If (j > CUTOFF) quickSortR(a, j); if (N > i + CUTOFF) quickSortR(a+i, N-i);

Таким образом, массивы из CUTOFF элементов и меньше досортировываться не будут, и в конце работы quickSortR() массив разделится на последовательные части из <=CUTOFF элементов, отсортированные друг относительно друга. Близкие элементы имеют близкие позиции, поэтому, аналогично сортировке Шелла, вызывается insertSort(), которая доводит процесс до конца.

Template void qsortR(T *a, long size) { quickSortR(a, size-1); insertSort(a, size); // insertSortGuarded быстрее, но нужна функция setmax() }

1. В случае явной рекурсии, как в программе выше, в стеке сохраняются не только границы подмассивов, но и ряд совершенно ненужных параметров, таких как локальные переменные. Если эмулировать стек программно, его размер можно уменьшить в несколько раз.
2. Чем на более равные части будет делиться массив - тем лучше. Потому в качестве опорного целесообразно брать средний из трех, а если массив достаточно велик - то из девяти произвольных элементов.
3. Пусть входные последовательности очень плохи для алгоритма. Например, их специально подбирают, чтобы средний элемент оказывался каждый раз минимумом. Как сделать QuickSort устойчивой к такому "саботажу" ? Очень просто - выбирать в качестве опорного случайный элемент входного массива. Тогда любые неприятные закономерности во входном потоке будут нейтрализованы. Другой вариант - переставить перед сортировкой элементы массива случайным образом.
4. Быструю сортировку можно использовать и для двусвязных списков. Единственная проблема при этом - отсутствие непосредственного доступа к случайному элементу. Так что в качестве опорного приходится выбирать первый элемент, и либо надеяться на хорошие исходные данные, либо случайным образом переставить элементы перед сортировкой.

Рассмотрим наихудший случай, когда случайно выбираемые опорные элементы оказались очень плохими(близкими к экстремумам). Вероятность этого чрезвычайно мала, уже при n = 1024 она меньше 2 -50 , так что интерес скорее теоретический, нежели практический. Однако, поведение "быстрой сортировки" является "эталоном" для аналогично реализованных алгоритмов типа "разделяй-и-властвуй". Не везде можно свести вероятность худшего случая практически к нулю, поэтому такая ситуация заслуживает изучения.

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

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

Псевдокод.
Итеративная QuickSort (массив a, размер size) { Положить в стек запрос на сортировку массива от 0 до size-1. do { Взять границы lb и ub текущего массива из стека. do { 1. Произвести операцию разделения над текущим массивом a. 2. Отправить границы большей из получившихся частей в стек. 3. Передвинуть границы ub, lb чтобы они указывали на меньшую часть. } пока меньшая часть состоит из двух или более элементов } пока в стеке есть запросы } Реализация на Си.
#define MAXSTACK 2048 // максимальный размер стека template void qSortI(T a, long size) { long i, j; // указатели, участвующие в разделении long lb, ub; // границы сортируемого в цикле фрагмента long lbstack, ubstack; // стек запросов // каждый запрос задается парой значений, // а именно: левой(lbstack) и правой(ubstack) // границами промежутка long stackpos = 1; // текущая позиция стека long ppos; // середина массива T pivot; // опорный элемент T temp; lbstack = 0; ubstack = size-1; do { // Взять границы lb и ub текущего массива из стека. lb = lbstack[ stackpos ]; ub = ubstack[ stackpos ]; stackpos--; do { // Шаг 1. Разделение по элементу pivot ppos = (lb + ub) >> 1; i = lb; j = ub; pivot = a; do { while (a[i] < pivot) i++; while (pivot < a[j]) j--; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i <= j); // Сейчас указатель i указывает на начало правого подмассива, // j - на конец левого (см. иллюстрацию выше), lb ? j ? i ? ub. // Возможен случай, когда указатель i или j выходит за границу массива // Шаги 2, 3. Отправляем большую часть в стек и двигаем lb,ub if (i < ppos) { // правая часть больше if (i < ub) { // если в ней больше 1 элемента - нужно stackpos++; // сортировать, запрос в стек lbstack[ stackpos ] = i; ubstack[ stackpos ] = ub; } ub = j; // следующая итерация разделения // будет работать с левой частью } else { // левая часть больше if (j > lb) { stackpos++; lbstack[ stackpos ] = lb; ubstack[ stackpos ] = j; } lb = i; } } while (lb < ub); // пока в меньшей части более 1 элемента } while (stackpos != 0); // пока есть запросы в стеке }

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

Всем привет! Я расскажу об алгоритме быстрой сортировки и покажу, как его можно реализовать программно.

Итак, быстрая сортировка, или, по названию функции в Си, Qsort - это алгоритм сортировки, сложность которого в среднем составляет O(n log(n)). Суть его предельно проста: выбирается так называемый опорный элемент, и массив делится на 3 подмассива: меньших опорного, равных опорному и больших опорного. Потом этот алгоритм применяется рекурсивно к подмассивам.

Алгоритм

1. Выбираем опорный элемент
2. Разбиваем массив на 3 части
   • Создаём переменные l и r - индексы соответственно начала и конца рассматриваемого подмассива
   • Увеличиваем l, пока l-й элемент меньше опорного
   • Уменьшаем r, пока r-й элемент больше опорного
   • Если l всё ещё меньше r, то меняем l-й и r-й элементы местами, инкрементируем l и декрементируем r
   • Если l вдруг становится больше r, то прерываем цикл
3. Повторяем рекурсивно, пока не дойдём до массива из 1 элемента

Что ж, выглядит не так уж сложно. Реализуем на Си? Нет проблем!

void qsort (int b, int e)
{
int l = b, r = e;
int piv = arr[(l + r) / 2]; // Опорным элементом для примера возьмём средний
while (l <= r)
{
while (arr[l] < piv)
l++;
while (arr[r] > piv)
r--;
if (l <= r)
swap (arr, arr);
}
if (b < r)
qsort (b, r);
if (e > l)
qsort (l, e);
} /* ----- end of function qsort ----- */

// qsort (0, n-1);

* This source code was highlighted with Source Code Highlighter .

Эта реализация имеет ряд недостатков, таких как возможное переполнение стека из-за большого количества вложенной рекурсии и то, что опорным элементом всегда берётся средний. Для примера это, может, и нормально, но при решении, например, олимпиадных задач, хитрое жюри может специально подобрать такие тесты, чтобы на них это решение работало слишком долго и не проходило в лимит. В принципе, в качестве опорного элемента можно брать любой, но лучше, чтобы он был максимально приближен к медиане, поэтому можно выбрать его случайно или взять средний по значению из первого, среднего и последнего. Зависимость быстродействия от опорного элемента - один из недостатков алгоритма, ничего с этим не поделать, но сильная деградация производительности происходит редко, обычно если сортируется специально подобранный набор чисел. Если всё-таки нужна сортировка, работающая гарантированно быстро, можно использовать, например, пирамидальную сортировку, всегда работающую строго за O(n log n). Обычно Qsort всё же выигрывает в производительности перед другими сортировками, не требует много дополнительной памяти и достаточно прост в реализации, поэтому пользуется заслуженной популярностью.

Писáл сам, изредка поглядывая на Википедию . Пользуясь случаем, передаю спасибо замечательным преподавателям и студентам ПетрГУ, научившим меня множеству полезных вещей, в том числе и этому алгоритму!

Теги: Qsort, быстрая сортировка, алгоритмы сортировки, алгоритмы, C