Быстрая сортировка - один из лучших методов сортировки массивов. Алгоритмы и структуры данных для начинающих: сортировка Быстрая сортировка пример на си

Краткое описание алгоритма

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

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

Алгоритм

Быстрая сортировка использует стратегию «разделяй и властвуй ». Шаги алгоритма таковы:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом . С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана , но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.
2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного - справа от него. Обычный алгоритм операции:
   1. Два индекса - l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.
   2. Вычисляется индекс опорного элемента m.
   3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не превысит опорный.
   4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
   5. Если r = l - найдена середина массива - операция разделения закончена, оба индекса указывают на опорный элемент.
   6. Если l < r - найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.
3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.

Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится.

Интересно, что Хоар разработал этот метод применительно к машинному переводу : дело в том, что в то время словарь хранился на магнитной ленте , и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе , где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов).

//алгоритм на языке java public static void qSort(int A, int low, int high) { int i = low; int j = high; int x = A[ (low+ high) / 2 ] ; do { while (A[ i] < x) ++ i; while (A[ j] > x) -- j; if (i <= j) { int temp = A[ i] ; A[ i] = A[ j] ; A[ j] = temp; i++; j--; } } while (i < j) ; if (low < j) qSort(A, low, j) ; if (i < high) qSort(A, i, high) ; }

//алгоритм на языке pascal procedure qSort(var ar: array of real ; low, high: integer ) ; var i, j: integer ; m, wsp: real ; begin i: = low; j: = high; m: = ar[ (i+ j) div 2 ] ; repeat while (ar[ i] m) do j: = j- 1 ; if (i<= j) then begin wsp: = ar[ i] ; ar[ i] : = ar[ j] ; ar[ j] : = wsp; i: = i+ 1 ; j: = j- 1 ; end ; until (i > j) ; if (low

//алгоритм на языке Visual Basic //при первом вызове 2-ой аргумент должен быть равен 1 //3-ий аргумент должен быть равен числу элементов массива Sub qSort(ByVal ar() As double, ByVal low As Integer , ByVal high As Integer ) Dim i, j As Integer Dim m, wsp As double i = low j = high m = ar((i + j) \ 2 ) Do Until i > j Do While ar(i) < m i += 1 Loop Do While ar(j) > m j -= 1 Loop If (i <= j) Then wsp = ar(i) ar(i) = ar(j) ar(j) = wsp i += 1 j -= 1 End If Loop If (low < j) Then qSort(ar, low, j) If (i < high) Then qSort(ar, i, high) End Sub

Оценка эффективности

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

• Лучший случай. Для этого алгоритма самый лучший случай - если в каждой итерации каждый из подмассивов делился бы на два равных по величине массива. В результате количество сравнений, делаемых быстрой сортировкой, было бы равно значению рекурсивного выражения C N = 2C N/2 +N, что в явном выражении дает примерно N lg N сравнений. Это дало бы наименьшее время сортировки.
• Среднее. Даёт в среднем O(n log n ) обменов при упорядочении n элементов. В реальности именно такая ситуация обычно имеет место при случайном порядке элементов и выборе опорного элемента из середины массива либо случайно.
  На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n lg n ), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C N/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C N = N lg N.
• Худший случай. Худшим случаем, очевидно, будет такой, при котором на каждом этапе массив будет разделяться на вырожденный подмассив из одного опорного элемента и на подмассив из всех остальных элементов. Такое может произойти, если в качестве опорного на каждом этапе будет выбран элемент либо наименьший, либо наибольший из всех обрабатываемых.
  Худший случай даёт O(n ²) обменов. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Улучшения

• При выборе опорного элемента из данного диапазона случайным образом худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(n lg n ).
• Выбирать опорным элементом средний из трех (первого, среднего и последнего элементов). Такой выбор также направлен против худшего случая.
• Во избежание достижения опасной глубины рекурсии в худшем случае (или при приближении к нему) возможна модификация алгоритма, устраняющая одну ветвь рекурсии: вместо того, чтобы после разделения массива вызывать рекурсивно процедуру разделения для обоих найденных подмассивов, рекурсивный вызов делается только для меньшего подмассива, а больший обрабатывается в цикле в пределах этого же вызова процедуры . С точки зрения эффективности в среднем случае разницы практически нет: накладные расходы на дополнительный рекурсивный вызов и на организацию сравнения длин подмассивов и цикла - примерно одного порядка. Зато глубина рекурсии ни при каких обстоятельствах не превысит log 2 n, а в худшем случае вырожденного разделения она вообще будет не более 2 - вся обработка пройдёт в цикле первого уровня рекурсии.
• Разбивать массив не на две, а на три части (см. Dual Pivot Quicksort).

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

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

Недостатки:

Примечания

Литература

• Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. - М .: «Вильямс», 2006. - С. 174-179. - ISBN 5-8459-0987-2
• Кормен, Т. , Лейзерсон, Ч. , Ривест, Р. , Штайн, К. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. - 2-е изд. - М .: Вильямс, 2005. - С. 198-219. - ISBN 5-8459-0857-4

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 ).

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

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

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

Описание

Функция qsort выполняет сортировку num элементов массива, на который ссылается указатель first . Для каждого элемента массива устанавливается размер в байтах, который передается через параметр size . Последний параметр функции qsort — указатель comparator на функцию сравнения, которая используется для определения порядка следования элементов в отсортированном массиве.

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

Эта функция не возвращает никакого значения, но изменяет содержимое массива, на который указывает first . Таким образом, элементы массива занимают новые места, согласно отсортированному порядку.

Параметры:

• first
  Указатель на первый элемент сортируемого массива.
• number
  Количество элементов в сортируемом массиве, на который ссылается указатель first .
• size
  Размер одного элемента массива в байтах.
• comparator
  Функция, которая сравнивает два элемента. Функция должна иметь следующий прототип:

int funccmp(const void * val1, const void * val2);

Функция должна принимать два параметра — указатели на элементы массива, типа void* . Эти параметры должны быть приведены к определённым типам данных. Возвращаемое значение этой функции должно быть отрицательным, равным нулю или положительным. Если val1 меньше, равен или больше, чем val2 , функция должна вернуть отрицательное значение, ноль или положительное значение, соответственно.

Возвращаемое значение

Пример: исходный код программы

//пример использования функции qsort #include #include int vector = { 14, 10, 11, 19, 2, 25 }; int compare(const void * x1, const void * x2) // функция сравнения элементов массива { return (*(int*)x1 - *(int*)x2); // если результат вычитания равен 0, то числа равны, < 0: x1 < x2; > 0: x1 > x2 } int main () { qsort(vector, 6, sizeof(int), compare); // сортируем массив чисел for (int ix = 0; ix < 6; ix++) std::cout << vector << " "; return 0; }

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

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

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

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

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

А лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за n·log(n) шагов. В худшем случае сложность опускается до порядка n 2 , хотя такая ситуация довольно редкая. Быстрая сортировка обычно быстрее других "скоростных" сортировок со сложностью порядка n·log(n). Быстрая сортировка не устойчивая. Обычно, она преподносится как рекурсивная, однако, может быть с помощью стека (возможно, и без него, не проверено) сведена к итеративной, при этом потребуется не более n·log(n) дополнительной памяти.

Начнём с задачи, которую обычно называют Bolts & Nuts (Болты и Гайки). Вы пошли в магазин и купили болтов и гаек, много, целых два ведра. В одном ведре болты, в другом гайки. При этом известно, что для каждого болта из ведра есть соответствующая ему по размеру гайка, и для каждой гайки есть соответствующий по размеру болт. Одна беда - у вас отключили свет и вы не можете сравнить болт с болтом и гайку с гайкой. Вы можете сравнить только гайку с болтом и болт гайкой и проверить, подходят они друг другу или нет. Задача - найти для каждой гайки соответствующий ей болт.

Пусть у нас n пар болт-гайка. Самое простое решение - "в лоб" - берём гайку и находим для неё болт. Всего надо будет проверить n болтов. Поле этого берём вторую гайку, находим для неё болт, предстоит сделать уже n-1 проверку. И так далее. Всего надо будет сделать n + (n-1) + (n-2) + ... + 1 = n 2 /2 шагов. Существует ли более простое решение?

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

Возьмём любой (случайный) болт и с его помощью разобьём все гайки на те, которые меньше, и те которые больше, чем нужно для этого болта. Конечно, во время разбиения мы найдём и соответствующую ему гайку. Таким образом мы получим две кучи гаек - те, которые больше и те, которые меньше. С помощью найденной гайки разобьём все болты на те, которые меньше, и те, которые больше, чем первоначальный болт. Получим две кучи болтов, мелкие и крупные.

Далее, из кучи мелких болтов выберем случайный болт и с его помощью разобьём кучу гаек (тех, которые мелкие) на две кучи. Во время разбиения найдём подходящую гайку, с помощью которой разобьём мелкие болты на две кучи и т.д. То же самое проделаем и с большей кучей. Рекурсивно будем применять этот алгоритм к каждой "подкуче". Таким образом, предстоит сделать порядка n·log(n) шагов.

Алгоритм быстрой сортировки напоминает решение нашей задачи. Сначала мы находим опорный элемент - это случайный элемент из множества, относительно которого мы будем проводить разбиение. Далее разобьём множество на три - элементы, которые больше опорного, равны ему и элементы, которые меньше. После чего рекурсивно применим алгоритм к двум оставшимся подмножествам (меньше и больше), если их длина больше единицы.

Рекурсивное решение

Ф ункция принимает в качестве аргументов массив и левую и правую границу массива. В самом начале левая граница это 0, а правая - длина массива минус один. Нам понадобятся следующие переменные

Size_t i, j;

указывают на левый и правый элементы,

Int tmp, pivot;

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

I = low; j = high; pivot = a[(low + (high-low)/2)];

Здесь следует сразу же оговориться. Выбирать всегда средний элемент в качестве опорного – достаточно рискованно. Если известно, какой элемент будет выбран в качестве опорного, то можно подобрать такую последовательность, для которой сортировка будет происходить максимально медленно, за время порядка n 2 . Поэтому в качестве элемента, относительно которого будет сортировка, берут либо случайный элемент, либо медиану из первого, последнего и среднего элементов.

Пока i будет меньше j (пока они не пересекутся) делаем следующее. Во первых, нужно пропустить все уже отсортированные элементы

Do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; }

If (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; j--; } } while (i <= j);

Здесь, однако, возможна ошибка. i вряд ли переполнится - размер массива не больше, чем максимальное значение типа size_t, умноженное на размер элемента массива байт (более сложные варианты даже рассматривать не будем). Но вот переменная j вообще-то может перейти через нуль. Так как переменная целочисленная, то при переходе через нуль её значение станет больше, чем i, что приведёт к зацикливанию. Поэтому необходима превентивная проверка.

If (j > 0) { j--; }

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

If (i < high) { qsortx(a, i, high); } if (j > low) { qsortx(a, low, j); }

Void qsortx(int *a, size_t low, size_t high) { size_t i, j; int tmp, pivot; i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; } if (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > <= j); if (i < high) { qsortx(a, i, high); } if (j > low) { qsortx(a, low, j); } }

Функция называется qsortx, чтобы не спутать со стандартной функцией быстрой сортировки qsort.

Итеративное решение

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

Void qsortxi(int *a, size_t size) { size_t i, j; int tmp, pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size - 1); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = a[(low + (high-low)/2)]; do { while (a[i] < pivot) { i++; } while (a[j] > pivot) { j--; } if (i <= j) { if (a[i] > a[j]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; } i++; if (j > 0) { j--; } } } while (i <= j); if (i < high) { push(lows, i); push(highs, high); } if (j > low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); }

Код стека

#define STACK_INIT_SIZE 100 typedef struct Stack { size_t size; size_t limit; int *data; } Stack; Stack* createStack() { Stack *tmp = (Stack*) malloc(sizeof(Stack)); tmp->limit = STACK_INIT_SIZE; tmp->size = 0; tmp->data = (int*) malloc(tmp->limit * sizeof(int)); return tmp; } void freeStack(Stack **s) { free((*s)->data); free(*s); *s = NULL; } void push(Stack *s, int item) { if (s->size >= s->limit) { s->limit *= 2; s->data = (int*) realloc(s->data, s->limit * sizeof(int)); } s->data = item; } int pop(Stack *s) { if (s->size == 0) { exit(7); } s->size--; return s->data; }

Функция в общем виде

Void qsortxig(void *a, size_t item, size_t size, int (*cmp)(const void*, const void*)) { size_t i, j; void *tmp, *pivot; Stack *lows = createStack(); Stack *highs = createStack(); size_t low, high; push(lows, 0); push(highs, size - 1); tmp = malloc(item); while (lows->size > 0) { low = pop(lows); high = pop(highs); i = low; j = high; pivot = (char*)a + (low + (high-low)/2)*item; do { while (cmp(((char*)a + i*item), pivot)) { i++; } while (cmp(pivot, (char*)a + j*item)) { j--; } if (i <= j) { if (cmp((char*)a + j*item, (char*)a + i*item)) { memcpy(tmp, (char*)a + i*item, item); memcpy((char*)a + i*item, (char*)a + j*item, item); memcpy((char*)a + j*item, tmp, item); } i++; if (j > 0) { j--; } } } while (i <= j); if (i < high) { push(lows, i); push(highs, high); } if (j > low) { push(lows, low); push(highs, j); } } freeStack(&lows); freeStack(&highs); free(tmp); }