Быстрая сортировка объяснение. Быстрая сортировка
Подробности Категория: Сортировка и поискБыстрая сортировка (англ. quicksort ), часто называемая qsort (по имени в стандартной библиотеке языка Си) - широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
Реализация алгоритма на различных языках программирования:
C
Работает для произвольного массива из n целых чисел.
Int n, a[n]; //n - количество элементов void qs(int* s_arr, int first, int last) { int i = first, j = last, x = s_arr[(first + last) / 2]; do { while (s_arr[i] < x) i++; while (s_arr[j] > x) j--; if(i <= j) { if (s_arr[i] > s_arr[j]) swap(&s_arr[i], &s_arr[j]); i++; j--; } } while (i <= j); if (i < last) qs(s_arr, i, last); if (first < j) qs(s_arr, first, j); }
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
Java/C#
Int partition (int array, int start, int end) { int marker = start; for (int i = start; i <= end; i++) { if (array[i] <= array) { int temp = array; // swap array = array[i]; array[i] = temp; marker += 1; } } return marker - 1; } void quicksort (int array, int start, int end) { if (start >= end) { return; } int pivot = partition (array, start, end); quicksort (array, start, pivot-1); quicksort (array, pivot+1, end); }
C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable
Int partition
C# с использованием лямбда-выражений
Using System;
using System.Collections.Generic;
using System.Linq;
static public class Qsort
{
public static IEnumerable
C++
Быстрая сортировка на основе библиотеки STL.
#include
Java
import java.util.Comparator; import java.util.Random; public class Quicksort { public static final Random RND = new Random(); private void swap(Object array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private int partition(Object array, int begin, int end, Comparator cmp) { int index = begin + RND.nextInt(end - begin + 1); Object pivot = array; swap(array, index, end); for (int i = index = begin; i < end; ++ i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private void qsort(Object array, int begin, int end, Comparator cmp) { if (end > begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public void sort(Object array, Comparator cmp) { qsort(array, 0, array.length - 1, cmp); }Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)
<=N;i=i+1) { A[i]=N-i; System.out.print(A[i]+" "); } System.out.println("\nBefore qSort\n"); // перемешивание массива Random r = new Random(); //инициализация от таймера int yd,xs; for (int i=0;i<=N;i=i+1) { yd=A[i]; xs=r.nextInt(N+1); A[i]=A; A=yd; } for (int i=0;i<=N;i=i+1) System.out.print(A[i]+" "); System.out.println("\nAfter randomization\n"); long start, end; int low=0; int high=N; start=System.nanoTime(); // получить начальное время qSort(A,low,high); end=System.nanoTime(); // получить конечное время for (int i=0;i<=N;i++) System.out.print(A[i]+" "); System.out.println("\nAfter qSort"); System.out.println("\nTime of running: "+(end-start)+"nanosec"); } //описание функции qSort 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); //рекурсивные вызовы функции qSort if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); } }
JavaScript
Import java.util.Random; public class QuickSort { public static void main(String args) { int N=10; int A; A = new int; // заполнение массива for (int i=0;i<=N;i=i+1) { A[i]=N-i; System.out.print(A[i]+" "); } System.out.println("\nBefore qSort\n"); // перемешивание массива Random r = new Random(); //инициализация от таймера int yd,xs; for (int i=0;i<=N;i=i+1) { yd=A[i]; xs=r.nextInt(N+1); A[i]=A; A=yd; } for (int i=0;i<=N;i=i+1) System.out.print(A[i]+" "); System.out.println("\nAfter randomization\n"); long start, end; int low=0; int high=N; start=System.nanoTime(); // получить начальное время qSort(A,low,high); end=System.nanoTime(); // получить конечное время for (int i=0;i<=N;i++) System.out.print(A[i]+" "); System.out.println("\nAfter qSort"); System.out.println("\nTime of running: "+(end-start)+"nanosec"); } //описание функции qSort 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); //рекурсивные вызовы функции qSort if(low < j) qSort(A, low, j); if(i < high) qSort(A, i, high); } }
Python
С использованием генераторов:
Def qsort(L):
if L: return qsort( if x
Математическая версия:
Def qsort(L): if L: return qsort(filter(lambda x: x < L, L)) + L + qsort(filter(lambda x: x >= L, L)) return
Joy
DEFINE sort == split] [ dip cons concat] binrec .PHP
function qsort($s) { for($i=0, $x=$y=array(); $iQsort = qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Математическая версия - с использованием генераторов:
Qsort = qsort (x:xs) = qsort ++ [x] ++ qsort
Common Lisp
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp"а.
(defun quickSort (array l r) (let ((i l) (j r) (p (svref array (round (+ l r) 2)))) (while (<= i j) (while (< (svref array i) p) (incf i)) (while (> (svref array j) p) (decf j)) (when (<= i j) (rotatef (svref array i) (svref array j)) (incf i) (decf j))) (if (>= (- j l) 1) (quickSort array l j)) (if (>= (- r i) 1) (quickSort array i r))) array)
Pascal
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его - зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве - он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» - необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии - будут обменены местами. Что займёт больше времени - проверки или лишние перестановки, - зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
Const max=20; { можно и больше... }
type
list = array of integer;
procedure quicksort(var a: list; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=a; { x:= a[(r+l) div 2]; - для выбора среднего элемента }
repeat
while a[i] Устойчивый вариант (требует дополнительно O(n)памяти) Const max=20; { можно и больше… }
type
list = array of integer;
procedure quicksort(var a: list; Lo,Hi: integer);
procedure sort(l,r: integer);
var
i,j,x,xval,y: integer;
begin
i:=l; j:=r; x:=random(r-l+1)+l; xval:=a[x]; xvaln:=num[x]{ x:=(r+l) div 2; - для выбора среднего элемента }
repeat
while (a[i] Быстрая сортировка, нерекурсивный вариант
Нерекурсивная реализация быстрой сортировки через стек. Функции compare и change реализуются в зависимости от типа данных. Procedure quickSort(var X: itemArray; n: integer);
type
p_node = ^node;
node = record
node: integer;
next: p_node
end;
var
l,r,i,j: integer;
stack: p_node;
temp: item;
procedure push(i: integer);
var
temp: p_node;
begin
new(temp);
temp^.node:=i;
temp^.next:=stack;
stack:=temp
end;
function pop: integer;
var
temp: p_node;
begin
if stack=nil then
pop:=0
else
begin
temp:=stack;
pop:=stack^.node;
stack:=stack^.next;
dispose(temp)
end
end;
begin
stack:=nil;
push(n-1);
push(0);
repeat
l:=pop;
r:=pop;
if r-l=1 then
begin
if compare(X[l],X[r]) then
change(X[l],X[r])
end
else
begin
temp:=x[(l+r) div 2]; {random(r-l+1)+l}
i:=l;
j:=r;
repeat
while compare(temp,X[i]) do i:=i+1;
while compare(X[j],temp) do j:=j-1;
if i<=j then
begin
change(X[i],X[j]);
i:=i+1;
j:=j-1
end;
until i>j;
if l This example demonstrates the use of an arbitrary predicate in a functional language. Fun quicksort lt lst =
let val rec sort =
fn =>
| (x::xs) =>
let
val (left,right) = List.partition (fn y => lt (y, x)) xs
in sort left @ x:: sort right
end
in sort lst
end
@out=(5,2,7,9,2,5,67,1,5,7,-8,5,0);
sub sortQ{
my($s, $e) = @_;
my $m = $s - 1;
for($s..$e - 1){
if($out[$_] lt $out[$e]){
++$m;
($out[$m], $out[$_]) = ($out[$_], $out[$m]);
}
}
++$m;
($out[$m], $out[$e]) = ($out[$e], $out[$m]);
sortQ($s, $m-1) if $s < $m-1;
sortQ($m+1, $e) if $m+1 < $e;
}
sortQ(0, $#out); Let rec quicksort = function
->
| h::t -> quicksort ([ for x in t when x<=h -> x])
@ [h] @ quicksort ([ for x in t when x>h -> x]);; Let rec qsort l=match l with
->
|a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b));; Qsort() -> ;
qsort() -> qsort() ++ [H] ++ qsort(). Array qsort(array)(array _a)
{
alias typeof(array.init) _type;
array filter(bool delegate(_type) dg, array a){
array buffer = null;
foreach(value; a) {
if(dg(value)){
buffer ~= value;
}
}
return buffer;
}
if(_a.length <= 1) {
return _a;
}
else {
return qsort(filter((_type e){ return _a >= e; }, _a)) ~ _a ~
qsort(filter((_type e){ return _a < e; }, _a));
}
} Более короткий вариант с использованием стандартной библиотеки Phobos: Import std.algorithm;
T _qsort3(T)(T a) {
if(a.length <= 1)
return a;
else
return _qsort3(a.filter!(e => a >= e).array) ~ a ~
_qsort3(a.filter!(e => a < e).array);
} Def qsort](list: List[A]): List[A] = list match
{
case head::tail =>
{
qsort(tail filter(head>=)) ::: head:: qsort(tail filter(head<))
}
case _ => list;
} Еще вариант: Def sort(xs: Array): Array = {
if (xs.length <= 1) xs
else {
val pivot = xs(xs.length / 2)
Array.concat(sort(xs filter (pivot >)), xs filter (pivot ==), sort(xs filter (pivot <)))
}
} Ленивая реализация: (defn qsort []
(letfn [(f [g] (qsort (filter #(g % x) xs)))]
(when x (lazy-cat (f <) [x] (f >=))))) (define filter
{(A --> boolean) --> (list A) --> (list A)}
_ ->
T? -> (append [A] (filter T? B)) where (T? A)
T? [_|B] -> (filter T? B))
(define q-sort
{(list number) --> (list number)}
->
-> (append (q-sort (filter (> A) ))
[A]
(q-sort (filter (< A) )))) Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort"ом Sub Swap(ByRef Val1, ByRef Val2)
Dim Proc
Proc = Val1
Val1 = Val2
Val2 = Proc
End Sub
Function partition(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer, ByRef pivot As Integer)
Dim i
Dim piv
Dim store
piv = a(pivot)
Swap(a(right - 1), a(pivot))
store = left
For i = left To right - 2
If a(i) <= piv Then
Swap(a(store), a(i))
store = store + 1
End If
Next
Swap(a(right - 1), a(store))
Return store
End Function
Function getpivot(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Return New System.Random().Next(left, right - 1)
End Function
Sub quicksort(ByRef a() As Integer, ByVal left As Integer, ByVal right As Integer)
Dim pivot As Integer
If right - left > 1 Then
pivot = getpivot(a, left, right)
pivot = partition(a, left, right, pivot)
quicksort(a, left, pivot)
quicksort(a, pivot + 1, right)
End If
End Sub
Sub qSort(ByVal a() As Integer)
Dim i
Dim ii
For i = 0 To a.Length() - 1
ii = New System.Random().Next(0, a.Length() - 1)
If i <> ii Then
Swap(a(i), a(ii))
End If
Next
quicksort(a, 0, a.Length())
End Sub Вызов функции: QSort(имя сортируемого массива)
Function
quicksort (&
$array
,
$l
=
0
,
$r
=
0
)
{
if($r === 0) $r = count($array)-1;
$i = $l;
$j = $r;
$x = $array[($l + $r) / 2];
do {
while ($array[$i] < $x) $i++;
while ($array[$j] > $x) $j--;
if ($i <= $j) {
if ($array[$i] > $array[$j])
list($array[$i], $array[$j]) = array($array[$j], $array[$i]);
$i++;
$j--;
}
} while ($i <= $j);
if ($i < $r) quicksort ($array, $i, $r);
if ($j > $l) quicksort ($array, $l, $j);
} Здесь приведен алгоритм сортировки на примере объекта типа «СписокЗначений», но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций «СравнитьЗначения», «ПолучитьЗначение», «УстановитьЗначение». Функция СравнитьЗначения(Знач1, Знач2)
Если Знач1>Знач2 Тогда
Возврат 1;
КонецЕсли;
Если Знач1<Знач2 Тогда
Возврат -1;
КонецЕсли;
Возврат 0;
КонецФункции
Функция ПолучитьЗначение(Список, Номер)
Возврат Список.Получить(Номер-1).Значение;
КонецФункции
Процедура УстановитьЗначение(Список, Номер, Значение)
Список[Номер-1].Значение = Значение;
КонецПроцедуры
Процедура qs_0(s_arr, first, last)
i = first;
j = last;
x = ПолучитьЗначение(s_arr, Окр((first + last) / 2, 0));
Пока i <= j Цикл
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, i), x)=-1 Цикл
i=i+1;
КонецЦикла;
Пока СравнитьЗначения(ПолучитьЗначение(s_arr, j), x)=1 Цикл
j=j-1;
КонецЦикла;
Если i <= j Тогда
Если i < j Тогда
к=ПолучитьЗначение(s_arr, i);
УстановитьЗначение(s_arr, i, ПолучитьЗначение(s_arr, j));
УстановитьЗначение(s_arr, j, к);
КонецЕсли;
i=i+1;
j=j-1;
КонецЕсли;
КонецЦикла;
Если i < last Тогда
qs_0(s_arr, i, last);
КонецЕсли;
Если first < j Тогда
qs_0(s_arr, first,j);
КонецЕсли;
КонецПроцедуры
Процедура Сортировать(Список, Размер="", Первый="", Последний="")
Если Не ЗначениеЗаполнено(Первый) Тогда
Первый=1;
КонецЕсли;
Если НЕ ЗначениеЗаполнено(Последний) Тогда
Последний=Размер;
КонецЕсли;
qs_0(Список, Первый, Последний);
КонецПроцедуры DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP
J=HIGH
X=Y[(LOW+HIGH)/2]
DO
WHILE Y[I] Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
При написании статьи были использованы открытые источники сети интернет:
А
лгоритм быстрой сортировки был придуман Тони Хоаром, в среднем он выполняется за 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);
} До текущего момента единственной публикацией о сортировке в моем блоге была . Пора это исправлять! Строить грандиозных планов о покорении всех видов сортировки я не стану, а начну с одной из самых популярных — быстрая сортировка. Я буду далеко не первым и не последним, кто скажет, что «быстрая» она только в названии и сейчас существует куча аналогов, и вообще для каждого типа данных нужна своя сортировка. Да, это все правда, но эта правда не отменяет простого факта, что собственноручная реализация быстрой сортировки оттачивает навыки программирования в общем
, и она всегда будет в университетских курсах, я в этом уверен. Из этих же соображений был выбран язык программирования для реализации, ибо тут же можно попрактиковаться в использовании указателей в C/C++. Предлагаю перейти к делу и для начала кратко рассмотреть суть алгоритма. Схему алгоритма можно описать таким образом: Заходы в рекурсию прекратятся в тот момент, когда размер обоих частей будет меньше или равен единице. Иллюстрацию одного шага алгоритма я позаимствовал , больно уж она наглядная. На вход функция принимает сам массив(указатель на начало) и его размер. Void qsortRecursive(int *mas, int size) {
//Указатели в начало и в конец массива
int i = 0;
int j = size - 1;
//Центральный элемент массива
int mid = mas;
//Делим массив
do {
//Пробегаем элементы, ищем те, которые нужно перекинуть в другую часть
//В левой части массива пропускаем(оставляем на месте) элементы, которые меньше центрального
while(mas[i] < mid) {
i++;
}
//В правой части пропускаем элементы, которые больше центрального
while(mas[j] > mid) {
j--;
}
//Меняем элементы местами
if (i <= j) {
int tmp = mas[i];
mas[i] = mas[j];
mas[j] = tmp;
i++;
j--;
}
} while (i <= j);
//Рекурсивные вызовы, если осталось, что сортировать
if(j > 0) {
//"Левый кусок"
qsortRecursive(mas, j + 1);
}
if (i < size) {
//"Првый кусок"
qsortRecursive(&mas[i], size - i);
}
}
Это задание одновременно помогает понять, как работает рекурсия и учит прослеживать изменение данных во время исполнения алгоритма. Рекомендуется «дойти» и написать это самостоятельно, но все же вот моя реализация, мне и самому она может пригодиться. На этом у меня все, спасибо за внимание! Алгоритмы и структуры данных для начинающих: сортировка Никита Прияцелюк В этой части мы посмотрим на пять основных алгоритмов сортировки данных в массиве. Начнем с самого простого - сортировки пузырьком - и закончим «быстрой сортировкой» (quicksort)
. Для каждого алгоритма, кроме объяснения его работы, мы также укажем его сложность по памяти и времени в наихудшем, наилучшем и среднем случае. Также смотрите другие материалы этой серии: , и . Для упрощения кода и улучшения читаемости мы введем метод Swap , который будет менять местами значения в массиве по индексу. Void Swap(T items, int left, int right)
{
if (left != right)
{
T temp = items;
items = items;
items = temp;
}
}
Сортировка пузырьком - это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива. Например, у нас есть массив целых чисел: При первом проходе по массиву мы сравниваем значения 3 и 7. Поскольку 7 больше 3, мы оставляем их как есть. После чего сравниваем 7 и 4. 4 меньше 7, поэтому мы меняем их местами, перемещая семерку на одну позицию ближе к концу массива. Теперь он выглядит так: Этот процесс повторяется до тех пор, пока семерка не дойдет почти до конца массива. В конце она сравнивается с элементом 8, которое больше, а значит, обмена не происходит. После того, как мы обошли массив один раз, он выглядит так: Поскольку был совершен по крайней мере один обмен значений, нам нужно пройти по массиву еще раз. В результате этого прохода мы перемещаем на место число 6. И снова был произведен как минимум один обмен, а значит, проходим по массиву еще раз. При следующем проходе обмена не производится, что означает, что наш массив отсортирован, и алгоритм закончил свою работу. Public void Sort(T items)
{
bool swapped;
do
{
swapped = false;
for (int i = 1; i < items.Length; i++) {
if (items.CompareTo(items[i]) > 0)
{
Swap(items, i - 1, i);
swapped = true;
}
}
} while (swapped != false);
}
Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее - нет. Важный момент: сортировка вставками обрабатывает элементы массива по порядку. Поскольку алгоритм проходит по элементам слева направо, мы знаем, что все, что слева от текущего индекса - уже отсортировано. На этом рисунке показано, как увеличивается отсортированная часть массива с каждым проходом: Постепенно отсортированная часть массива растет, и, в конце концов, массив окажется упорядоченным. Давайте взглянем на конкретный пример. Вот наш неотсортированный массив, который мы будем использовать: Алгоритм начинает работу с индекса 0 и значения 3. Поскольку это первый индекс, массив до него включительно считается отсортированным. На этом этапе элементы с индексами 0..1 отсортированы, а про элементы с индексами 2..n ничего не известно. Следующим проверяется значение 4. Так как оно меньше семи, мы должны перенести его на правильную позицию в отсортированную часть массива. Остается вопрос: как ее определить? Это осуществляется методом FindInsertionIndex . Он сравнивает переданное ему значение (4) с каждым значением в отсортированной части, пока не найдет место для вставки. Итак, мы нашли индекс 1 (между значениями 3 и 7). Метод Insert осуществляет вставку, удаляя вставляемое значение из массива и сдвигая все значения, начиная с индекса для вставки, вправо. Теперь массив выглядит так: Теперь часть массива, начиная от нулевого элемента и заканчивая элементом с индексом 2, отсортирована. Следующий проход начинается с индекса 3 и значения 4. По мере работы алгоритма мы продолжаем делать такие вставки. Когда больше нет возможностей для вставок, массив считается полностью отсортированным, и работа алгоритма закончена. Public void Sort(T items)
{
int sortedRangeEndIndex = 1;
while (sortedRangeEndIndex < items.Length)
{
if (items.CompareTo(items) < 0)
{
int insertIndex = FindInsertionIndex(items, items);
Insert(items, insertIndex, sortedRangeEndIndex);
}
sortedRangeEndIndex++;
}
}
private int FindInsertionIndex(T items, T valueToInsert)
{
for (int index = 0; index < items.Length; index++) {
if (items.CompareTo(valueToInsert) > 0)
{
return index;
}
}
throw new InvalidOperationException("The insertion index was not found");
}
private void Insert(T itemArray, int indexInsertingAt, int indexInsertingFrom)
{
// itemArray = 0 1 2 4 5 6 3 7
// insertingAt = 3
// insertingFrom = 6
//
// Действия:
// 1: Сохранить текущий индекс в temp
// 2: Заменить indexInsertingAt на indexInsertingFrom
// 3: Заменить indexInsertingAt на indexInsertingFrom в позиции +1
// Сдвинуть элементы влево на один.
// 4: Записать temp на позицию в массиве + 1.
// Шаг 1.
T temp = itemArray;
// Шаг 2.
itemArray = itemArray;
// Шаг 3.
for (int current = indexInsertingFrom; current > indexInsertingAt; current--)
{
itemArray = itemArray;
}
// Шаг 4.
itemArray = temp;
}
Сортировка выбором - это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце. Давайте посмотрим на работу сортировки выбором на нашем неотсортированном массиве. При первом проходе алгоритм с помощью метода FindIndexOfSmallestFromIndex пытается найти наименьшее значение в массиве и переместить его в начало. Имея такой маленький массив, мы сразу можем сказать, что наименьшее значение - 3, и оно уже находится на правильной позиции. На этом этапе мы знаем, что на первой позиции в массиве (индекс 0) находится самое маленькое значение, следовательно, начало массива уже отсортировано. Поэтому мы начинаем второй проход - на этот раз по индексам от 1 до n – 1. На втором проходе мы определяем, что наименьшее значение - 4. Мы меняем его местами со вторым элементом, семеркой, после чего 4 встает на свою правильную позицию. Теперь неотсортированная часть массива начинается с индекса 2. Она растет на один элемент при каждом проходе алгоритма. Если на каком-либо проходе мы не сделали ни одного обмена, это означает, что массив отсортирован. После еще двух проходов алгоритм завершает свою работу: Public void Sort(T items)
{
int sortedRangeEnd = 0;
while (sortedRangeEnd < items.Length)
{
int nextIndex = FindIndexOfSmallestFromIndex(items, sortedRangeEnd);
Swap(items, sortedRangeEnd, nextIndex);
sortedRangeEnd++;
}
}
private int FindIndexOfSmallestFromIndex(T items, int sortedRangeEnd)
{
T currentSmallest = items;
int currentSmallestIndex = sortedRangeEnd;
for (int i = sortedRangeEnd + 1; i < items.Length; i++)
{
if (currentSmallest.CompareTo(items[i]) > 0)
{
currentSmallest = items[i];
currentSmallestIndex = i;
}
}
return currentSmallestIndex;
}
До сих пор мы рассматривали линейные алгоритмы. Они используют мало дополнительной памяти, но имеют квадратичную сложность. На примере сортировки слиянием мы посмотрим на алгоритм типа «разделяй и властвуй» (divide and conquer)
. Алгоритмы этого типа работают, разделяя крупную задачу на более мелкие, решаемые проще. Мы пользуемся ими каждый день. К примеру, поиск в телефонной книге - один из примеров такого алгоритма. Если вы хотите найти человека по фамилии Петров, вы не станете искать, начиная с буквы А и переворачивая по одной странице. Вы, скорее всего, откроете книгу где-то посередине. Если попадете на букву Т, перелистнете несколько страниц назад, возможно, слишком много - до буквы О. Тогда вы пойдете вперед. Таким образом, перелистывая туда и обратно все меньшее количество страниц, вы, в конце концов, найдете нужную. Насколько эффективны эти алгоритмы? Предположим, что в телефонной книге 1000 страниц. Если вы открываете ее на середине, вы отбрасываете 500 страниц, в которых нет искомого человека. Если вы не попали на нужную страницу, вы выбираете правую или левую сторону и снова оставляете половину доступных вариантов. Теперь вам надо просмотреть 250 страниц. Таким образом мы делим нашу задачу пополам снова и снова и можем найти человека в телефонной книге всего за 10 просмотров. Это составляет 1% от всего количества страниц, которые нам пришлось бы просмотреть при линейном поиске. При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке. Давайте посмотрим на такой массив: Разделим его пополам: И будем делить каждую часть пополам, пока не останутся части с одним элементом: Теперь, когда мы разделили массив на максимально короткие участки, мы сливаем их в правильном порядке. Сначала мы получаем группы по два отсортированных элемента, потом «собираем» их в группы по четыре элемента и в конце собираем все вместе в отсортированный массив. Для работы алгоритма мы должны реализовать следующие операции: Стоит отметить, что в отличие от линейных алгоритмов сортировки, сортировка слиянием будет делить и склеивать массив вне зависимости от того, был он отсортирован изначально или нет. Поэтому, несмотря на то, что в худшем случае он отработает быстрее, чем линейный, в лучшем случае его производительность будет ниже, чем у линейного. Поэтому сортировка слиянием - не самое лучшее решение, когда надо отсортировать частично упорядченный массив. Public void Sort(T items)
{
if (items.Length <= 1)
{
return;
}
int leftSize = items.Length / 2;
int rightSize = items.Length - leftSize;
T left = new T;
T right = new T;
Array.Copy(items, 0, left, 0, leftSize);
Array.Copy(items, leftSize, right, 0, rightSize);
Sort(left);
Sort(right);
Merge(items, left, right);
}
private void Merge(T items, T left, T right)
{
int leftIndex = 0;
int rightIndex = 0;
int targetIndex = 0;
int remaining = left.Length + right.Length;
while(remaining > 0)
{
if (leftIndex >= left.Length)
{
items = right;
}
else if (rightIndex >= right.Length)
{
items = left;
}
else if (left.CompareTo(right) < 0)
{
items = left;
}
else
{
items = right;
}
targetIndex++;
remaining--;
}
}
Быстрая сортировка - это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги: Давайте посмотрим на работу алгоритма на следующем массиве: Сначала мы случайным образом выбираем ключевой элемент: Int pivotIndex = _pivotRng.Next(left, right);
Теперь, когда мы знаем ключевой индекс (4), мы берем значение, находящееся по этому индексу (6), и переносим значения в массиве так, чтобы все числа больше или равные ключевому были в правой части, а все числа меньше ключевого - в левой. Обратите внимание, что в процессе переноса значений индекс ключевого элемента может измениться (мы увидим это вскоре). Перемещение значений осуществляется методом partition . На этом этапе мы знаем, что значение 6 находится на правильной позиции. Теперь мы повторяем этот процесс для правой и левой частей массива. Мы рекурсивно вызываем метод quicksort на каждой из частей. Ключевым элементом в левой части становится пятерка. При перемещении значений она изменит свой индекс. Главное - помнить, что нам важно именно ключевое значение, а не его индекс. Снова применяем быструю сортировку: И еще раз: У нас осталось одно неотсортированное значение, а, поскольку мы знаем, что все остальное уже отсортировано, алгоритм завершает работу. Random _pivotRng = new Random();
public void Sort(T items)
{
quicksort(items, 0, items.Length - 1);
}
private void quicksort(T items, int left, int right)
{
if (left < right)
{
int pivotIndex = _pivotRng.Next(left, right);
int newPivot = partition(items, left, right, pivotIndex);
quicksort(items, left, newPivot - 1);
quicksort(items, newPivot + 1, right);
}
}
private int partition(T items, int left, int right, int pivotIndex)
{
T pivotValue = items;
Swap(items, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++)
{
if (items[i].CompareTo(pivotValue) < 0)
{
Swap(items, i, storeIndex);
storeIndex += 1;
}
}
Swap(items, storeIndex, right);
return storeIndex;
}
На этом мы заканчиваем наш цикл статей по алгоритмам и структурам данных для начинающих. За это время мы рассмотрели связные списки, динамические массивы, двоичное дерево поиска и множества с примерами кода на C#. Примечание: на практике обычно разделяют сортируемое множество не на три, а на две части: например, «меньшие опорного» и «равные и большие». Такой подход в общем случае оказывается эффективнее, так как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов. Быстрая сортировка использует стратегию «разделяй и властвуй ». Шаги алгоритма таковы: Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута всегда и обработка гарантированно завершится. Интересно, что Хоар разработал этот метод применительно к машинному переводу : дело в том, что в то время словарь хранился на магнитной ленте , и если упорядочить все слова в тексте, их переводы можно получить за один прогон ленты. Алгоритм был придуман Хоаром во время его пребывания в Советском Союзе , где он обучался в Московском университете компьютерному переводу и занимался разработкой русско-английского разговорника (говорят, этот алгоритм был подслушан им у русских студентов). //алгоритм на языке 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]
//алгоритм на языке 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 является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка » и «Шейкерная сортировка »), известного, в том числе, своей низкой эффективностью. Принципиальное отличие состоит в том, что после каждого прохода элементы делятся на две независимые группы. Любопытный факт: улучшение самого неэффективного прямого метода сортировки дало в результате эффективный улучшенный метод. Достоинства: Недостатки:Prolog
split(H, , , Z) :-
order(A, H), split(H, X, Y, Z).
split(H, , Y, ) :-
not(order(A, H)), split(H, X, Y, Z).
split(_, , , ).
quicksort(, X, X).
quicksort(, S, X) :-
split(H, T, A, B),
quicksort(A, S, ),
quicksort(B, Y, X).
Ruby
def sort(array)
return if array.empty?
left, right = array.partition { |y| y <= array.first }
sort(left) + [ array.first ] + sort(right)
end
SML
JavaScript
function QuickSort(A, p, r)
{
if(pPerl
F#
OCaml
Erlang
D
Scala
Clojure
Shen/Qi II
VB.NET
PHP
Встроенный язык 1С 8.*
Turbo Basic 1.1
Рекурсивное решение
Итеративное решение
Как работает быстрая сортировка
Наглядно это можно показать таким образом:
|———————|—————————|———————|
| mas[i] <= mid | mid = mas | mas[i] >= mid |
|———————-|—————————|———————|Рекурсивная реализация быстрой сортировки
Заключение
Метод Swap
Пузырьковая сортировка
Сортировка вставками
Сортировка выбором
Сортировка слиянием
Разделяй и властвуй
Сортировка слиянием
Быстрая сортировка
Заключение
Краткое описание алгоритма
Алгоритм
Оценка эффективности
На практике (в случае, когда обмены являются более затратной операцией, чем сравнения) быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(n
lg n
), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре. 2C N/2 покрывает расходы по сортировке двух полученных подмассивов; N - это стоимость обработки каждого элемента, используя один или другой указатель. Известно также, что примерное значение этого выражения равно C N = N lg N.
Худший случай даёт O(n
²) обменов. Но количество обменов и, соответственно, время работы - это не самый большой его недостаток. Хуже то, что в таком случае глубина рекурсии при выполнении алгоритма достигнет n, что будет означать n-кратное сохранение адреса возврата и локальных переменных процедуры разделения массивов. Для больших значений n худший случай может привести к исчерпанию памяти во время работы алгоритма. Впрочем, на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.Улучшения
Достоинства и недостатки
Примечания
Литература
