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

Материал из Викиучебника
Перейти к: навигация, поиск


Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка \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 (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 элементов будет иметь следующий вид.

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]; // swap
               array[marker] = 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<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());
        }
    }

C++[править]

Быстрая сортировка на основе библиотеки STL.

#include <functional>
#include <algorithm>
#include <iterator>
template< typename BidirectionalIterator, typename Compare >
void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
  if( first != last ) {
    BidirectionalIterator left  = first;
    BidirectionalIterator right = last;
    BidirectionalIterator pivot = left++;
    while( left != right ) {
      if( cmp( *left, *pivot ) ) {
         ++left;
      } else {
         while( (left != --right) && cmp( *pivot, *right ) )
           ;
         std::iter_swap( left, right );
      }
    }
    --left;
    std::iter_swap( first, left );
    quick_sort( first, left, cmp );
    quick_sort( right, last, cmp );
  }
}

//для вещественных чисел
int partition (double *a, int p, int r)
 {
   double x = *(a+r);
   int i = p - 1;
   int j;
   double tmp;
   for (j = p; j < r; j++)
   {
     if (*(a+j) <= x)
     {
       i++;
       tmp = *(a+i);
       *(a+i) = *(a+j);
       *(a+j) = tmp;
     }
   }
   tmp = *(a+r);
   *(a+r) = *(a+i+1);
   *(a+i+1) = tmp;
   return i + 1;
 }

void quicksort (double *a, int p, int r)
 {
   int q;
   if (p < r)
   {
     q = partition (a, p, r);
     quicksort (a, p, q-1);
     quicksort (a, q+1, r);
   }
 }
template< typename BidirectionalIterator >
inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
  quick_sort( first, last,
    std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
  );

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[index];
        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, с инициализацией и перемешиванием массива и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива)

import java.util.Random;
 
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[l+r>>1];
            //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);
};

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

Математическая версия:

 def qsort(L):
    if L: return qsort(filter(lambda x: x < L[0], L[1:])) + L[0:1] + qsort(filter(lambda x: x >= L[0], L[1:]))
    return []

Joy[править]

DEFINE sort == [small][]
               [uncons [>] split]
               [[swap] dip cons concat] binrec .

PHP[править]

/*
* Функция, непосредственно производящая сортировку.
* Так как массив передается по ссылке, ничего не возвращает.
*/
 
function custom_sort(&$array, $left, $right) {
 
  //Создаем копии пришедших переменных, с которыми будем манипулировать в дальнейшем.
  $l = $left;
  $r = $right;
 
  //Вычисляем 'центр', на который будем опираться. Берем значение ~центральной ячейки массива.
  $center = $array[(int)($left + $right) / 2];
 
  //Цикл, начинающий саму сортировку
  do {
 
    //Ищем значения больше 'центра'
    while ($array[$r] > $center) { 
      $r--;
    }
 
    //Ищем значения меньше 'центра'
    while ($array[$l] < $center) { 
      $l++;
    }
 
    //После прохода циклов проверяем счетчики циклов
    if ($l <= $r) {
 
      //И если условие true, то меняем ячейки друг с другом.
      list($array[$r], $array[$l]) = array($array[$l], $array[$r]);
 
      //И переводим счетчики на следующий элементы
      $l++;
      $r--;
    }
 
  //Повторяем цикл, если true
  } while ($l <= $r);
 
  if ($r > $left) {
    //Если условие true, совершаем рекурсию
    //Передаем массив, исходное начало и текущий конец
    custom_sort($array, $left, $r); 
  }
 
  if ($l < $right) {
    //Если условие true, совершаем рекурсию
    //Передаем массив, текущие начало и конец
    custom_sort($array, $l, $right);
  }
 
//Сортировка завершена
 
}

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]

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[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,xvaln,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).

Ruby[править]

def sort(array)
  return [] if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end

SML[править]

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

JavaScript[править]

function QuickSort(A, p, r)
{
        if(p<r)
        {
                var q = Partition(A, p, r);
                QuickSort(A, p, q);
                QuickSort(A, q+1, r);
        }
}
function Partition(A, p, r)
{
        var x = A[r];
        var i=p-1;
        for(var j=p; j<=r ;j++ )
        {
                if(A[j] <= x)
                {
                        i++;
                        var temp = A[i];
                        A[i] = A[j];
                        A[j] = temp;
                }
        }
        return i<r ?i : i-1;
}

TCL[править]

 # Функция выбирает подсписок из списка используя условие condition
 proc lfind {data arg condition} {
   set foo [list]
   foreach item $data {
     set $arg $item
     if {[expr $condition]} {lappend foo $item}
   }
   return $foo
 }
 # Сама сотрировка
 proc QSort data {
   set result {}
   if {[llength $data] != 0} {
     set check [lindex $data 0]
     set result [
       concat \
         [QSort [lfind $data argument "\$argument < $check"]] \
         [list $check] \
         [QSort [lfind $data argument "\$argument > $check"]]]
   }
   return $result
 }

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 List.filter(fun z -> z<=h)  t -> x])
              @ [h] @ quicksort ([ for x in List.filter(fun z -> z>h)  t -> x])
 
let list1 = [2; 34; 56; 12; 1; 5; 100; 450; 788 ]
 
let res = quicksort list1

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 .. $] ) );
    }
 
}

Более короткий вариант с использованием стандартной библиотеки Phobos:

import std.algorithm;
 
T _qsort3(T)(T a) {
    if( a.length <= 1 )
        return a;
    else
        return _qsort3( a[1..$].filter!( e => a[0] >= e ).array ) ~ a[0] ~
               _qsort3( a[1..$].filter!( e => a[0] <  e ).array );
}

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

Еще вариант:

def sort(xs: Array[Int]): Array[Int] = {
	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 <)))
	}
}

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=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С 8.*[править]

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

Функция СравнитьЗначения(Знач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(Список, Первый, Последний);
КонецПроцедуры

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

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

LOW=N1
HIGH=N2
F=FN QSORT(LOW,HIGH)


PLSQL[править]

----------------------------------------------------------------------------------
TYPE sort_lst IS TABLE OF INTEGER;
-----------------------------------------------------------------------------------
FUNCTION sort(in_array IN OUT sort_lst, in_low IN INTEGER, in_high IN INTEGER) RETURN sort_lst
  IS
      i INTEGER DEFAULT 1; j INTEGER DEFAULT 1;
      m REAL; wsp REAL;
      l_array sort_lst:=sort_lst();
  BEGIN  
      l_array :=in_array;
 
      i:=in_low; j:=in_high; m:=l_array((i+j)/2); -- Взятие среднего опорного элемента
 
      LOOP
        WHILE (l_array(i)<m) LOOP
              i:=i+1; -- изменить порядок сортировки можно
           END LOOP; 
 
        WHILE (l_array(j)>m) LOOP
             j:=j-1;  -- поменяв >< в этих двух строках
        END LOOP; 
 
        IF i<=j THEN 
            BEGIN
               wsp:=l_array(i); l_array(i):=l_array(j); l_array(j):=wsp;
               I:=I+1; j:=j-1;
            END;
        END IF;
 
        EXIT WHEN i>j; -- пост условие
      END LOOP;
 
      IF in_low<j THEN 
         l_array:=sort(l_array, in_low, j);     
      END IF;
 
      IF i<in_high THEN
          l_array:=sort(l_array, i, in_high);  
      END IF;
 
      RETURN l_array;
 
END sort;
----------------------Быстрая сортировка---------------------------------------------------------------------------------------------------------
FUNCTION Quick_sort(in_unsorted_list IN sort_lst) RETURN sort_lst
  IS   
    l_unsorted_list sort_lst:=sort_lst();
    l_res sort_lst:=sort_lst();
BEGIN
  l_unsorted_list:=in_unsorted_list;  
  l_unsorted_list:=sort(l_unsorted_list, l_unsorted_list.FIRST, l_unsorted_list.LAST);
  RETURN l_unsorted_list;  
END Quick_sort;
--------------------------------------------------------------------------------------------------------------------------------------------------