Метод Хоара - Быстрая сортировка(Quick-sort)
- Подробности
- Категория: Сортировка и поиск
Быстрая сортировка (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.
Один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n log n) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Отличительной особенностью быстрой сортировки является операция разбиения массива на две части относительно опорного элемента. Например, если последовательность требуется упорядочить по возрастанию, то в левую часть будут помещены все элементы, значения которых меньше значения опорного элемента, а в правую элементы, чьи значения больше или равны опорному. Вне зависимости от того, какой элемент выбран в качестве опорного, массив будет отсортирован, но все же наиболее удачным считается ситуация, когда по обеим сторонам от опорного элемента оказывается примерно равное количество элементов. Если длина какой-то из получившихся в результате разбиения частей превышает один элемент, то для нее нужно рекурсивно выполнить упорядочивание, т. е. повторно запустить алгоритм на каждом из отрезков.
Таким образом, алгоритм быстрой сортировки включает в себя два основных этапа:
- разбиение массива относительно опорного элемента;
- рекурсивная сортировка каждой части массива.
| Худшее время |
O(n2) |
|---|---|
| Лучшее время |
O(n log n) (обычное разделение) |
| Среднее время |
O(n log n) |
| Затраты памяти |
O(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 элементов будет иметь следующий вид.
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
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);
}
}
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 qsort($s) {
for($i=0, $x=$y=array(); $i<count($s)-1; $s[++$i]<=$s[0] ? $x[]=$s[$i] : $y[]=$s[$i]);
return count($s)<=1 ? $s : array_merge(qsort($x), array($s[0]), qsort($y));
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,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 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 .. $] ) );
}
}
Более короткий вариант с использованием стандартной библиотеки 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)
Стоит отметить, что быстрая сортировка может оказаться малоэффективной на массивах, состоящих из небольшого числа элементов, поэтому при работе с ними разумнее отказаться от данного метода. В целом алгоритм неустойчив, а также использование рекурсии в неверно составленном коде может привести к переполнению стека. Но, несмотря на эти и некоторые другие минусы, быстрая сортировка все же является одним из самых эффективных и часто используемых методов.
При написании статьи были использованы открытые источники сети интернет :
