Pikalajittelu

Wikipedia

Pikalajittelu on lajittelualgoritmi, jossa joukosta valitaan yksi alkio (pivot) vertailukohdaksi. Muut alkiot lajitellaan kahteen ryhmään pivotalkiota käyttäen (esimerkiksi pivotia pienemmät ja suuremmat + yhtäsuuret), joille rekursiivisesti toistetaan sama ryhmittely nyt uudella pivotilla.

Algoritmi pseudokoodina:

funktio pikajarjestys(lista)
  Jos listan pituus <= 1 
  Niin palauta lista
  Muuten valitse ja poista pivot listasta
         palauta pikajarjestys([listan pivotia pienemmät]) 
                 + [pivot] +
                 pikajarjestys([listan pivotia suuremmat ja yhtäsuuret])  

esim.

pikajarjesta([6,3,2,8,9,0,5])

pivot=6 ->

 pienet=[3,2,0,5]
 suuret=[8,9]

->

palauta pikajarjesta([3,2,0,5]) + [6] + pikajarjesta([8,9])

->

palauta pikajarjesta([2,0]) + [3] + pikajarjesta([5]) + [6] + [8] + [9]

->

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

->

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

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, joka 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.