Kekolajittelu

Kekolajittelu on J. W. J. Williamsin vuonna 1964 kehittelemä lajittelualgoritmi, joka perustuu kekorakenteeseen. Aluksi lajiteltavasta joukosta muodostetaan maksimikeko, jonka varmistetaan täyttävän kekoehdon. Kun keko on valmis, sen suurin alkio poistetaan, asetetaan valmiin listan alkuun ennen muita valmiita alkioita ja keko käsitellään uudestaan kekoehdon täyttymiseksi. Tätä jatketaan kunnes alkio on järjestyksessä.

Kekolajittelun esitys. Aluksi alkioista muodostetaan kekoehtoa toteuttava maksimikeko, joka näkyy animaatiossa.

Kekolajittelu on yleensä hivenen hitaampi kuin pikalajittelu, mutta sillä on kuitenkin tätä paljon suotavampi asymptoottinen suoritusaika huonoimmassa tapauksessa, O(n log n). Pikalajittelun tavoin kekolajittelu ei ole vakaa lajittelualgoritmi, eli samansuuruiseksi käsitettävien alkioiden keskinäinen järjestys voi vaihtua lajiteltaessa.

Kekolajittelu toimii minimitilassa eikä siten vaadi joukon koosta riippuvaa lisämuistia.

Esimerkki kekolajittelusta

• Aloitetaan joukosta [2, 4, 3, 0, 6, 1, 5, 8, 7].
• Muodostetaan kekorakenne. Kekorakennetta kuvaa käsiteltävässä joukossa sarja listoja, jotka kuvaavat keon eri tasoja (ylin alkio on ensimmäisenä, sen kaksi ala-alkiota seuraavana, jne.).

             [ 2 ]
     [ 4 ]           [ 3 ]
 [ 0 ]   [ 6 ]   [ 1 ]   [ 5 ] 
[8] [7]

• Suoritetaan heapify-operaatio, joka varmistaa, että keko on kekoehtoa totteleva maksimikeko. Siten ylimpänä on keon suurin alkio, ja kaikki keossa olevat alkiot ovat suurempia kuin mikään niiden alialkioista.

             [ 8 ]
     [ 7 ]           [ 5 ]
 [ 4 ]   [ 6 ]   [ 1 ]   [ 3 ] 
[0] [2]

• Poistetaan keon ylin kohta (korkein arvo) ja asetetaan se listan alkuun. Keko pienenee nyt yhdellä. Otetaan keon 'viimeinen' alkio ja asetetaan se ylimmäksi.

Tulos: [8]

             [ 2 ]
     [ 7 ]           [ 5 ]
 [ 4 ]   [ 6 ]   [ 1 ]   [ 3 ] 
[0] ---

• Suoritetaan siftDown: siirretään ylimpänä olevaa arvoa aina suurimpaa alialkiotaan päin (vaihtaen niiden paikkaa) kunnes kekoehto taas täyttyy. (2 ja 7 sekä 2 ja 6 vaihtavat paikkaa, siinä järjestyksessä.)

Tulos: [8]

             [ 7 ]
     [ 6 ]           [ 5 ]
 [ 4 ]   [ 2 ]   [ 1 ]   [ 3 ] 
[0] 

• Jatketaan suurimman alkion poistamista ja kekoehdon varmistamista kunnes keko on kutistunut yhteen alkioon. Silloin lisäämme tämän alkion ensimmäisenä listaan (sillä kekolajittelu rakentaa listaa suurimmasta pienimpään, lopusta alkuun).