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<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;
 }
 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);
   }
 }

 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 >()
   );
 }

 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<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 

  sort :: (Ord a)   => [a] -> [a]

  sort []           = []
  sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                      ++ [pivot] ++ 
                      sort [y | y <- rest, 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 = array[1..-1].partition { |y| y <= array.first }
   sort(left) + [ array.first ] + sort(right)
 end

 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