Quicksort
Vikipediya, ochiq ensiklopediya
Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzog'i bilan O(n2) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O(n log n) ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi.
Contents |
[tahrir] Ishlash printsipi
- Massivda ixtiyoriy tayanch element tanlaymiz.
- Keyin undan kichik yoki teng elementlarni uning chap tomoniga, katta elementlarni o'ng tomoniga o'tkazamiz.
- 1-2-chi qadamlarni tayanch elementning o'ng va chap tomonlaridagi elementlar uchun qo'llaymiz.
Algorimning 2 qadami turlicha bo'lib uning bir nechta realizatsiyalari mavjud. Ayni shu 2 qadamda elementlarni joylashtirish algoritmi tufayli algoritm saralash algoritmlari ichida eng tez ishlaydiganlaridan biridir.
[tahrir] Tez saralash (QuickSort) algoritmining javascriptdagi realizatsiyasi
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;
}
[tahrir] C
void swap(int *a, int *b)
{
int t=*a; *a=*b; *b=t;
}
void sort(int arr[], int beg, int end)
/* sort elements arr[beg],...,arr[end-1]*/
{
int middle,l,r;
if (end > beg + 1)
{
middle=arr[(beg+end)/2];
l=beg;r=end;
while (l < r)
{
while (arr[l]<middle) l++;
while (arr[r]>middle) r--;
if (l<r)
{
swap(arr[l],arr[r]);
l++;r--;
}
}
sort(arr, beg, r);
sort(arr, l, end);
}
}
[tahrir] C++
#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 >()
);
}
[tahrir] 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);
}
}
[tahrir] Python
def qsort(L):
if L == []: return []
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]])
[tahrir] Joy
DEFINE sort == [small][]
[uncons [>] split]
[[swap] dip cons concat] binrec .
[tahrir] PHP
function quicksort($seq) {
if(count($seq)>1) {
$k = $seq[0];
$x = array();
$y = array();
for($i=1; $i<count($seq); $i++) {
if($seq[$i] <= $k) {
$x[] = $seq[$i];
} else {
$y[] = $seq[$i];
}
}
$x = quicksort($x);
$y = quicksort($y);
return array_merge($x, array($k), $y);
} else {
return $seq;
}
}
[tahrir] Haskell
sort :: (Ord a) => [a] -> [a]
sort [] = []
sort (pivot:rest) = sort [y | y <- rest, y < pivot]
++ [pivot] ++
sort [y | y <- rest, y >=pivot]
[tahrir] 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).
[tahrir] 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
[tahrir] SML
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

