Pikalajittelu

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

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 $O(n\log n)$ vertailua, mutta pahimmassa tapauksessa $O(n^{2})$, 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 $O(n\log n)$ -algoritmit. Pikalajittelun tilavaatimus on $O(\log n)$ keskimäärin ja $O(n)$ 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.