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

Материал из Викиучебника
Перейти к: навигация, поиск
Статья «Быстрая сортировка» в Википедии


Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка \Theta(n^2).

В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки \Theta(n \log n) в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за \Theta(n^2) времени на некоторых специально-сконструированных массивах.

Содержание

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[] array, int start, int end) {
       int marker = start;
 
       for ( int i = start; i <= end; i++ ) {
           if ( array[i] <= array[end] ) {
               int temp = array[marker];
 
               array[marker] = array[i];
               array[i] = temp;
               marker += 1;
           }
       }
       return marker - 1;
   }
 
   void quicksort (int[] array, int start, int end) {
       int pivot;
 
       if ( start >= end ) {
           return;
       }
 
       pivot = partition (array, start, end);
       quicksort (array, start, pivot-1);
       quicksort (array, pivot+1, end);
   }

C# с обобщенными типами, тип Т должен реализовывать интерфейс IComparable<T>

int partition<T>( T[] m, int a, int b) where T :IComparable<T>
{
    int i = a;
    for (int j = a; j <= b; j++)         // просматриваем с a по b
    {        
        if (m[j].CompareTo( m[b]) <= 0)  // если элемент m[j] не превосходит m[b],
        {
            T 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<T>( T[] m, int a, int b) where T : IComparable<T>// 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);
}
 
//Пример вызова
//double[] arr = {9,1.5,34.4,234,1,56.5};
//quicksort<double>(arr,0,arr.Length-1);
//

C# с использованием лямбда-выражений

using System;
using System.Collections.Generic;
using System.Linq;
 
static public class Qsort
    {
        public static IEnumerable<T> QuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
        {
            if (!list.Any())
            {
                return Enumerable.Empty<T>();
            }
            var pivot = list.First();
            var smaller = list.Skip(1).Where(item => item.CompareTo(pivot) <= 0).QuickSort();
            var larger = list.Skip(1).Where(item => item.CompareTo(pivot) > 0).QuickSort();
 
            return smaller.Concat(new[] { pivot }).Concat(larger);
        }
 
//(тоже самое, но записанное в одну строку, без объявления переменных)
 
        public static IEnumerable<T> shortQuickSort<T>(this IEnumerable<T> list) where T : IComparable<T>
        {
            return !list.Any() ? Enumerable.Empty<T>() : list.Skip(1).Where(
                item => item.CompareTo(list.First()) <= 0).shortQuickSort().Concat(new[] { list.First() })
                    .Concat(list.Skip(1).Where(item => item.CompareTo(list.First()) > 0).shortQuickSort());
        }       
    }


Java, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером

import java.util.Random;
import java.lang.*;
 
public class QuickSort {
    public static void main(String[] args) {
       int N=10;
       int A[];
       A = new int[N+1];
       // заполнение массива
       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[xs];
          A[xs]=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 [править]

/*
 * Алгоритм быстрой сортировки
 *
 * @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 + c + 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 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]])
    return []


Haskell [править]

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

Математическая версия — с использованием генераторов:

  qsort [] = []
  qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

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 [править]

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

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

Erlang [править]

qsort([]) -> [];
qsort([H|T]) -> qsort([X || X <- T, X < H]) ++ [H] ++ qsort([X || X <- T, X >= H])].

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;
  }

Clojure [править]

Ленивая реализация:

  (defn qsort [[x & xs]]
    (letfn [(f [g] (qsort (filter #(g % x) xs)))]
      (when x (lazy-cat (f <) [x] (f >=)))))

Shen/Qi II [править]

(define filter
  {(A --> boolean) --> (list A) --> (list A)}
  _   []      -> []
  T?  [A | B]  -> (append [A] (filter T? B)) where (T? A)
  T?  [_|B]    -> (filter T? B)
)
 
(define q-sort
  {(list number) --> (list number)}
  [] -> []
  [A | B] -> (append (q-sort (filter (> A) [A|B]))
                     [A]
                     (q-sort (filter (< A) [A|B]))))

VB.NET [править]

Судя по тестам, сортировка пузырьком 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(имя сортируемого массива)

PHP [править]

function quicksort (&$array, $l, $r) {
 
    function swap (&$x, &$y) {
        list($x, $y) = array($y, $x);
    }
 
    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);
}

Встроенный язык 1С [править]

Здесь приведен алгоритм сортировки на примере объекта типа «СписокЗначений», но его можно модифицировать для работы с любым объектом, для этого нужно изменить соответствующим образом код функций «СравнитьЗначения», «ПолучитьЗначение», «УстановитьЗначение».

Функция СравнитьЗначения(Знач1, Знач2)
    Если Знач1>Знач2 Тогда
        Возврат 1;
    КонецЕсли;
    Если Знач1<Знач2 Тогда
        Возврат -1;
    КонецЕсли;
    Возврат 0;
КонецФункции
 
Функция ПолучитьЗначение(Список, Номер)
    стр="";
    Возврат Список.ПолучитьЗначение(Номер, стр);
КонецФункции
 
Процедура УстановитьЗначение(Список, Номер, Значение)
    Список.УстановитьЗначение(Номер, Значение);
КонецПроцедуры
 
Процедура qs_0(s_arr, first, last)
 
    i = first;
    j = last;
    x = ПолучитьЗначение(s_arr, (first + last) / 2);
 
    Пока СравнитьЗначения(ПолучитьЗначение(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 <= 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 Тогда
        Первый=1;
    КонецЕсли;
    Если ПустоеЗначение(Последний)=1 Тогда
        Последний=Размер;
    КонецЕсли;
    qs_0(Список, Первый, Последний);
КонецПроцедуры

Turbo Basic 1.1 [править]

DEF FN QSORT(LOW,HIGH) LOCAL I,J,X,TEMP

  J=HIGH
  X=Y[(LOW+HIGH)/2]
  DO
     WHILE Y[I]<X:I=I+1:WEND
     WHILE Y[J]>X:J=J-1:WEND
     IF I<=J THEN
        TEMP=Y[I]
        Y[I]=Y[J]
        Y[J]=TEMP
        I=I+1
        J=J-1
     END IF
  LOOP WHILE I<=J
  IF LOW<J THEN F=FN QSORT(LOW,J)
  IF I<HIGH THEN F=FN QSORT(I,HIGH)
  FN QSORT=TRUE

END DEF </source> Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y[N1:N2]

LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
Источник — «http://ru.wikibooks.org/w/index.php?title=Примеры_реализации_быстрой_сортировки&oldid=78500»