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*&nbsp;log&nbsp;*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**< 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|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|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|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<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;
   }
 }

=== [[Haskell|Haskell]] ===

  sort :: (Ord a)   => [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?
   left, right = array[1..-1].partition { |y| y <= array.first }
   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'''