Pikalajittelu

Wikipediasta
Siirry navigaatioon Siirry hakuun
Pikalajittelu käytännössä. Vaakaviivat ovat sarana-alkioita.

Pikalajittelu (quicksort) on C. A. R. Hoaren kehittämä epävakaa lajittelualgoritmi, jossa joukosta valitaan tietty alkio vertailukohdaksi. Tätä alkiota nimitetään sarana-alkioksi (pivot), koska se yhdistää aineiston eri osat. Muut alkiot lajitellaan kahteen ryhmään sarana-alkiota käyttäen (esimerkiksi alkiota pienemmät ja suuremmat/yhtäsuuret), joille rekursiivisesti toistetaan sama ryhmittely uudella sarana-alkiolla.

Algoritmin pseudokoodi[muokkaa | muokkaa wikitekstiä]

Algoritmin pseudokoodi:

funktio pikajärjestys(lista)
  Jos listan pituus <= 1 
  Niin palauta lista
  Muuten valitse ja poista sarana-alkio listasta
         palauta pikajärjestys([listan sarana-alkiota pienemmät]) 
                 + [sarana-alkio] +
                 pikajärjestys([listan sarana-alkiota suuremmat ja yhtäsuuret])  

Esimerkki[muokkaa | muokkaa wikitekstiä]

  • pikajärjestys([5,3,2,8,9,0,6]) (sarana-alkioksi valitaan joukon viimeinen alkio)
  • sarana-alkio=6 →
    • pienemmät=[5,3,2,0]
    • suuremmat=[8,9]

  • palauta pikajärjestys([5,3,2,0]) + [6] + pikajärjestys([8,9])

  • palauta [0] + pikajärjestys([3,2,5]) + [6] + pikajärjestys([8]) + [9]

  • palauta [0] + pikajärjestys([3,2]) + [5] + [6] + [8] + [9]

  • palauta [0] + [2] + pikajärjestys([3]) + [5] + [6] + [8] + [9]

  • palauta [0] + [2] + [3] + [5] + [6] + [8] + [9]

  • palauta [0,2,3,5,6,8,9]

Esimerkkitoteutus C-kielellä[muokkaa | muokkaa wikitekstiä]

Esimerkkikoodi lajittelee mitä tahansa alkioita sisältävän taulukon järjestykseen (ei-vähenevä järjestys). Muuttuja "tab" on taulukon ensimmäisen alkion osoite, "ts" taulukon alkioiden lukumäärä (tai lajiteltavien alkioiden haluttu lukumäärä), "vs" taulukon alkion koko tavuina, "cmp" vertailufunktion osoite ja "swap" funktio taulukon kahden alkion paikkojen vaihtamiseksi. Sarana-alkiona (pivot) toimii taulukon ensimmäinen alkio (jonka indeksi on 0).

void quicksort(void *tab, int ts, int vs, int (*cmp)(void *a, void *b)) {
    register int i;
    register int j;
    register char *ctab;

    ctab = (char *)tab;
    if (tab != NULL && ts > 1 && vs > 0) {
        i = 1;
        j = ts - 1;
        while (i <= j) {
            if ((*cmp)(ctab, ctab + i * vs) > 0)
                i++;
            else
                swap(ctab + i * vs, ctab + vs * j--, vs);
        }
        swap(ctab, ctab + (i - 1) * vs, vs);
        quicksort(ctab, i - 1, vs, cmp);
        quicksort(ctab + i * vs, ts - i, vs, cmp);
    }
}

void swap(void *a, void *b, int vs) {
    register char c;
    register int i;

    if (a != b) {
        i = -1;
        while (++i < vs) {
            c = *((char *)a + i);
            *((char *)a + i) = *((char *)b + i);
            *((char *)b + i) = c;
        }
    }
}

Aika- ja tilavaatimus[muokkaa | muokkaa wikitekstiä]

Yleinen pikalajittelu vaatii keskimäärin vertailua, mutta pahimmassa tapauksessa , jos järjestettävät alkiot ovat jo valmiiksi järjestyksessä. Pikalajittelu on kevyt ja nopea lähes kaikilla suorittimilla, mikä tekee siitä nopeamman kuin muut -algoritmit. Pikalajittelun tilavaatimus on keskimäärin ja pahimmassa tapauksessa. Pikalajittelun pahimman tilanteen välttämiseksi voidaan siihen liittää algoritmi, joka ennen järjestämistä sekoittaa järjestettävät alkiot epäjärjestykseen.