Алгоритм быстрой сортировки си реализация. Быстрая сортировка - один из лучших методов сортировки массивов. Быстрая сортировка, нерекурсивный вариант

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

Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.

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

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

В этой статье приведены примеры реализации стандартных алгоритмов сортировки.

Сортировка выбором (Selection sort)

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

Код C++

void SortAlgo::selectionSort(int data, int lenD) { int j = 0; int tmp = 0; for (int i=0; idata[k]){ j = k; } } tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }

Пузырьковая сортировка (Bubble sort)

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

Код C++

void SortAlgo::bubbleSort(int data, int lenD) { int tmp = 0; for (int i = 0;i=(i+1);j--){ if (data[j]

Сортировка вставками (Insertion sort)

При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.

На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.

Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i].

Код C++

void SortAlgo::insertionSort(int data, int lenD) { int key = 0; int i = 0; for (int j = 1;j=0 && data[i]>key){ data = data[i]; i = i-1; data=key; } } }

Сортировка слиянием (Merge sort)

Код C++

void SortAlgo::mergeSort(int data, int lenD) { if (lenD>1){ int middle = lenD/2; int rem = lenD-middle; int * L = new int ; int * R = new int ; for (int i=0;i

Быстрая сортировка (Quick sort)

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

Код C++

void SortAlgo::quickSort(int * data, int const len) { int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1){ int * L = new int ; int * R = new int ; pivot = data; for (i=0;i

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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


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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include
#include
#define SIZE 20
// Функция быстрой сортировки
void quickSort(int *numbers, int left, int right)
{
int pivot; // разрешающий элемент
int l_hold = left; //левая граница
int r_hold = right; // правая граница
pivot = numbers;
while (left < right) // пока границы не сомкнутся
{
while ((numbers >= pivot) && (left < right))
right--; // сдвигаем правую границу пока элемент больше
if (left != right)
{
numbers = numbers; // перемещаем элемент на место разрешающего
left++; // сдвигаем левую границу вправо
}
while ((numbers <= pivot) && (left < right))
left++; // сдвигаем левую границу пока элемент меньше
if (left != right) // если границы не сомкнулись
{
numbers = numbers; // перемещаем элемент на место
right--; // сдвигаем правую границу вправо
}
}
numbers = pivot; // ставим разрешающий элемент на место
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
quickSort(numbers, left, pivot - 1);
if (right > pivot)
quickSort(numbers, pivot + 1, right);
}
int main()
{
int a;
// Заполнение массива случайными числами
for (int i = 0; i a[i] = rand() % 201 - 100;
// Вывод элементов массива до сортировки
for (int i = 0; i printf("%4d " , a[i]);
printf("\n" );
quickSort(a, 0, SIZE-1); // вызов функции сортировки
// Вывод элементов массива после сортировки
for (int i = 0; i printf("%4d " , a[i]);
printf("\n" );
getchar();
return 0;
}


Результат выполнения

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

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

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

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

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

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

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

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

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

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

Имеется массив целых чисел Mas , состоящий из 8 элементов (рис. 5.5): Mas . Начальным значением first будет 1, а last – 8. Пройденная часть закрашивается голубым цветом.

В качестве опорного элемента возьмем элемент со значением 5, и индексом 4. Его мы вычислили, используя выражение (first +last )/2, отбросив дробную часть. Теперь mid =5.

Первый элемент левой части сравнивается с mid . Mas >mid , следовательно first остается равным 1. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 8 и значением 8. Mas >mid , следовательно last смещается на одну позицию влево. Mas <mid , следовательно last остается равным 7. На данный момент first =1, а last =7. Первый и седьмой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.

Алгоритм снова переходит к сравнению элементов. Второй элемент сравнивается с опорным: Mas >mid, следовательно first остается равным 2. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 6 и значением 1: Mas <mid , следовательно last не изменяет своей позиции. На данный момент first =2, а last =6. Второй и шестой элементы меняются местами. Оба указателя смещаются на одну позицию каждый в своем направлении.

Алгоритм снова переходит к сравнению элементов. Третий элемент сравнивается с опорным: Mas <mid , следовательно first смещается на одну позицию вправо. Далее, элементы правой части сравниваются с mid . Проверяется элемент с индексом 5 и значением 9: Mas >mid , следовательно last смещается на одну позицию влево. Теперь first =last =4, а значит, условие first <last не выполняется, этап разбиения завершается.

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

Рекурсивное доупорядочивание

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

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

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

Код программы на C++:

#include "stdafx.h" #include #include using namespace std; const int n=7; int first, last; //функция сортировки void quicksort(int *mas, int first, int last) { int mid, count; int f=first, l=last; mid=mas[(f+l) / 2]; //вычисление опорного элемента do { while (mas[f]mid) l--; if (f<=l) //перестановка элементов { count=mas[f]; mas[f]=mas[l]; mas[l]=count; f++; l--; } } while (f>void"); }

#include "stdafx.h"

#include

#include

using namespace std ;

const int n = 7 ;

int first , last ;

//функция сортировки

void quicksort (int * mas , int first , int last )

int mid , count ;

int f = first , l = last ;

mid = mas [ (f + l ) / 2 ] ; //вычисление опорного элемента

while (mas [ f ] < mid ) f ++ ;

while (mas [ l ] > mid ) l -- ;

if (f <= l ) //перестановка элементов

count = mas [ f ] ;

mas [ f ] = mas [ l ] ;

mas [ l ] = count ;

f ++ ;

l -- ;

} while (f < l ) ;

if (first < l ) quicksort (mas , first , l ) ;

if (f < last ) quicksort (mas , f , last ) ;

//главная функция

void main ()

setlocale (LC_ALL , "Rus" ) ;

int * A = new int [ n ] ;

srand (time (NULL ) ) ;

cout << "Исходный массив: " ;

for (int i = 0 ; i < n ; i ++ )

A [ i ] = rand () % 10 ;

cout << A [ i ] << " " ;

first = 0 ; last = n - 1 ;

quicksort (A , first , last ) ;

cout << endl << "Результирующий массив: " ;

for (int i = 0 ; i < n ; i ++ ) cout << A [ i ] << " " ;

delete A ;

system ("pause>>void" ) ;

Код программы на Pascal:

Delphi/Pascal

program qsort; uses crt; const n=7; var A: array of integer; first, last, i: integer; {процедура сортировки} procedure quicksort(var mas: array of integer; first, last: integer); var f, l, mid, count: integer; begin f:=first; l:=last; mid:=mas[(f+l) div 2]; {вычисление опорного элемента} repeat while mas[f]mid do dec(l); if f<=l then {перестановка элементов} begin count:=mas[f]; mas[f]:=mas[l]; mas[l]:=count; inc(f); dec(l); end; until f>l; if first

program qsort ;

uses crt ;

const n = 7 ;

var A : array [ 1..n ] of integer ;

first , last , i : integer ;

{ процедурасортировки}

procedure quicksort (var mas : array [ 1..n ] of integer ; first , last : integer ) ;

var f , l , mid , count : integer ;

begin

f := first ;

l := last ;

mid := mas [ (f + l ) div 2 ] ; { вычислениеопорногоэлемента}

repeat

while mas [ f ] < mid do inc (f ) ;

while mas [ l ] > mid do dec (l ) ;

Описание

Функция 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; }

А лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за 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); }