Greitojo rikiavimo algoritmas - Vikipedija

# Greitojo rikiavimo algoritmas

### Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Algoritmas
Tipas | Rikiavimo algoritmai
Pavadinimas | Greitasis rikiavimas (Quicksort)
Sudėtingumas | Vidutinis - Nlog(N); blogiausias - N2

Greitos nuorodos

- Algoritmai
  - Rikiavimo algoritmai
    - Greitasis rikiavimas
- Šablonas

Greito rikiavimo algoritmas (angl. quicksort) - vienas iš rikiavimo algoritmų, pasiūlytas C. A. R. Hoare 1962 metais. Dėl realizavimo paprastumo ir efektyvaus atminties naudojimo, šis algoritmas labai paplitęs.

## [taisyti] Savybės

Algoritmas yra nestabilus, jis naudojasi skaldyk ir valdyk paradigma, pagrindinė idėja - išskaidžius duomenų seką į dvi dalis, kad vienoje dalyje visi elementai būtų mažesni už kitos dalies elementus, šias dvi dalis galima rikiuoti nepriklausomai viena nuo kitos. Tai daroma rekursiškai. Elementas, atskiriantis dalis - slenkstis.

Teigiamos algoritmo savybės:

- beveik nenaudojama papildoma atmintis;
- laukiamu atveju algoritmo sudėtingumas yra O(N log N);
- algoritmo realizavime gali būti apibrėžti labai trumpi vidiniai ciklai.

Neigiamos algoritmo savybės:

- algoritme naudojama rekursija, todėl nepatogus, kai nėra rekursijos mechanizmo;
- blogiausiu atveju algoritmo sudėtingumas yra O(N2);
- labai jautrus programavimo klaidoms.

## [taisyti] 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 log2N. Tačiau esant "blogiems" duomenims, algoritmo sudėtingumas gali siekti O(N2), dėl to siekiant nuspėjamo rezultato, šis algoritmas derinamas su kitais.

## [taisyti] Algoritmas

Algoritmas veikia tokiu principu:

- Pasirenkamas tam tikras masyvo elementas (angl. pivot); geriausiai kai jis yra mediana, tačiau praktikoje tai neefektyvu
- Perkeliant elementus, masyvas suskirstomas į dvi dalis: pirmoje dalyje yra tik elementai mažesni už pivot, kitame tik didesni
- Naudojantis algoritmu, rekursyviai rikiuojami šie du masyvai
- Kai nebelieka ką rikiuoti, pagrindinis masyvas yra surikiuotas

## [taisyti] Algoritmo pagerinimai

Praktikoje, norint pagreitinti šio algoritmo veikimo laiką galima taikyti keletą būdų:

- Prieš rikiavimą reikia visus masyvo skaičius atsitiktinai sukeisti vietomis. Algoritmas su tokiu pagerinimu vadinamas Randomized Quicksort ir dirba vidutiniškai O(nlogn) laiko.
- Trumpiems masyvams naudojamas įterpimo rikiavimas. Dėl rekursijos ir kitų "blogų" faktorių Quicksort tampa ne toks efektyvus trumpiems masyvams. Todėl, jei masyve mažiau nei 12 elementų, naudojamas įterpimo rikiavimas.
- Jei paskutinis funkcijos elementas yra “iškvietimas” šios funkcijos, tai kalbama apie “uodeginę” rekursiją. Ją reikėtų pakeisti iteracijomis, šiuo atveju geriausiai naudoti steką.
- Po skaidymo pirmiausia rikiuojama mažesnė dalis, tai pagerina steko naudojimą, nes trumpos sekos rikiuojamos greičiau ir joms reikalingas trumpesnis stekas. Atminties reikalavimai sumažėja nuo n iki logn.

## [taisyti] Algoritmo ypatumai

- Rekursijos eliminavimas – reikia kruopščiai valdyti algoritmo vykdymo eigą ir iš anksto numatyti nepalankių arba išsigimusių sekų atvejus.
- Trumpi posekiai – kai reikia rikiuoti trumpą posekį, tarkime, tokį, kad r-1=<M, tikslinga naudoti kokį nors tiesioginį metodą, pvz., įterpimą, ribinį skaičių M parenkant tokį, kokio reikia.
- Slenksčio parinkimas - dažniausiai naudojamas arba didesnio iš pirmųjų dviejų nesutampančių sekos elementų principas arba vadinamasis medianos iš trijų elementų principas.

## [taisyti] Realizacija

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

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

### [taisyti] Realizacija Java kalba

    public class Pavyzdys {

       ....

       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 + (int)(Math.random() * (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);
           }
       }

       ...

    }

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

### [taisyti] Realizacija Python kalba

    def dalinti ( kaire, desine ):
        t = indeksas = kaire;
        for j in xrange( 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

Rodomas puslapis "http://lt.wikipedia.org../../../g/r/e/Greitojo_rikiavimo_algoritmas.html"

Kategorija: Rikiavimo algoritmai

##### Views

- Straipsnis
- Aptarimas
- Dabartinė versija

##### Paieška

##### Kitomis kalbomis

- العربية
- Català
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Italiano
- 日本語
- 한국어
- Nederlands
- Polski
- Português
- Русский
- Slovenčina
- Slovenščina
- Svenska
- Українська
- O'zbek
- Tiếng Việt
- 中文