Quicksort

Tez saralash(quicksort) algoritmi - Charlz Xoar tomonidan yaratilgan mashxur saralash algoritmidir. Ushbu algoritm n ta elementdan iborat massivni eng uzogʻi bilan O(n²) 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

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