Quicksort. Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashhur saralash algoritmidir. Ushbu algoritm "n" ta elementdan iborat massivni eng uzogʻi bilan O("n"2) vaqtda saralaydi. Biroq algoritm bajarilish tezligining matematik kutilmasi O("n" log "n") ga teng va u boshqa shunday tezlikda bajariluvchi algoritmlardan tezroq ishlaydi. Ishlash printsipi. 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. Tez saralash (QuickSort) algoritmining javascriptdagi realizatsiyasi. function QuickSort(A, p, r) if(p beg + 1) middle=arr[(beg+end)/2]; l=beg;r=end; while (l < r) while (arr[l]middle) r--; if (l" "#include " "#include " 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 >() 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); 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]]) Joy. DEFINE sort == [small][] [uncons [>] split] [[swap] dip cons concat] binrec . [[PHP]]. function quicksort($seq) { if(count($seq)>1) { $k = $seq[0]; $x = array(); $y = array(); for($i=1; $i [a] -> [a] sort [] = [] sort (pivot:rest) = sort [y | y <- rest, y < pivot] ++ [pivot] ++ sort [y | y <- rest, y >=pivot] [[Prolog|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|Ruby]]. def sort(array) return [] if array.empty? sort(left) + [ array.first ] + sort(right) end [[Standard ML|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 [[Turkum:Saralash algoritmlari]] [[no:Sorteringsalgoritme#Quick sort]]