Viikko 9: Tiivistelmä

Viikon 9 aiheena on luentomateriaalin sivut 355–421.

O(n log n)-algoritmit

Tämän viikon tehtävänä on oppia tuntemaan kolme järjestämisalgoritmia, jotka toimivat ajassa O(n log n):

• kekojärjestäminen (heapsort)
• lomitusjärjestäminen (mergesort)
• pikajärjestäminen (quicksort)

Alarajatodistus

O(n log n) on nopein mahdollinen aikavaativuus yleiselle järjestämisalgoritmille.

Tämä johtuu siitä, että taulukon eri järjestyksiä on olemassa n! kpl (kaikki alkioiden permutaatiot). Toimivan järjestämisalgoritmin täytyy tunnistaa mikä tahansa näistä järjestyksistä. Kun algoritmin suoritusta tarkastelee puuna, jokainen kahden alkion vertailu aiheuttaa haarautumisen kahteen osaan. Puussa on n! lehteä, joten sen korkeus on vähintään O(log(n!)). Tämä taas on sama kuin O(log(n)+log(n–1)+...+log(1)) eli O(n log n).

O(n)-algoritmi

Jos järjestettävässä taulukossa on kokonaislukuja kohtuullisen pieneltä alueelta, myös O(n)-algoritmi on mahdollinen. Ideana on laskea, kuinka monta kertaa kukin luku esiintyy taulukossa ja muodostaa tämän kirjanpidon perusteella lopullinen järjestetty taulukko.

Javan komento Arrays.sort

Tämän viikon aiheesta huolimatta kannattaa muistaa, että Javan valmis komento Arrays.sort on käytännössä aina paras valinta taulukon järjestämiseen. Ei siis ole syytä koodata itse järjestämisalgoritmia – paitsi laskaritehtävässä 3.