Greitojo rikiavimo algoritmas

Sudėtingumas

Greito rikiavimo algoritmas geriausiai veikia, kai kiekvienąkart slenkstis skaido duomenis po lygiai. Šiuo atveju algoritmo sudėtingumas yra O(N  log N), lyginimo operacijų naudojama 2N  log₂N. Tačiau esant „blogiems“ duomenims, algoritmo sudėtingumas gali siekti O(N²), dėl to siekiant nuspėjamo rezultato, šis algoritmas derinamas su kitais.

Realizacija C kalba

void swap(int a, int b) {
  int t = list[a];
  list[a] = list[b];
  list[b] = t;}int partition(int a, int b, int piv) {
  int store, i;
  int piv_value = list[piv];
   
  store = a;
  swap(piv, b);
  for (i = a; i < b; i++) {
    if (list[i] < piv_value) {
      swap(i, store);
      store++;
    }
  }
  swap(store, b);
  return store;}
 
void sort(int a, int b) {
  int piv;

  if (a < b) {
    piv = partition(a, b, (a+b)/2);
    sort(a, piv-1);
    sort(piv+1, b);
  }}

Realizacija C++ kalba

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

Realizacija Java kalba

import java.util.Random;public class Pavyzdys {
   private static final Random rand = new Random();
   ....

   public static void keisti(int[] masyvas, int pirmas, int antras) {
       if (pirmas != antras) {
           masyvas[antras] -= masyvas[pirmas];
           masyvas[pirmas] += masyvas[antras];
           masyvas[antras] *= -1;
           masyvas[antras] += masyvas[pirmas];
       }
   }
   
   public static int dalinti(int[] masyvas, int kaire, int desine) {
       int t = kaire + rand.nextInt(desine - kaire + 1);
       keisti(masyvas, t, kaire);
       int indeksas = kaire;
       for (int j = kaire + 1; j <= desine; ++j) {
           if (masyvas[j] < masyvas[kaire]) {
               ++indeksas;
               keisti(masyvas, indeksas, j);                            
           }
       }
       keisti(masyvas, kaire, indeksas);
       return indeksas;
   }
   
   public static void rusiuoti(int[] masyvas, int kaire, int desine) {
       if (kaire < desine) {
           int indeksas = dalinti(masyvas, kaire, desine);
           rusiuoti(masyvas, kaire, indeksas - 1);
           rusiuoti(masyvas, indeksas + 1, desine);
       }
   }
   
   ...}

Realizacija Perl kalba

@masyvas = ( -1, 0, 7, 8, 6, 9, 5, 2, 2, -3, 4, 6, 8, 9, -2 );rusiuoti( 0, $#masyvas );print "Rezultatas: @masyvas";sub keisti {
    ( $_[0], $_[1] ) = ( $_[1], $_[0] );}sub dalinti {
    my ($kaire, $desine, $t, $indeksas) = ($_[0], $_[1], $_[0], $_[0]);
    for ( $j = $kaire + 1 ; $j <= $desine ; ++$j ) {
        if ( $masyvas[$j] < $masyvas[$kaire] ) {
            ++$indeksas;
            keisti( $masyvas[$indeksas], $masyvas[$j] );
        }
    }
    keisti( $masyvas[$kaire], $masyvas[$indeksas] );
    return $indeksas;}sub rusiuoti {
    my ( $kaire, $desine ) = ( $_[0], $_[1] );
    if ( $kaire < $desine ) {
        my ($indeksas) = dalinti( $kaire, $desine );
        rusiuoti( $kaire, $indeksas – 1 );
        rusiuoti( $indeksas + 1, $desine );
    }}

Realizacija Python kalba

def dalinti ( kaire, desine ):
    t = indeksas = kaire;
    for j in range( kaire + 1, desine + 1 ):
        if masyvas[j] < masyvas[kaire]:
            indeksas += 1;
            masyvas[indeksas], masyvas[j] = masyvas[j], masyvas[indeksas]
    masyvas[kaire], masyvas[indeksas] = masyvas[indeksas], masyvas[kaire]
    return indeksas;def rusiuoti( kaire, desine ):
    if kaire < desine :
        indeksas = dalinti( kaire, desine )
        rusiuoti( kaire, indeksas - 1)
        rusiuoti( indeksas + 1, desine )
    
masyvas = [ -1, 0, 7, 8, 6, 9, 5, 2, 2, -3, 4, 6, 8, 9, -2 ]rusiuoti ( 0, len( masyvas ) - 1 )print ("Rezultatas: ", masyvas)