Реализации алгоритмов/Сортировка/Быстрая: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
→‎C: оформление
Строка 887: Строка 887:
qs_0(Список, Первый, Последний);
qs_0(Список, Первый, Последний);
КонецПроцедуры
КонецПроцедуры
</source></big>
== [[w:Turbo Basic|Turbo Basic 1.1]] ==
<big><source lang="qbasic">
DEF FN QSORT(LOW,HIGH)
LOCAL I,J,X,TEMP
I=LOW
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></big>
Пример вызова функции FN QSORT(LOW,HIGH), входные и выходные данные в массиве DIM Y[N1:N2]
<big><source lang="qbasic">
LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
</source></big>
</source></big>


Версия от 11:04, 24 мая 2012

Логотип Википедии
Логотип Википедии

В Википедии имеется статья по теме «Быстрая сортировка»

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

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

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


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

  #! /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 ));;

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
   I=LOW
   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

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

LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)
Источник — https://ru.wikibooks.org/w/index.php?title=Реализации_алгоритмов/Сортировка/Быстрая&oldid=72567