From Wikipedia, the free encyclopedia
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ä.
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.
[ 2 ] [ 4 ] [ 3 ] [ 0 ] [ 6 ] [ 1 ] [ 5 ] [8] [7]
[ 8 ] [ 7 ] [ 5 ] [ 4 ] [ 6 ] [ 1 ] [ 3 ] [0] [2]
Tulos: [8] [ 2 ] [ 7 ] [ 5 ] [ 4 ] [ 6 ] [ 1 ] [ 3 ] [0] ---
Tulos: [8] [ 7 ] [ 6 ] [ 5 ] [ 4 ] [ 2 ] [ 1 ] [ 3 ] [0]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.