Greitojo rikiavimo algoritmas
Algoritmas | |
Tipas | Rūšiavimo algoritmai |
Pavadinimas | Greitasis rūšiavimas (Quicksort) |
Sudėtingumas | Vidutinis - Nlog(N); blogiausias - N2 |
Greitos nuorodos |
Greito rūšiavimo algoritmas (angl. quicksort) - vienas iš rūšiavimo algoritmų, pasiūlytas C. A. R. Hoare 1962 metais. Dėl realizavimo paprastumo ir efektyvaus atminties naudojimo, šis algoritmas labai paplitęs.
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 rūšiuoti 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.
Sudėtingumas
Greito rūšiavimo 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.
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 rūšiuojami šie du masyvai
- Kai nebelieka ką rūšiuoti, pagrindinis masyvas yra surikiuotas
Realizacija
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 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); } } ... }
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 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