Pikalajittelu

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])

Esimerkkitoteutus C-kielellä

Esimerkkikoodi lajittelee mitä tahansa alkioita sisältävän taulukon järjestykseen (ei-vähenevä järjestys). Muuttuja "alkio" on taulukon ensimmäisen alkion osoite, "lkm" taulukon alkioiden lukumäärä (tai lajiteltavien alkioiden haluttu lukumäärä), "koko" taulukon alkion koko tavuina, ja "cmp" lajittelussa välttämättömän vertailufunktion osoite (joka on toteutettava itse tai jotenkin muutoin). 
void swap(void *valkio1, void *valkio2, int koko) /* kahden alkion paikkojen vaihtoa varten */{
    int i;
    char apu;
    for (i = 0; i < koko; i++)
    {
        apu = ((char*)valkio1)[i];
        ((char*)valkio1)[i] = ((char*)valkio2)[i];
        ((char*)valkio2)[i] = apu;
    }}void quicksort(void *alkio, int lkm, int koko, int (*cmp)(void *valkio1, void *valkio2)){
  if(alkio != NULL && lkm > 1 && koko > 0) /* jonkinlaiset järkevät alkuehdot */
    {
      int i1=lkm-2, i2=0;

      for(i1=lkm-2; i1>=i2; i1--)
        {
          if(i1==i2)
            if(cmp((char *)alkio+(lkm-1)*koko, (char *)alkio+i1*koko) < 0)
              i2++;
            else
              {
              }
          else
            if(cmp((char *)alkio+(lkm-1)*koko, (char *)alkio+i1*koko) < 0)
              {
                while(i2<i1 && cmp((char *)alkio+(lkm-1)*koko, (char *)alkio+i2*koko)<0)
                  i2++;
                if(i2<i1)
                  swap((char *)alkio+i1*koko, (char *)alkio+i2*koko, koko);
                i2++;
              }
        }

      if(i2<lkm-1)
        swap((char *)alkio+(lkm-1)*koko, (char *)alkio+i2*koko, koko);

      /* rekursiokutsut tarvittaessa */
      if(i2>1) /* luonnollisesti yhden alkion kokoista taulukkoa ei tarvitse lajitella */
        quicksort(alkio, i2, koko, cmp);
      if(i2<lkm-2) /* sama kuin yllä */
        quicksort((i2+1)*koko+(char *)alkio, lkm-i2-1, koko, cmp);
    }}

Aika- ja tilavaatimus

Yleinen pikalajittelu vaatii keskimäärin O(n log(n)) vertailua, mutta pahimmassa tapauksessa O(n²), 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.