Реализации алгоритмов/Сортировка/Быстрая
Некоторые из представленных здесь реализаций используют в качестве опорного элемента один из крайних элементов подмассива. Эти реализации страдают одним общим недостатком: при передаче им уже отсортированного массива в качестве параметра, их время работы становится порядка .
В качестве опорного элемента следует выбирать случайный элемент массива, чтобы получить гарантированное время сортировки в среднем. В случае, если использование случайных чисел нежелательно, в качестве опорного элемента можно выбрать, например, элемент в середине массива, но такие алгоритмы всё равно будут работать за времени на некоторых специально-сконструированных массивах.
Работает для произвольного массива из n целых чисел.
Sub QSort(ByRef arr As Variant, ByVal iLbound As Integer, iUbound As Integer)
Dim iL As Integer, iU As Integer
Dim iVal As Integer, iSwap As Integer
iL = iLbound: iU = iUbound
iVal = arr((iLbound + iUbound) \ 2)
Do While iL <= iU
Do While arr(iL) < iVal And iL < iUbound
iL = iL + 1
Loop
Do While iVal < arr(iU) And iU > iLbound
iU = iU - 1
Loop
If iL <= iU Then
iSwap = arr(iL)
arr(iL) = arr(iU)
arr(iU) = iSwap
iL = iL + 1
iU = iU - 1
End If
Loop
If iLbound < iU Then
Call QSort(arr, iLbound, iU)
End If
If iL < iUbound Then
Call QSort(arr, iL, iUbound)
End If
End Sub
int Partition(int[] array, int start, int end)
{
int marker = start; // divides left and right subarrays
for (int i = start; i < end; i++)
{
if (array[i] < array[end]) // array[end] is pivot
{
(array[marker], array[i]) = (array[i], array[marker]);
marker += 1;
}
}
// put pivot(array[end]) between left and right subarrays
(array[marker], array[end]) = (array[end], array[marker]);
return marker;
}
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);
}
Работает для произвольного массива из n целых чисел.
int n, a[n]; //n - количество элементов
void qs(int *s_arr, int first, int last)
{
if (first < last)
{
int left = first, right = last, middle = s_arr[(left + right) / 2];
do
{
while (s_arr[left] < middle) left++;
while (s_arr[right] > middle) right--;
if (left <= right)
{
int tmp = s_arr[left];
s_arr[left] = s_arr[right];
s_arr[right] = tmp;
left++;
right--;
}
} while (left <= right);
qs(s_arr, first, right);
qs(s_arr, left, last);
}
}
Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.
qs(a, 0, n-1);
int partition (int[] array, int start, int end)
{
int temp;//swap helper
int marker = start;//divides left and right subarrays
for ( int i = start; i < end; i++ )
{
if ( array[i] < array[end] ) //array[end] is pivot
{
temp = array[marker]; // swap
array[marker] = array[i];
array[i] = temp;
marker += 1;
}
}
//put pivot(array[end]) between left and right subarrays
temp = array[marker];
array[marker] = array[end];
array[end] = temp;
return marker;
}
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>.
static 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
}
static 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());
}
}
#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 );
}
}
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 >()
);
}
Для вещественных чисел
[править]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);
}
}
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 = new int[N + 1];
// заполнение массива
for (int i = 0; i <= N; i++)
{
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++)
{
yd=A[i];
xs=r.nextInt(N + 1);
A[i]=A[xs];
A[xs]=yd;
}
for (int i = 0; i <= N; i++) 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 - low) / 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);
}
}
Java без рекурсии, с использованием стека
[править]пошаговый алгоритм с возможностью вывода на экран текущего действия
import java.awt.Color;
import java.awt.Graphics;
import java.util.Arrays;
import java.util.Stack;
class ArrRange
{
// структура для хранения индексов границ массива
public int low, high;
public ArrRange(int from, int to)
{
this.low = from;
this.high = to;
}
}
public class QuickSorter
{
// Задаем размер массива
final static int size = 10;
// Объявляем массив
int[] a;
// Стек для хранения индексов начала и конца массива
Stack<ArrRange> stack;
QuickSorter ()
{
a = new int[size];
for (int i = 0; i < size; i++) a[i] = (int) (Math.random() * 100);
stack = new Stack<ArrRange>();
stack.push(new ArrRange(0, a.length - 1));
}
int step = -1; // текущий шаг
int drawStep = -1; // текущий шаг для вывода сообщения
int temp1 = -1, temp2 = -1; // текущие переставляемые элементы
int middle = -1; // середина массива
int opora; // опорный элемент
int i, j;
ArrRange range;
public void NextStep()
{
switch (step)
{
case -1: range = stack.pop(); step = 0; break;
// находим опорный элемент
case 0:
middle = (range.low + range.high) >> 1; opora = a[middle];
i = range.low; j = range.high;
step = 1;
break;
// ишем слева элемент больше опорного
case 1:
while (a[i] < opora) i++;
temp1 = a[i];
step = 2;
break;
// ишем справа элемент меньше опорного
case 2:
while (a[j] > opora) j--;
temp2 = a[j];
step = 3;
break;
// меняем местами
case 3:
if (i <= j)
{
int temp = a[i]; a[i] = a[j]; a[j] = temp;
i++;
j--;
}
step = i <= j ? 1 : 4;
break;
// разделить массив на 2 части
case 4:
if(i < middle)
{
/*
правая часть больше:
если в ней больше 1 элемента - нужно сортировать, отправляем в стек
следующая итерация разделения будет работать с левой частью
*/
if (i < range.high) stack.push (new ArrRange(i, range.high));
range.high = j;
}
else
{
/*
левая часть больше:
следующая итерация разделения будет работать с правой частью
*/
if (j > range.low) stack.push(new ArrRange(range.low, j));
range.low = i;
}
step = (range.low < range.high) ? 0 : (stack.size() > 0) ? -1 : 5;
break;
}
}
public void draw (Graphics g)
{
int h = 30, w = 30, l = 50;
for (int i = 0; i < size; i++)
{
g.setColor(new Color(0, 0, 0));
g.clearRect(l + i * h, 100, w, h);
g.drawRect (l + i * h, 100, w, h);
g.drawString(a[i] + "", l + i * h + 7, 105 + h / 2);
}
g.setColor(new Color(0, 0, 0));
g.drawString("temp1: " + temp1, l, 160);
g.drawString("temp2: " + temp2, l, 180);
g.drawString("opora: " + opora, l, 200);
String s = "";
switch (drawStep)
{
case -1: s = "начинаем сортировку"; break;
case 0: s = "находим опорный элемент"; break;
case 1: s = "ишем слева элемент больше опорного"; break;
case 2: s = "ишем справа элемент меньше опорного"; break;
case 3: s = "меняем местами"; break;
case 4: s = "разделяем массив на 2 части"; break;
case 5: s = "закончили сортировку"; break;
}
g.drawString("Действие: " + s, l, 50);
drawStep = step;
}
}/*
* Алгоритм быстрой сортировки
*
* @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-й элементы массива а (необязательная)
*
*/
const qsort = (data, compare, change) => {
let a = data,
f_compare = compare,
f_change = change;
if (!(a instanceof Array)) { // Данные не являются массивом
return undefined;
};
if (f_compare === undefined) { // Будем использовать простую функцию (для чисел)
f_compare = (a, b) => {
if (a === b) {
return 0;
} else if (a > b) {
return 1;
} else {
return -1;
}
}
};
if (f_change === undefined) { // Будем использовать простую смену (для чисел)
f_change = (a, i, j) => {
const temp = a[i];
a[i] = a[j];
a[j] = temp;
}
};
const qs = (l, r) => {
let 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);
}
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;
}
Через list comprehension:
def qsort(L):
if L: return qsort([x for x in L if x<L[0]]) + [x for x in L if x==L[0]] + qsort([x for x in L 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 []
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
/*
* Функция, непосредственно производящая сортировку.
* Так как массив передается по ссылке, ничего не возвращает.
*/
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, то меняем ячейки друг с другом.
if ($array[$l] > $array[$r]) 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);
}
//Сортировка завершена
}
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);
}
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]
Данная версия алгоритма является самой короткой из возможных, но тратит слишком много дополнительной памяти. На практике такой алгоритм использоваться не может. Стоит также отметить, что списки — неудачный выбор для реализации быстрой сортировки.
В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры 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)
В данном примере показан наиболее полный вид алгоритма, очищенный от особенностей, обусловленных применяемым языком. В комментариях показано несколько вариантов. Представленный вариант алгоритма выбирает опорный элемент псевдослучайным образом, что, теоретически, сводит вероятность возникновения самого худшего или приближающегося к нему случая к минимуму. Недостаток его — зависимость скорости алгоритма от реализации генератора псевдослучайных чисел. Если генератор работает медленно или выдаёт плохие последовательности ПСЧ, возможно замедление работы. В комментарии приведён вариант выбора среднего значения в массиве — он проще и быстрее, хотя, теоретически, может быть хуже.
Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.
const max=20; { можно и больше... }
type
list = array[1..max] of integer;
procedure quicksort(var a: list; );
procedure sort(l,r: integer);
var
i,j,x,y: integer;
begin
i:=l; j:=r; x:=a[l+random(r-l+1)]; { x := a[(l + r) 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; );
var
num: array[1..max] of 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 := l+(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-l) 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;
Частично рекурсивная реализация
[править]Реализация на языке pascal с одной рекурсивной ветвью. После разделения массива меньшая часть сортируется рекурсивным вызовом, а бо’льшая — в цикле. Это гарантирует глубину рекурсии не более lg(N).
procedure qSort(var ar: array of real;);
procedure sort(var ar: array of real; low, high: integer);
var i, j: integer;
m, wsp: real;
begin
repeat
i:=low; j:=high; m:=ar[(i+j) div 2]; // Взятие среднего опорного элемента
repeat
while ar[i]<m do Inc(i);
while ar[j]>m do Dec(j);
if i<=j then begin
wsp:=ar[i]; ar[i]:=ar[j]; ar[j]:=wsp;
Inc(i); Dec(j);
end;
until i>j;
if (j - low) < (high - i) then begin // Сравнение размеров выделенных подмассивов
if low < j then qSort(ar, low, j); // Если первый подмассив меньше - он сортируется рекурсивно,
low := i; // а для следующего прохода цикла выбирается второй подмассив.
end
else begin // в противном случае всё наоборот
if i < high then qSort(ar, i, high); // Рекурсивно сортируется второй подмассив,
high := j; // а в следующем проходе цикла - первый.
end;
until low = high;
end;
begin
sort(ar, 0, High(ar));
end;
Пример реализации алгоритма в объектно-ориентированном стиле с обобщением по типу данных (Generics)
[править]В представленной реализации алгоритма быстрой сортировки элементов массива порядок сортировки определяется пользовательской функцией обратного вызова:
function Comparer(const Left, Right: T): Integer,
которая должна удовлетворять условиям контракта вызова и возвращаемого значения:
- < 0, если Left < Right;
- = 0, если Left = Right;
- > 0, если Left > Right.
Библиотечный модуль
[править]unit VectorT;
interface
type
TVector<T> = record
public type
TComparer = function (const Left, Right: T): Integer;
private
procedure Sort(Comparer: TComparer; Left, Right: Integer); overload;
procedure Swap(One, Two: Integer);
public
Items: TArray<T>;
procedure Sort(Comparer: TComparer); overload;
end;
implementation
procedure TVector<T>.Sort(Comparer: TComparer);
var
Count: Integer;
begin
Count := Length(Items);
if Count > 1 then
Sort(Comparer, 0, Count - 1)
end;
procedure TVector<T>.Sort(Comparer: TComparer; Left, Right: Integer);
var
Delta: Integer;
Minor: Integer;
Major: Integer;
Basis: T;
begin
Delta := (Right - Left) div 2;
if Delta = 0 then
begin
if Comparer(Items[Right], Items[Left]) < 0 then
Swap(Left, Right);
Exit
end;
Minor := Left;
Major := Right;
Basis := Items[Left + Delta];
repeat
while Comparer(Items[Minor], Basis) < 0 do
Inc(Minor);
while Comparer(Basis, Items[Major]) < 0 do
Dec(Major);
if Minor >= Major then
Break;
if Comparer(Items[Major], Items[Minor]) < 0 then
Swap(Minor, Major);
Inc(Minor);
Dec(Major)
until Minor >= Major;
if Left < Major then
Sort(Comparer, Left, Major);
if Minor < Right then
Sort(Comparer, Minor, Right)
end;
procedure TVector<T>.Swap(One, Two: Integer);
var
Item: T;
begin
Item := Items[One];
Items[One] := Items[Two];
Items[Two] := Item
end;
end.
Пример использования
[править]program QuickSort_Demo;
{$APPTYPE CONSOLE}
{$R *.res}
uses
VectorT in 'VectorT.pas';
procedure ShowArray(const Caption: string; const Items: TArray<Integer>);
var
Index: Integer;
begin
WriteLn(Caption);
for Index := Low(Items) to High(Items) do
WriteLn('Items[', Index, '] = ', Items[Index])
end;
type
TSortOrder = record
public
class function Ascending(const Left, Right: Integer): Integer; static;
class function Descending(const Left, Right: Integer): Integer; static;
end;
class function TSortOrder.Ascending(const Left, Right: Integer): Integer;
begin
// Order: Left < Right
Result := Left - Right
end;
class function TSortOrder.Descending(const Left, Right: Integer): Integer;
begin
// Order: Right < Left
Result := Right - Left
end;
var
Vector: TVector<Integer> = (Items: [5, 3, 7, 11, 9]);
begin
ShowArray('Initial array:', Vector.Items);
Vector.Sort(TSortOrder.Ascending);
ShowArray('Sorted ascending:', Vector.Items);
Vector.Sort(TSortOrder.Descending);
ShowArray('Sorted descending:', Vector.Items);
Write('Press [Enter] key to exit ...');
ReadLn
end.
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).
def sort(array)
return [] if array.empty?
left, right = array[1..-1].partition { |y| y <= array.first }
sort(left) + [ array.first ] + sort(right)
end
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
# Функция выбирает подсписок из списка используя условие 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
}
@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);
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
let rec qsort l=match l with
[]->[]
|a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b ));;
qsort([]) -> [];
qsort([H|T]) -> qsort([X || X <- T, X < H]) ++ [H] ++ qsort([X || X <- T, X >= H]).
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 );
}
#[allow(non_camel_case_types)]
type tupe=i64;
fn quicksort(a:&mut Vec<tupe>)
{
if a.len()<=1
{return ();}
let mut amin=Vec::new();
let mut amax=Vec::new();
for _i in &a[1..]
{
if *_i>a[0]
{
amax.push(*_i);
}
else
{
amin.push(*_i);
}
}
quicksort(&mut amin);
quicksort(&mut amax);
amin.push(a[0]);
amin.extend(amax);
for (_num, _i) in amin.iter().enumerate()
{
a[_num]=*_i;
}
}
fn quicksort1(s_arr:&mut [tupe])
{
let last = s_arr.len()-1;
if 0 < last
{
let mut left = 0;
let mut right = last;
let middle = s_arr[ last / 2];
loop
{
while s_arr[left] < middle {left+=1};
while s_arr[right] > middle {right-=1};
if left < right
{
let tmp = s_arr[left];
s_arr[left] = s_arr[right];
s_arr[right] = tmp;
left+=1;
right-=1;
}
else {break;}
}
right-=1;
left+=1;
quicksort1(&mut s_arr[0..=right]);
quicksort1(&mut s_arr[left..=last]);
}
}
fn main()
{
let listfir = vec![10,29,14,4,35,6];
let mut list = listfir.clone();
println!("{:?}", list);
quicksort(&mut list);
println!("{:?}", list);
let mut list = listfir.clone();
println!("{:?}", list);
quicksort1(&mut list[..]);
println!("{:?}", list);
}
def qsort(xs: List[Int]): List[Int] = xs match {
case head :: tail =>
val left = tail.filter(_ < head)
val right = tail.filter(_ >= head)
qsort(left) ++ List(head) ++ qsort(right)
case Nil => Nil
}
Реализация с применением дженериков для типов данных, реализующих трейт Ordering:
def qSort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = {
import ord._
if(list.isEmpty) Nil
else {
val head :: tail = list
val (left, right) = tail.partition(_ <= head)
qSort(left) ::: head :: qSort(right)
}
}
Ленивая реализация:
(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]))))
Судя по тестам, сортировка пузырьком 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(имя сортируемого массива)
Встроенный язык 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(Список, Первый, Последний);
КонецПроцедуры
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)
----------------------------------------------------------------------------------
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_res:=sort(l_unsorted_list, l_unsorted_list.first, l_unsorted_list.last);
return l_res;
end Quick_sort;
--------------------------------------------------------------------------------------------------------------------------------------------------