Pikalajittelu

Pikalajittelu (quicksort) on C. A. R. Hoaren vuonna 1961 julkaisema 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 
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 
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ä 

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;
        }
    }
}

 Esimerkkitoteutus Python-kielellä 

Esimerkkikoodi lajittelee kokonaislukuja sisältävän listan ei-vähenevään järjestykseen. Muuttuja "l" on lista, "f" listan sen alkion indeksinumero, josta lähtien lajittelu halutaan tehdä, ja "length" lajiteltavaksi haluttujen alkioiden lukumäärä. Cmp-funktiota laajentamalla voidaan lajittelu toteuttaa myös sellaisille listoille, joissa on muunkin tyyppisiä alkioita kuin kokonaislukuja.

def cmp(a, b):
    return a > b

def quicksort(l, f, length):
    if length > 1:
        i = 1
        j = length - 1
        while i <= j:
            if cmp(l[f], l[f + i]) == True:
                i += 1
            else:
                l[f + i], l[f + j] = l[f + j], l[f + i]
                j -= 1
        l[f], l[f + i - 1] = l[f + i - 1], l[f]
        quicksort(l, f, i - 1)
        quicksort(l, f + i, length - i)

 Aika- ja tilavaatimus 

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. 

 Lähteet 

Luokka:Lajittelualgoritmit

no:Sorteringsalgoritme#Quick sort