Быстрая сортировка

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск
Анимированная схема алгоритма

Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Содержание

[править] Краткое описание алгоритма

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

[править] Алгоритм

Быстрая сортировка

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

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

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

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

[править] Оценка эффективности

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

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

[править] Улучшения

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

[править] Достоинства и недостатки

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

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

Недостатки:

  • Сильно деградирует как по скорости (до O(n²)), так и по потреблению памяти, при неудачном выборе опорного элемента, который неизбежно случится при неудачных входных данных.
  • Примитивные реализации легко приводят к ошибке переполнения стека, особенно в средах, где размер стека сильно ограничен (ядра ОС). Развитые же реализации требуют постоянного выделения все новых и новых небольших блоков памяти, что не оптимально.
  • Неустойчив — если требуется устойчивость, приходится расширять ключ.

С учетом склонности qsort к деградации, сортировка Шелла на практике зачастую оказывается более удачным выбором для наборов до ~1000 элементов. Кроме того, сортировка Шелла не требует дополнительной памяти.

Если же производительность важнее, чем экономия памяти, то как правило сортировка слиянием (merge sort), оказывается более удачным выбором, чем qsort, ввиду меньшей склонности к деградации, более оптимального паттерна выделения дополнительной памяти, и точно такой же скорости лучшего случая в O(n * log 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 (i < 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 элементов будет иметь следующий вид.

qs(a,0,n-1);

[править] Java/C#

   int partition (int[] m, int a, int b) 
    {
      int i = a;
      for (int j = a; j <= b; j++)    // просматриваем с a по b
       {
         if (m[j] <= m[b])               // если элемент m[j] не превосходит m[b],
          {
            int t = m[i];                    // меняем местами m[j] и m[a], m[a+1], m[a+2] и так далее...
            m[i] = m[j];                 // то есть переносим элементы меньшие m[b] в начало,
            m[j] = t;                    // а затем и сам m[b] «сверху»
            i++;                         // таким образом последний обмен: m[b] и m[i], после чего i++
          }
       }
      return i-1;                        // в индексе i хранится <новая позиция элемента m[b]> + 1
    }
 
   void quicksort (int[] m, int a, int b) // a - начало подмножества, b - конец
    {                                     // для первого вызова: a = 0, b = <элементов в массиве> - 1
     if (a >= b) return;
     int c = partition (m, a, b);
     quicksort (m, a, c-1);
     quicksort (m, c+1, b);
    }


[править] JavaScript

/*
 * Алгоритм быстрой сортировки
 * 
 * @param data Array
 * @param compare function(a, b) - возвращает 0 если a=b, -1 если a<b и 1 если a>b (необязательная) 
 * @param change function(a, i, j) - меняет местами i-й и j-й элементы массива а (необязательная)
 * 				  
 */
function qsort(data, compare, change) {
	var a = data,
		f_compare = compare,
		f_change  = change;
 
	if (!a instanceof Array) { // Данные не являются массивом
		return undefined;
	};
	if (f_compare == undefined) { // Будем использовать простую функцию (для чисел)
		f_compare = function(a, b) {return ((a == b) ? 0 : ((a > b) ? 1 : -1));};
	};
	if (f_change == undefined) { // Будем использовать простую смены (для чисел) 
		f_change = function(a, i, j) {var c = a[i];a[i] = a[j];a[j] = c;};
	};
 
	var qs = function (l, r)  {
		var i = l, 
			j = r,
			x = a[Math.floor(Math.random()*(r-l+1))+l];
			// x = a[l]; // Если нет желания использовать объект Math  
 
		while(i <= j) {
			while(f_compare(a[i], x) == -1) {i++;}
			while(f_compare(a[j], x) == 1) {j--;}
			if(i <= j) {f_change(a, i++, j--);}
		};
		if(l < j) {qs(l, j);}
		if(i < r) {qs(i, r);}
	};
 
	qs(0, a.length-1);	
};

[править] Ruby

Вариант 1:

class Array 
   def qsort
      return self.dup if size <=1
      l,r = partition   {|x| x <= self.first}
      c,l = l.partition {|x| x == self.first}
      l.qsort + с + r.qsort 
   end
end

Вариант 2:

class Array 
   def partition3
      a = Array.new(3) {|i| []}
      each do |x|
         a[yield(x)].push x
      end
      a
   end
   def qsort
      return self.dup if size <=1
      c,l,r = partition3 {|x| first <=> x}
      l.qsort + c +  r.qsort
   end
end

[править] Python

 def qsort(L):
    if L == []: return []
    return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + qsort([x for x in L[1:] if x>=L[0]])


[править] Haskell

  qsort []     = []
  qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

[править] Pascal

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

Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.

const max=20; { можно и больше... }
type
  list = array[1..max] 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[random(r-l+1)+l]; { x := a[(r+l) div 2]; - для выбора среднего элемента } 
    repeat
      while a[i]<x do i:=i+1; { a[i] > x  - сортировка по убыванию}
      while x<a[j] do j:=j-1; { x > a[j]  - сортировка по убыванию}
      if i<=j then 
      begin
        if a[i] > a[j] then {это условие можно убрать} {a[i] < a[j] при сортировке по убыванию}
        begin
          y:=a[i]; a[i]:=a[j]; a[j]:=y; 
        end; 
        i:=i+1; j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end; {sort}
 
begin {quicksort};
  randomize; {нужно только если используется выборка случайного опорного элемента}
  sort(Lo,Hi)
end; {quicksort}

Устойчивый вариант (требует дополнительно O(n)памяти)

const max=20; { можно и больше... }
type
  list = array[1..max] 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]<xval)or((a[i]=xval)and(num[i]<xvaln)) do i:=i+1; {> - сортировка по убыванию}
      while (xval<a[j])or((a[j]=xval)and(xvaln<num[j])) do j:=j-1; {> - сортировка по убыванию}
      if i<=j then 
      begin
        y:=a[i]; a[i]:=a[j]; a[j]:=y;
        y:=num[i]; num[i]:=num[j]; num[j]:=y;
        i:=i+1; j:=j-1
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r)
  end; {sort}
 
begin {quicksort};
  randomize; {нужно только если используется выборка случайного опорного элемента}
  for i:=1 to n do
    num[i]:=i;
  sort(Lo,Hi)
end; {quicksort}

Быстрая сортировка, нерекурсивный вариант

Нерекурсивная реализация быстрой сортировки через стек. Функции 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<j then
      begin
        push(j);
        push(l)
      end;
      if i<r then
      begin
        push(r);
        push(i)
      end
    end;
  until stack=nil
end;

[править] Prolog

split(H, [A|X], [A|Y], Z) :-
  order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :-
  not(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).

quicksort([], X, X).

quicksort([H|T], S, X) :-
  split(H, T, A, B),
  quicksort(A, S, [H|Y]),
  quicksort(B, Y, X).



[править] Perl

  #! /usr/bin/perl
 
  use strict;
 
  sub qsort {
      my ($q, $s, $e) = @_;
      my $m = $s-1;
 
      for (my $i = $s; $i < $e; $i++) {
          if ($q->[$i] < $q->[$e]) {
              $m++;
              ($q->[$m], $q->[$i]) = ($q->[$i], $q->[$m]);
          }
      }
 
      $m++;
      ($q->[$m], $q->[$e]) = ($q->[$e], $q->[$m]);
      qsort($q, $s, $m-1) if $s < $m-1;
      qsort($q, $m+1, $e) if $m+1 < $e;
  }
 
  my @data = map { int(rand(10)) } (1 .. 30);
 
  print "@data\n";
  qsort(\@data, 0, $#data);
  print "@data\n";

[править] F#

  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]);;

[править] OCaml

 let rec qsort l=match l with 
                    []->[]
                   |a::b-> (qsort (List.filter ((>=) a) b) lt) @  [a]  @  (qsort (List.filter ((<) a) b ));;


[править] D

array qsort(array)(array _a)
{
    alias typeof(array.init[0]) _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[0] >= e; }, _a[1 .. $] ) ) ~ _a[0] ~
               qsort( filter((_type e){ return _a[0] <  e; }, _a[1 .. $] ) );
    }
 
}


[править] Scala

  def qsort[A <% Ordered[A]](list: List[A]): List[A] = list match
  {
      case head::tail =>
          {
              qsort( tail filter(head>=) ) ::: head :: qsort( tail filter(head<) )
          }
      case _ => list;  
  }

[править] PHP

function quicksort (&$array, $l, $r) {
 
	function swap (&$x, &$y) {
		$z = $x;
		$x = $y;
		$y = $z;
	}
 
	function qsort ($left, $right) {
		global $array;
		$i = $left;
		$j = $right;
		$x = $array[($left + $right) / 2];
		do {
			while ($array[$i] < $x) $i++;
			while ($array[$j] > $x) $j--;
			if ($i <= $j) {
				if ($array[$i] > $array[$j]) swap ($array[$i], $array[$j]);
				$i++;
				$j--;
				}
		} while ($i <= $j);
    	        if ($i < $right) qsort ($i, $right);
    	        if ($j > $left) qsort ($left, $j);
	}
 
	qsort ($l, $r);
}

[править] Литература

  • Ананий В. Левитин Глава 4. Метод декомпозиции: Быстрая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 174-179. — ISBN 0-201-74395-7
  • Томас Х. Кормен и др. Глава 7. Быстрая сортировка // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
Источник — «http://ru.wikipedia.org/wiki/%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0»