Perl

@out=(5,2,8,9,4,2,7,9,4,1,6,9,0); sub sortM{ my($array,$first,$last)=@_; if($last>$first){ my$middle=int(($last+$first)/2); sortM($array,$first,$middle); sortM($array,$middle+1,$last); my$j=0; $work[$j++]=$$array[$_]for($first..$last); $middle=int(($first+$last)/2)if($middle>$last); my$n=$middle-$first+1; for($i=$first,$j=0,$k=$n;$i<=$last;$i++){ if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){ $$array[$i]=$work[$j++] }else{ $$array[$i]=$work[$k++]; } } } } sortM(\@out,0,$#out+1);

Паскаль (сортировка текстовых файлов)

Сортировка простым слиянием

Procedure MergeSort(name: string; var f: text); Var a1,a2,s,i,j,kol,tmp: integer; f1,f2: text; b: boolean; Begin kol:=0; Assign(f,name); Reset(f); While not EOF(f) do begin read(f,a1); inc(kol); End; Close(f); Assign(f1,"{имя 1-го вспомогательного файла}"); Assign(f2,"{имя 2-го вспомогательного файла}"); s:=1; While (s0 then begin tmp:=kol div 2; While tmp mod s<>0 do begin Read(f,a1); Write(f1,a1," "); inc(tmp); End; End; While not EOF(f) do begin Read(f,a2); Write(f2,a2," "); End; Close(f); Close(f1); Close(f2); Rewrite(f); Reset(f1); Reset(f2); Read(f1,a1); Read(f2,a2); While (not EOF(f1)) and (not EOF(f2)) do begin i:=0; j:=0; b:=true; While (b) and (not EOF(f1)) and (not EOF(f2)) do begin If (a1

Сортировка естественным слиянием

Procedure MergeSort(name: string; var f: text); Var s1,s2,a1,a2,where,tmp: integer; f1,f2: text; Begin s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while} Assign(f,name); Assign(f1,"{имя 1-го вспомогательного файла}"); Assign(f2,"{имя 2-го вспомогательного файла}"); While (s1>1) and (s2>=1) do begin where:=1; s1:=0; s2:=0; Reset(f); Rewrite(f1); Rewrite(f2); Read(f,a1); Write(f1,a1," "); While not EOF(f) do begin read(f,a2); If (a2

Delphi (сортировка произвольных типов данных - простое слияние)

Unit uMergeSort; interface type TItem = Integer; //Здесь можно написать Ваш произвольный тип TArray = array of TItem; procedure MergeSort(var Arr: TArray); implementation function IsBigger(d1, d2: TItem) : Boolean; begin Result:= (d1 > d2); //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа. //Сюда можно добавить счетчик сравнений end; //Процедура сортировки слияниями procedure MergeSort(var Arr: TArray); var tmp: TArray; //Временный буфер //Слияние procedure merge(L, Spl, R: Integer); var i, j, k: Integer; begin i:= L; j:= Spl + 1; k:= 0; //Выбираем меньший из первых и добавляем в tmp while (i <= Spl) and (j <=R) do begin if IsBigger(Arr[i], Arr[j]) then begin tmp[k] := Arr[j]; Inc(j); end else begin tmp[k] := Arr[i]; Inc(i); end; Inc(k); end; //Просто дописываем в tmp оставшиеся эл-ты if i <= Spl then //Если первая часть не пуста for j:= i to Spl do begin tmp[k] := Arr[j]; Inc(k); end else //Если вторая часть не пуста for i:= j to R do begin tmp[k] := Arr[i]; Inc(k); end; //Перемещаем из tmp в arr Move(tmp, Arr[L], k*SizeOf(TItem)); end; //Сортировка procedure sort(L, R: Integer); var splitter: Integer; begin //Массив из 1-го эл-та упорядочен по определению if L >= R then Exit; splitter:= (L + R) div 2; //Делим массив пополам sort(L, splitter); //Сортируем каждую sort(splitter + 1, R); //часть по отдельности merge(L, splitter, R); //Производим слияние end; //Основная часть процедуры сортировки begin SetLength(tmp, Length(Arr)); sort(0, Length(Arr) - 1); SetLength(tmp, 0); end; end.

D

Void mergeSort(int array) { static void merge(int array, int q) { int leftArray = array.dup ~ int.max; int rightArray = array.dup ~ int.max; int i = 0; int j = 0; int length = array.length; for (int k = 0; k < length; ++k) { array[k] = (leftArray[i] <= rightArray[j]) ? leftArray : rightArray; } } if (array.length > 1) { int q = array.length / 2; mergeSort(array); mergeSort(array); merge(array, q); } }

Python 2.7 (функциональная реализация)

Def merge(right, left, result): result.append((left if left < right else right).pop(0)) return merge(right=right, left=left, result=result) if left and right else result+left+right merge_sort = (lambda arr: arr if len(arr) == 1 else merge(merge_sort(arr), merge_sort(arr[:len(arr)/2]), ))

Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).

При написании статьи были использованы открытые источники сети интернет:

Сортировка слиянием

(См. стр. 430 Ф.М. Каррано и Дж.Дж.Причард)

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

Алгоритм сортировки методом слияний является рекурсивным. Его эффективность не за­висит от порядка следования элементов в ис­ходном массиве. Допустим, что мы разделили массив пополам, рекурсивно упорядочили обе половины, а затем объединили их в одно целое, как показано на рис. 9.8. На рисунке показано, что части массива <1, 4, 8> и <2, 3> объединяются в массив <1, 2, 3, 4, 8>. В ходе слияния элементы, стоящие в разных частях массива, по­парно сравниваются друг с другом, и меньший элемент отправляется во временный массив. Этот процесс продолжается до тех пор, пока не будет использована одна из двух частей массива. Теперь достаточно просто скопировать оставшиеся элементы во временный массив. В заключение содержимое временного массива копируется обратно в исходный массив.

Рис. 9.8. Сортировка методом слияния с помощью вспомогательного массива

Хотя в результате слияния возникает упорядоченный массив, остается неясным, как выполняется сортировка на предыдущих этапах. Сортировка слиянием выполняется рекурсивно. Ее псевдокод имеет следующий вид.

mergesort(inout theArray:ItemArray,

in first:integer, in last: integer)

// Упорядочивает отрезок theArray,

// 1) сортируя первую половину массива;

// 2) сортируя вторую половину массива;

// 3) объединяя две упорядоченные половины массива.

If (first < last)

mid = (first + last)/2 // Определяем середину

// Сортируем отрезок theArray mergesort(theArray, first, mid)

// Сортируем отрезок theArray mergesort(theArray, mid + 1, last)

// Объединяем упорядоченные отрезки theArray

// и theArray

merge(theArray, first, mid, last)

} // Конец оператора if

// Если first >= last, операции завершены

Совершенно ясно, что основные операции этого алгоритма выполняются на этапе слияния, и все же, почему в результате возникает упорядоченный массив? Рекурсивные вызовы продолжают разделять части массива пополам, пока в них не останется только по одному элементу. Очевидно, что массив, состоящий из одного элемента, является упорядоченным. Затем алгоритм объединяет фрагменты массива, пока не образуется один упорядоченный массив. Рекурсивные вызовы функции mergesort и результаты слияний проиллюстрированы на рис. 9.9 на примере массива, состоящего из шести целых чисел.

Рис. 9.9. Сортировка методом слияния массива, состоящего из шести целых чисел

Ниже приведена функция на языке C++, реализующая алгоритм сортировки методом слияний. Для того чтобы упорядочить массив theArray, состоящий из n элементов, выполняется рекурсивный вызов mergesort (theArray, 0, n-1).

const int MAX_SIZE = максимальное-количество-элементов-массива,-

void merge(DataType theArray, int first, int mid, int last)

// Объединяет два упорядоченных отрезка theArray и

//theArray в один упорядоченный массив.

// Предусловие: first <= mid <= last. Оба подмассива

// theArray и theArray упорядочены

// по возрастанию.

// Постусловие: отрезок theArray упорядочен.

// Замечание о реализации: функция выполняет слияние двух

// подмассивов во временный массив, а затем копирует его

// содержимое в исходный массив theArray.

// _________________________________________________________

Анализ. Поскольку основные операции в этом алгоритме выполняются на этапе слияния, начнем анализ с него. На каждом шаге происходит объединение подмассивов theArray и theArray . На рис. 9.10 показан пример, в котором требуется выполнить максимальное количество сравнений. Если общее количество элементов объединяемых отрезков массива равно п, то при их слиянии потребуется выполнить п-1 сравнений. (Например, на рис. 9.10 показан массив, состоящий из шести элементов, следовательно, выполняется пять сравнений.) Кроме того, после сравнений осуществляется копиров­ние п элементов временного массива в исходный. Таким образом, на каждом шаге слияния выполняется 3*п-1 основных операций.

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

Каждый вызов функции mergesort делит массив пополам. На первом этапе исходный массив оказывается разделенным на две части. При следующем рекурсивном вызове функции mergesort каждая из этих частей снова делится пополам, образуя четыре части исходного массива. При следующем рекурсивном вызове каждая из этих четырех частей опять делится пополам, образуя восемь частей массива и т.д. Рекурсивные вызовы продолжаются до тех пор, пока части массива не станут содержать только по одному элементу, иными словами, пока исходный массив не будет разбит на п частей, что соответствует количеству его элементов, если число п является степенью двойки (n=2 m), глубина рекурсии равна k=log 2 n Например, как показано на рис. 9.11, если исходный массив содержит восемь элементов (8=2 3), то глубина рекурсии равна 3. Если число п неявляется степенью двойки, глубина рекурсии равна 1+ log 2 n (округленное значение).

Исходный вызов функции mergesort (ypoвень 0) обращается к функции merge только один раз. Затем функция merge осуществляет слияние п элементов, выполняя 3*n-1 операций. На первом уровне рекурсии выполняются два вызова функции mergesort и, следовательно, функции merge. Каждый из этих двух вызовов приводит к слиянию n/2 элементов и требует вы­полнения 3*(n/2)-1 операций. Таким образом, на этом уровне выполняется 2*(3*(n/2)-1)=3*n-2 операций. На m-м уровне рекурсии выполняются 2 т вызовов функции merge. Каждый из этих вызовов приводит к слиянию п/2 т элементов, а общее количество операций равно 3*(n/2 m)-2. В целом, 2 m рекурсивных вызова функции merge порождает 3*n-2 m операций. Таким образом, на каждом уровне рекурсии выполняется О(л) операций. Поскольку количество уровней рекурсии равно log 2 n или log 2 n+l, в наихудшем и среднем вариантах функция mergesort имеет сложность O(n*log 2 n). Посмотрите на рис. 9.3 и еще раз убедитесь, что величина O(n*log 2 n) растет намного медленнее, чем величина О(п г).

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

Объединить упорядоченные подмассивы theArray и theArray

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

Разбиение, показанное на рис. 9.12, характе­ризуется тем, что все элементы множества Si=theArray меньше опорного элемента р, а множество S 2 = theArray состоит из элементов, больших или равных опорному. Хотя из этого свойства не следует, что массив упорядочен, из него вытекает чрезвычайно полезный факт: если массив упорядочен, элементы, стоящие на позициях от first до pivotlndex-l, остаются на своих местах, хотя их позиции относительно друг друга могут измениться. Аналогичное утверждение выполняется и для элементов, стоящих на позициях от pivotlndex+l до last. Опорный элемент в полученном упорядоченном массиве останется на своем месте.

Такое разбиение массива определяет рекур­сивный характер алгоритма. Разбиение массива относительно опорного элемента р порождает две задачи сортировки меньшего размера - сортировка левой (S 1) и правой (S 2) частей массива. Решив эти две задачи, мы получим решение исходной задачи. Иными словами, разбиение массива перед рекур­сивными вызовами оставляет опорный элемент на своем месте и гарантирует, что левый и правый отрезки массива окажутся упорядоченными. Кроме того, алго­ритм быстрой сортировки конечен: размеры левого и правого отрезка массива меньше размера исходного массива, причем каждый шаг рекурсии приближает нас к базису, когда массив состоит из одного элемента. Это следует из того факта, что опорный элемент р не принадлежит ни одному из массивов S l и S 2 .

Псевдокод алгоритма быстрой сортировки выглядит следующим образом.

quicksort (inout theArray .- ItemArray,

in first:integer, in last:integer) // Упорядочивает массив theArray

if (first < last)

Выбрать опорный элемент р из массива theArray Разбить массив theArray относительно

опорного элемента р // Разбиение имет вид theArray

// Упорядочиваем массив SI

quicksort(theArray, first, pivotlndex-l)

// Упорядочиваем массив S2

quicksort(theArray, pivotlndex+l, last) } // Конец оператора if // если first >= last, ничего не делаем

Как выбрать опорный элемент? Если элемен­ты массива записаны в произвольном порядке, в качестве опорного можно выбрать любой эле­мент, например theArray . (Более де­тально процедура выбора опорного элемента будет рассмотрена позднее.) При раз­биении массива опорный элемент удобно помещать в ячейку theArray , независимо от того, какой именно элемент выбран в качестве опорного.

Часть массива, в которой находятся элементы, еще не распределенные по от­резкам S1 и S 2 , называется неопределенной. Итак, рассмотрим массив, изобра­женный на рис. 9.14. Индексы first, lastS1, firstUnknown и last разделяют массив на три части. Отношения между опорным элементом и элементами неоп­ределенной части theArray неизвестны.

Puc. 9.14. Инвариант алгоритма разбиения

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

Элементы множества S1 должны быть меньше опорного элемента, а элементы множества S 2 - больше или равны ему.

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

first firstUnknown last

Puc. 9.15. Исходное состояние массива

На каждом шаге алгоритма разбиения проверяется один элемент из неопреде­ленной части. В зависимости от его значения он помещается в множество S1 или S 2 . Таким образом, на каждом шаге размер неопределенной части уменьшается на единицу. Алгоритм останавливается, когда размер неопределенной части становится равным нулю, т.е. выполняется условие firstUnknown > last.

Рассмотрим псевдокод этого алгоритма.

partition (inout theArray:ItemArray,

in first:integer, in last:integer,

out pivotlndex:integer) // Разделяет массив theArray

// Инициализация

Выбрать опорный элемент и поменять его местами

с элементом theArray
р = theArray // p - опорный элемент

// Задаем пустые множества S1 и S 2 , а неопределенную // часть массива инициализируем отрезком

// theArray lastSl = first firstUnknown = first + 1

// Определяем множества Sj и S 2 while (firstUnknown <= last)

// Вычисляем индекс самого левого элемента // неопределенной части массива if (theArray < р)

Поместить элемент theArray в Si else

Поместить элемент theArray в S 2 } // Конец оператора while

// Ставим опорный элемент между множествами S 2 и S 2 // и запоминаем его новый индекс

Поменять местами theArray и theArray pivotlndex = lastSl

Алгоритм достаточно прост, но операция перемещения требует разъяснения. Рассмотрим два возможных действия, которые необходимо выполнить на каждой итерации цикла while.

Поместить элемент theArray в множество S t . Множество S1 и неопределенная часть, как правило, не являются смежными. Обычно между ними располагается множество S 2 . Однако эту операциюможно выполнить более эффективно. Элемент theArray можно поменять местами с первым элементом множества S 2 , т.е. с элементом theArray , как показано на рис. 9.16. Как быть сэлементом множества S 2 , который был помещен в ячейку theArray? Если увеличить индекс firstUnknown на единицу, этот элемент становится самым правым в множестве S 2 . Таким образом, для переноса элемента theArray в массив S1 необходимо выполнить следующие шаги.

Поменять местами элементы theArray

и theArray Увеличить индекс lastSl на единицу Увеличить индекс firstUnknown на единицу

Эта стратегия остается верной, даже если множество S 2 пусто. В этом случае величина lastSl+l равна индексу firstUnknown, и элемент просто остается на своем месте.

Поместить элемент theArray в множество S 2 . Эту операцию легко выполнить. Напомним, что индекс крайнего правого элемента множества S 2 равен firstUnknown-1, т.е. множество S 2 и неизвестная часть являются смежными (рис. 9.17). Таким образом, чтобы переместить элемент theArray в множество S 2 , нужно просто увеличить индекс firstUnknown на единицу, расширяя множество S 2 вправо.Инвариант при этом не нарушается.

После переноса всех элементов из неопределенной части в множества S 1 и S 2 остается решить последнюю задачу. Нужно поместить опорный элемент между множествами S1 и S 2 . Обратите внимание, что элемент theArray явля-

Рис. 9.17. Перенос элемента theArray в множество S2 после увеличения индекса firstUnknown на единицу

ется крайним правым элементом множества S1. Если поменять его местами с опорным элементом, тот станет на правильное место. Следовательно, оператор

pivotlndex = lastSl

позволяет определить индекс опорного элемента. Этот индекс можно использо­вать в качестве границы между множествами Sj и 5г. Результаты трассировки алгоритма разбиения массива, состоящего из шести целых чисел, когда опорным является первый элемент, показаны на рис. 9.18.

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

Все элементы множества S 2 (theArray) меньше опорно­го, а все элементы множества S 2 (theArray) больше или равны опорному

Напомним, что для определения правильности алгоритма с помощью его инва­риантов, необходимо выполнить четыре шага.

1. Инвариант должен быть истинным с самого начала, до выполнения цикла. В алгоритме разбиения опорным элементом является theArray , неизвестной частью- отрезок массива theArray , a множества S1 и S 2 пусты. Очевидно, что при этих условиях инвариант является истинным.

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

3. Инвариант должен определять корректность алгоритма. Иными словами, из истинности инварианта должна следовать корректность алгоритма. Выполнение алгоритма разбиения прекращается, когда неопределенная область становится пустой. В этом случае каждый элемент отрезка theArray должен принадлежать либо множеству S1, либо множеству S2. В любом случае из корректности инварианта следует, что
алгоритм достиг своей цели.

4. Цикл должен быть конечным. Иными словами, нужно показать, что выполнение цикла завершится после конечного числа итераций. В алгоритме разбиения размер неопределенной части на каждой итерации уменьшается на единицу. Следовательно, после выполнения конечного количества итераций неопределенная часть становится пустой, и цикл завершается.

Рис. 9.18. Первое разбиение массива, когда опорным является первый элемент

Перед вызовом функции quicksort выполняется разбиение массива на части S1 и S2. Затем алгоритм упорядочивает отрезки S1 и S2 независимо друг от друга, поскольку любой элемент отрезка S1 находится левее любого элемента отрезка S2. В функции mergeSort, наоборот, перед рекурсивными вызовами никакая работа не выполняется. Алгоритм упорядочивает каждую из частей массива, по­стоянно учитывая отношения между элементами обеих частей. По этой причине алгоритм должен объединять две половины массива после выполнения рекурсивных вызовов.

Анализ. Основная работа в алгоритме quicksort выполняется на этапе раз­биения массива. Анализируя каждый элемент, принадлежащий неопределенной части, необходимо сравнивать элемент theArray с опорным и помещать его либо в отрезок S1, либо в отрезок S2. Один из отрезков S1 или S2 может быть пустым; например, если опорным элементом является наименьший элемент отрезка, множество S1 останется пустым. Это происходит в наихудшем случае, поскольку размер отрезка S2 при каждом вызове функции quicksort уменьшается только на единицу. Таким образом, в этой ситуации будет выпол­нено максимальное количество рекурсивных вызовов функции quicksort.

При следующем рекурсивном вызове функции quicksort функция partition просмотрит п-1 элемент. Чтобы распределить их по отрезкам, понадобится п-2 сравнений. Поскольку размер отрезка, рассматриваемого функцией quicksort, на каждом уровне рекурсии уменьшается только на единицу, возникнет п-1 уровней рекурсии. Следовательно, функция quicksort выполняет 1 + 2 + ...+ (n-1) = n * (n-1)/2 сравнений. Напомним, однако, что при переносе элемента в множество S2 вы­полнять перестановку элементов не обязательно. Для этого достаточно лишь из­менить индекс firstUnknown.

Аналогично, если множество S2 при каждом рекурсивном вызове остается пус­тым, потребуется n * (n-1)/2 сравнений. Кроме того, в этом случае для переноса каждого элемента из неизвестной части в множество S1 придется выполнять пере­становку элементов. Таким образом, понадобится * (n-1)/2 перестановок. (На­помним, что каждая перестановка выполняется с помощью трех операций при­сваивания.) Итак, в худшем случае сложность алгоритма quicksort равна О(n2).

Для контраста на рис. 9.20 продемонстрирован пример, когда множества S1 и S2 состоят из одинакового количества элементов. В среднем случае, когда мно­жества S1 и S2 состоят из одинакового - или приблизительно одинакового - количества элементов, записанных в произвольном порядке, рекурсивных вызо­вов функции quicksort потребуется меньше. Как и при анализе алгоритма mergeSort, легко показать, что глубина рекурсии в алгоритме quicksort равна log2n или log2n+l. При каждом вызове функции quicksort выполняется m сравнений и не больше, чем m перестановок, где m - количество элементов в подмассиве, подлежащем сортировке.

Быстрая сортировка: наихудший вариант О(п 2), средний вариант O(n*logn).

Таким образом, с большими массивами алгоритм

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

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

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

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

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

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

Программа 8.4. Сортировка слиянием без копирования

Данная рекурсивная программа сортирует массив b, помещая результат сортировки в массив a. Поэтому рекурсивные вызовы написаны так, что их результаты остаются в массиве b, а для их слияния в массив a используется программа 8.1. Таким образом, все пересылки данных выполняются во время слияний.

template void mergesortABr(Item a, Item b, int l, int r) { if (r-l <= 10) { insertion(a, l, r); return; } int m = (l+r)/2; mergesortABr(b, a, l, m); mergesortABr(b, a, m+1, r); mergeAB(a+l, b+l, m-l+1, b+m+1, r-m); } template void mergesortAB(Item a, int l, int r) { static Item aux; for (int i = l; i <= r; i++) aux[i] = a[i]; mergesortABr(a, aux, l, r); }

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

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

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

Упражнения

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

8.17. Выполните сортировку слиянием больших случайно упорядоченных файлов и экспериментально определите среднюю длину другого подфайла на момент исчерпания первого подфайла как функцию от N (сумма длин двух сливаемых подфайлов).

8.18. Предположим, программа 8.3 модифицирована так, что не вызывает метод merge при a[m] < a . Сколько сравнений экономится в этом случае, если сортируемый файл уже упорядочен?

8.19. Выполните модифицированный алгоритм, предложенный в упражнении 8.18, для больших случайно упорядоченных файлов. Экспериментально определите среднее количество пропусков вызова merge в зависимости от N (размер исходного сортируемого файла).

8.20. Допустим, что сортировка слиянием должна быть выполнена на h-сортированном файле для небольшого значения h. Какие изменения нужно внести в подпрограмму merge, чтобы воспользоваться этим свойством входных данных? Поэкспериментируйте с гибридами сортировки методом Шелла и сортировки слиянием, основанными на этой подпрограмме.

8.21. Разработайте реализацию слияния, уменьшающую требование дополнительной памяти до max(M, N/M) за счет следующей идеи. Разбейте массив на N/M блоков размером M (для простоты предположим, что N кратно M). Затем, (1) рассматривая эти блоки как записи, первые ключи которых являются ключами сортировки, отсортируйте их с помощью сортировки выбором, и (2) выполните проход по массиву, сливая первый блок со вторым, затем второй блок с третьим и так далее.

8.22. Докажите, что метод, описанный в упражнении 8.21, выполняется за линейное время.

8.23. Реализуйте битоническую сортировку слиянием без копирования.

Восходящая сортировка слиянием

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

Рассмотрим последовательность слияний, выполняемую рекурсивным алгоритмом. Из примера, приведенного на рис. 8.2 , видно, что файл размером 15 сортируется следующей последовательностью слияний:

1-и-1 1-и-1 2-и-2 1-и-1 1-и-1 2-и-2 4-и-4

1-и-1 1-и-1 2-и-2 1-и-1 2-и-1 4-и-3 8-и-7.

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

1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1

2-и-2 2-и-2 2-и-2 2-и-1 4-и-4 4-и-3 8-и-7.

Рис. 8.4.

В каждой строке показан результат вызова метода merge при выполнении восходящей сортировки слиянием. Вначале выполняются слияния 1-и-1 : при слиянии A и S получается A S ; при слиянии O и R получается O R и т.д. Из-за нечетности размера файла последнее E не принимает участие в слиянии. На втором проходе выполняются слияния 2-и-2 : A S сливается с O R , и получается A O R S и т.д., до последнего слияния 2-и-1 . После этого выполняются слияния 4-и-4 , 4-и-3 и завершающее 8-и-7 .

В обоих случаях выполняются семь слияний 1-и-1 , три слияния 2-и-2 и по одному слиянию 2-и-1, 4-и-4, 4-и-3 и 8-и-7 , но они выполняются в различном порядке. Восходящая стратегия предлагает сливать наименьшие из оставшихся файлов, проходя по массиву слева направо.

Последовательность слияний, выполняемая рекурсивным алгоритмом, определяется деревом " разделяй и властвуй " , показанным на рис. 8.3 : мы просто выполняем обратный проход по этому дереву. Как было показано в "Элементарные структуры данных" , можно разработать нерекурсивный алгоритм, использующий явный стек, который даст ту же последовательность слияний. Однако совсем не обязательно ограничиваться только обратным порядком: любой проход по дереву, при котором обход поддеревьев узла завершается перед посещением самого узла, дает правильный алгоритм. Единственное ограничение заключается в том, что сливаемые файлы должны быть предварительно отсортированы. В случае сортировки слиянием удобно сначала выполнять все слияния 1-и-1 , затем все слияния 2-и-2 , затем все 4-и-4 , и так далее. Такая последовательность соответствует обходу дерева по уровням, который поднимается по дереву снизу вверх.

В "Рекурсия и деревья" мы уже видели на нескольких приме -рах, что при рассуждении в стиле снизу-вверх имеет смысл переориентировать мышление в сторону стратегии " объединяй и властвуй " , когда сначала решаются небольшие подзадачи, а затем они объединяются для получения решения большей задачи. В частности, нерекурсивный вариант вида " объединяй и властвуй " сортировки слиянием в программе 8.5 получается следующим образом: вначале все элементы файла рассматриваются как упорядоченные подсписки длиной 1. Потом для них выполняются слияния 1-и-1 , и получаются упорядоченные подсписки размером 2, затем выполняется серия слияний 2-и-2 , что дает упорядоченные подсписки размером 4, и так далее до упорядочения всего списка. Если размер файла не является степенью 2, то последний подсписок не всегда имеет тот же размер, что и все другие, но его все равно можно слить.

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

Если размер файла не равен степени 2, восходящий алгоритм дает другое множество слияний, как показано на рис. 8.5 . Восходящий алгоритм соответствует дереву " объединяй и властвуй " (см. упражнение 5.75), отличному от дерева " разделяй и властвуй " , которое соответствует нисходящему алгоритму. Можно сделать так, чтобы последовательность слияний, выполняемых рекурсивным методом, была такой же, как и для нерекурсивного метода, однако для этого нет особых причин, поскольку разница в производительности невелика по отношению к общим затратам.

Если размер файла не равен степени 2, то структуры слияний для восходящей сортировки слиянием совершенно не похожи на структуры слияний для нисходящей сортировки ( рис. 8.3). При восходящей сортировке размеры всех файлов (возможно, за исключением последнего) равны степени 2. Эти различия помогают понять базовую структуру алгоритмов, но почти не влияют на производительность.

Леммы 8.1-8.4 справедливы и для восходящей сортировки слиянием, при этом имеют место следующие дополнительные леммы:

Лемма 8.5. Все слияния на каждом проходе восходящей сортировки слиянием манипулируют файлами, размер которых равен степени 2, за исключением, возможно, размера последнего файла.

Это факт легко доказать методом индукции.

Лемма 8.6. Количество проходов при восходящей сортировке слиянием по файлу из N элементов в точности равно числу битов в двоичном представлении N (без ведущих нулей). Размер подсписков после к проходов равен 2 k , т.к. на каждом проходе восходящей сортировки слиянием размер упорядоченных подфайлов удваивается. Значит, количество проходов, необходимое для сортировки файла из N элементов, есть наименьшее к такое, что , что в точности равно , т.е. количеству битов в двоичном представлении N. Этот результат можно доказать и методом индукции или с помощью анализа структурных свойств деревьев " объединяй и властвуй " . ¦

Программа 8.5. Восходящая сортировка слиянием

Восходящая сортировка слиянием состоит из последовательности проходов по всему файлу с выполнением слияний вида m-и-m и с удвоением m на каждом проходе. Последний подфайл имеет размер m лишь тогда, когда размер файла является четным кратным m, так что последнее слияние имеет тип m-и-х , для некоторого х, меньшего или равного m.

Подводя итоги, отметим, что нисходящая и восходящая сортировки - это два простых алгоритма сортировки, основанных на операции слияния двух упорядоченных подфайлов в результирующий объединенный упорядоченный файл. Оба алгоритма тесно связаны между собой и даже выполняют одно и то же множество слияний, если размер исходного файла является степенью 2, но они отнюдь не идентичны. На рис. 8.7 демонстрируются различия динамических характеристик алгоритмов на примере большого файла. Каждый алгоритм может использоваться на практике, если экономия памяти не важна, и желательно гарантированное время выполнения в худшем случае. Оба алгоритма представляют интерес как прототипы общих принципов построения алгоритмов: " разделяй и властвуй " и " объединяй и властвуй " .

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

Упражнения

8.24. Покажите, какие слияния выполняет восходящая сортировка слиянием (программа 8.5) для ключей E A S Y Q U E S T I O N .

8.25. Реализуйте восходящую сортировку слиянием, которая начинает с сортировки вставками блоков по M элементов. Определите эмпирическим путем значение M, для которого разработанная программа быстрее всего сортирует произвольно упорядоченные файлы из N элементов, при N = 10 3 , 10 4 , 10 5 и 10 6 .

8.26. Нарисуйте деревья, которые отображают слияния, выполняемые программой 8.5 для N = 16, 24, 31, 32, 33 и 39 .

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

8.28. Напишите программу восходящей сортировки слиянием, выполняющую те же слияния, что и нисходящая сортировка слиянием. (Это упражнение намного труднее, чем упражнение 8.27).

8.29. Предположим, что размер файла является степенью 2. Удалите рекурсию из нисходящей сортировки слиянием так, чтобы получить нерекурсивную сортировку слиянием, выполняющую ту же последовательность слияний.

8.30. Докажите, что количество проходов, выполняемых нисходящей сортировкой слиянием, также равно количеству битов в двоичном представлении числа N (см. лемму 8.6).

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

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

разбить имеющиеся отсортированные цепочки на пары, и осуществить слияние цепочек каждой пары;

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

Проще всего формализовать этот алгоритм рекурсивным способом (в следующем разделе мы реализуем этот алгоритм итерационным способом). Функция сортирует участок массива от элемента с номером a до элемента с номером b:

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

void MergeSort(char* M, int c)

if(c<2)return;// если размер меньше 2 то он упорядочен

MergeSort(M,c/2);//отсортировать рекурсивно первую

//половину

MergeSort(M+c/2,c-c/2);// оставшуюся часть

char* T=(char*)malloc(c*sizeof(char));

Merge(M,c/2,M+c/2,c-c/2,T);//объеденить в один

for(int i=0;i

Листинг 2. Реализация сортировки слиянием

3.Нисходящая сортировка слиянием.

Имея в своем распоряжении процедуру слияния, нетрудно воспользоваться ею в качестве основы для рекурсивной процедуры сортировки. Чтобы отсорти­ровать заданный файл, мы делим его на две части, выполняем рекурсивную сортировку обеих частей, после чего производим их слияние. Реализация этого алгоритма представлена в программе 8.3; пример ил­люстрируется на рис. 8.2. Этот алгоритм является одним из широко известных примеров использования принципа "разделяй и вла­ствуй" при разработке эффективных алгоритмов.

Рисунок 8.2 Пример нисходящей сортировки слиянием

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

Сортировка слиянием играет важную роль благо­даря простоте и оптимальности заложенного в нее метода (время ее выполнения пропорционально.Vlog/V), который допускает возмож­ность реализации, обладающей устойчивостью. Эти утверждения сравнительно не­трудно доказать.

Можно воспользоваться древовидной структурой, чтобы получить наглядное представление о структуре рекурсивных вызовов рекурсивного алгоритма, что поможет понять все варианты рассматриваемого алгоритма и провести его анализ. Что касается сортиров­ки слиянием, то структура рекурсивных вызовов целиком зависит от размеров вво­да. Для любого заданного N мы строим дерево, получившее название "дерево разде­ляй и властвуй" описывает размер подфайлов, подвергаемых обработке в процессе выполнения программы 8.3

Программа 8.3. Нисходящая сортировка слиян ием

Эта базовая реализация сортировки слиянием является примером рекурсивной про­граммы, прототипом которой служит принцип "разделяй и властвуй". Она выполняет сортировку массива а,..., а[г] путем деления его на две части а,...,а[m] и а,...,а(г] с последующей их сортировкой независимо друг от друга (через ре­курсивные вызовы) и слияния полученных упорядоченных подфайлов с тем, чтобы в конечном итоге получить отсортированный исходный файл. Функция может потре­бовать использования вспомогательного файла, достаточно большого, чтобы при­нять копию входного файла, однако эту абстрактную операцию удобно рассматри­вать как обменное слияние.

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

Рисунок 8.3. Деревья,построенный по принципу «разделяй и влавствуй».

Эти диаграммы иллюстрируют размеры подзадач, возникающих в процессе выполнения нисходящей сортировки слиянием. В отличие от деревьев, соответствующих, например, быстрой. сортировке, эти схемы определяются только размерами исходного файла, а не значениями ключей, присутствующих в файле. Верхняя диаграмма показывает, как сортируется файл, состоящий их 32 элементов. Мы (рекурсивно) сортируем два файла по 16 элементов, затем выполняем их слияние. Файлы сортируются по 16 мементов с выполнением (рекурсивной) сортировки файлов по 8 элементов и т.д. Для файлов, размер которых нельзя представить в виде степени 2, схема оказывается несколько более сложной, в чем нетрудно убедиться из нижней диаграммы

Сортировка слиянием требует выполнения примерно NlogN операций срав­нения для сортировки любого файла из N элементов .

Каждое слияние типа (N /2) на (N /2) требует N сравнений (это значение будет для разных файлов отличаться на 1 или на 2, в зависимости от того, как используются служебные метки). Следо­вательно, общее количество сравнений при сортировке в полном объеме мо­жет быть описано стандартным сбалансированным рекуррентным соотношени­ем: Mn = M [ n / 2] + M [ n \ 2] + N, где M1=0. Такое рекуррентное соотношение описывает также сумму меток узлов и длину внешнего пути). Это утверждение нетрудно про­верить, когда N является степенью числа 2 доказать методом индукции для произвольного N.

Сортировка слиянием использует дополнительное пространство, пропорци­ональное N.

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

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

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

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

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

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

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

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

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

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

Сортировка выбором (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