Quicksort

Vikipediya, ochiq ensiklopediya

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.

Contents 1 Ishlash printsipi 2 Tez saralash (QuickSort) algoritmining javascriptdagi realizatsiyasi 2.1 C 2.2 C++ 2.3 Java 2.4 Python 2.5 Joy 2.6 PHP 2.7 Haskell 2.8 Prolog 2.9 Ruby 2.10 SML

[tahrir] 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.

[tahrir] 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;
}

[tahrir] 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);
  }
}

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

[tahrir] 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);
    }
}

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

[tahrir] Joy

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

[tahrir] 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;
  }
}

[tahrir] Haskell

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

[tahrir] 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).

[tahrir] 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

[tahrir] 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