Quicksort

Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashhur 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.

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.

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 middle) r--;
 if (l
 #include 
 #include 
 
 template
 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
 inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
 quick_sort( first, last,
 std::less_equal::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 = arrayi;
 arrayi = arrayj;
 arrayj = tmp;
 }
 
 private int partition(Object array, int begin, int end, Comparator cmp) {
 int index = begin + RND.nextInt(end - begin + 1);
 Object pivot = arrayindex;
 swap(array, index, end); 
 for (int i = index = begin; i 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 L1: if x=L0)

 Joy 

 DEFINE sort == small
 uncons > split
 swap dip cons concat binrec .

PHP

 function quicksort($seq) {
 if(count($seq)>1) {
 $k = $seq0;
 $x = array;
 $y = array;
 for($i=1; $i a -> a
 
 sort = 
 sort (pivot:rest) = sort y | y =pivot

 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 = array1..-1.partition { |y| y 
 | (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