Jump to content

Қуиcксорт

From Ziyosfera
(Redirected from Tez Saralash)

Тез саралаш(қуиcксорт) алгоритми - Чарлз Хоар томонидан яратилган машҳур саралаш алгоритмидир. Ушбу алгоритм н та элементдан иборат массивни энг узоғи билан О(н2) вақтда саралайди. Бироқ алгоритм бажарилиш тезлигининг математик кутилмаси О(н лог н) га тенг ва у бошқа шундай тезликда бажарилувчи алгоритмлардан тезроқ ишлайди.

Ишлаш принципи

  1. Массивда ихтиёрий таянч элемент танлаймиз.
  2. Кейин ундан кичик ёки тенг элементларни унинг чап томонига, катта элементларни ўнг томонига ўтказамиз.
  3. 1-2-чи қадамларни таянч элементнинг ўнг ва чап томонларидаги элементлар учун қўллаймиз.

Алгоримнинг 2 қадами турлича бўлиб унинг бир нечта реализациялари мавжуд. Айни шу 2 қадамда элементларни жойлаштириш алгоритми туфайли алгоритм саралаш алгоритмлари ичида энг тез ишлайдиганларидан биридир.

Тез саралаш (ҚуиcкСорт) алгоритмининг жавасcриптдаги реализацияси

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;
}
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);
  }
}
#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 >()
  );
}
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);
    }
}
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]])
DEFINE sort == [small][]
               [uncons [>] split]
               [[swap] dip cons concat] binrec .
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;
  }
}
 sort :: (Ord a)   => [a] -> [a]
 
 sort []           = []
 sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                     ++ [pivot] ++ 
                     sort [y | y <- rest, y >=pivot]
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).
def sort(array)
  return [] if array.empty?
  left, right = array[1..-1].partition { |y| y <= array.first }
  sort(left) + [ array.first ] + sort(right)
end
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