Pikalajittelu

Wikipedia
Loikkaa: valikkoon, 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 "alkio" on taulukon ensimmäisen alkion osoite, "lkm" taulukon alkioden 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[muokkaa | muokkaa wikitekstiä]

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.