Bosh menuni ochish

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.

Ishlash printsipiTahrirlash

  1. Massivda ixtiyoriy tayanch element tanlaymiz.
  2. Keyin undan kichik yoki teng elementlarni uning chap tomoniga, katta elementlarni oʻng tomoniga oʻtkazamiz.
  3. 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 realizatsiyasiTahrirlash

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

CTahrirlash

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

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

JavaTahrirlash

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

PythonTahrirlash

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

JoyTahrirlash

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

PHPTahrirlash

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

HaskellTahrirlash

 sort :: (Ord a)   => [a] -> [a]
 
 sort []           = []
 sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                     ++ [pivot] ++ 
                     sort [y | y <- rest, y >=pivot]

PrologTahrirlash

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

RubyTahrirlash

def sort(array)
  return [] if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end

SMLTahrirlash

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