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

 

Работает для произвольного массива из n целых чисел.

Sub QSort(ByRef arr As Variant, ByVal iLbound As Integer, iUbound As Integer)

Dim iL As Integer, iU As Integer

End If

End Sub

 

==[[C Sharp|C#]]==

 

int partition (int[] array, int start, int end)

{

quicksort (array, pivot+1, end);

}

 

==[[Язык Си в примерах|C]]==

 

Работает для произвольного массива из n целых чисел.

int n, a[n]; //n - количество элементов

void qs(int *s_arr, int first, int last)

}

}

 

Исходный вызов функции qs для массива из n элементов будет иметь следующий вид.

qs(a, 0, n-1);

 

== [[C Sharp|C#]] ==

 

int partition (int[] array, int start, int end)

{

quicksort (array, pivot+1, end);

}

 

=== C# с обобщёнными типами ===

Тип Т должен реализовывать интерфейс [http://msdn.microsoft.com/ru-ru/library/4d7sx9hd.aspx IComparable<T>].

 

static int partition<T>( T[] m, int a, int b)

where T : IComparable<T>

//

 

 

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

 

using System;

using System.Collections.Generic;

}

}

 

== [[Си++|C++]] ==

=== Быстрая сортировка на основе библиотеки [[Си++/Стандартная библиотека|STL]] ===

 

#include <algorithm>

#include <iterator>

quick_sort( first, last,

std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()

 

=== Для вещественных чисел ===

{

double x = *(a+r);

quicksort (a, q+1, r);

}

 

== [[Java]] ==

и с измерением времени сортировки массива нанотаймером (работает только если нет совпадающих элементов массива).

 

import java.util.Random;

 

}

}

 

=== Java без рекурсии, с использованием стека ===

пошаговый алгоритм с возможностью вывода на экран текущего действия

 

import java.awt.Color;

import java.awt.Graphics;

}

}

 

== [[JavaScript]] ==

 

/*

* Алгоритм быстрой сортировки

}

}

 

'''function''' QuickSort(A, p, r)

 

Через 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 []

 

== [[w:Joy|Joy]] ==

== [[PHP]] ==

 

/*

* Функция, непосредственно производящая сортировку.

 

}

 

function quicksort ($array, $l=0, $r=0) {

if($r === 0) $r = count($array)-1;

if ($j > $l) quicksort ($array, $l, $j);

}

 

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

 

Данная версия алгоритма является самой короткой из возможных, но тратит слишком много дополнительной памяти. На практике такой алгоритм использоваться не может. Стоит также отметить, что списки — неудачный выбор для реализации быстрой сортировки.

 

В отличие от других вариантов реализации на функциональных языках, представленных здесь, приводимая реализация алгоритма на Лиспе является "честной" - она не порождает новый отсортированный массив, а сортирует тот, который поступил ей на вход, "на том же месте". При первом вызове функции в параметры l и r необходимо передать нижний и верхний индексы массива (или той его части, которую требуется отсортировать). Код использует "императивные" макросы Common Lisp'а.

(defun quickSort (array l r)

(let ((i l)

(if (>= (- r i) 1) (quickSort array i r)))

array)

 

== [[w:Pascal|Pascal]] ==

 

Внутреннее условие, помеченное комментарием «это условие можно убрать» — необязательно. Его наличие влияет на действия в ситуации, когда поиск находит два равных ключа: при наличии проверки они останутся на местах, а при отсутствии — будут обменены местами. Что займёт больше времени — проверки или лишние перестановки, — зависит как от архитектуры, так и от содержимого массива (очевидно, что при наличии большого количества равных элементов лишних перестановок станет больше). Следует особо отметить, что наличие условия не делает данный метод сортировки устойчивым.

const max=20; { можно и больше... }

type

sort(Lo,Hi)

end; {quicksort}

 

Устойчивый вариант (требует дополнительно O(n)памяти)

 

const max=20; { можно и больше… }

type

end; {quicksort}

 

 

=== Быстрая сортировка, нерекурсивный вариант ===

Нерекурсивная реализация быстрой сортировки через управляемый вручную [[w:стек|стек]].

Функции compare и change реализуются в зависимости от типа данных.

procedure quickSort(var X: itemArray; n: integer);

type

until stack=nil

end;

 

=== Частично рекурсивная реализация ===

а бо’льшая — в цикле. Это гарантирует глубину рекурсии не более lg(N).

 

procedure qSort(var ar: array of real;);

procedure sort(var ar: array of real; low, high: integer);

sort(ar, 0, High(ar));

end;

 

=== Пример реализации алгоритма в объектно-ориентированном стиле с обобщением по типу данных (Generics) ===

 

== [[Perl]] ==

@out=(5,2,7,9,2,5,67,1,5,7,-8,5,0);

sub sortQ{

}

sortQ(0, $#out);

 

== [[w:F Sharp|F#]] ==

 

<!-- http://habrahabr.ru/blogs/starting_programming/50967/ -->

let rec quicksort = function

[] -> []

 

let res = quicksort list1

 

== [[w:OCaml|OCaml]] ==

 

 

let rec qsort l=match l with

[]->[]

|a::b-> (qsort (List.filter ((>=) a) b) lt) @ [a] @ (qsort (List.filter ((<) a) b ));;

 

== [[w:Erlang|Erlang]] ==

 

qsort([]) -> [];

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

 

== [[Язык программирования D|D]] ==

 

array qsort(array)(array _a)

{

 

}

 

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

 

import std.algorithm;

 

_qsort3( a[1..$].filter!( e => a[0] < e ).array );

}

 

== [[Scala]] ==

 

def qsort(xs: List[Int]): List[Int] = xs match {

case head :: tail =>

case Nil => Nil

}

 

Реализация с применением дженериков для типов данных, реализующих трейт Ordering:

def qSort[T](list: List[T])(implicit ord: Ordering[T]): List[T] = {

import ord._

}

}

 

== [[w:Clojure|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)}

[A]

(q-sort (filter (< A) [A|B]))))

 

== [[w:VB.NET|VB.NET]] ==

 

Судя по тестам, сортировка пузырьком 5000 занимает в 8 с половиной раз больше времени, чем qSort'ом

Sub Swap(ByRef Val1, ByRef Val2)

Dim Proc

quicksort(a, 0, a.Length())

End Sub

 

 

== Встроенный язык 1С 8.* ==

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

 

Функция СравнитьЗначения(Знач1, Знач2)

Если Знач1>Знач2 Тогда

qs_0(Список, Первый, Последний);

КонецПроцедуры

 

== [[w:Turbo Basic|Turbo Basic 1.1]] ==

 

LOCAL I,J,X,TEMP

 

FN QSORT=TRUE

END DEF

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

LOW=N1

HIGH=N2

F=FN QSORT(LOW,HIGH)

 

== [[w:PL/SQL|PLSQL]] ==

 

----------------------------------------------------------------------------------

type sort_lst is table of integer;

end Quick_sort;

--------------------------------------------------------------------------------------------------------------------------------------------------

 

{{BookCat | filing = deep}}