Ylös Edellinen Seuraava Otsikkosivu Hakemisto Sisällys

22.3 Lajittelu

Lajittelun vaatimia algoritmeja olemme käsitelleet jo aikaisemmin. Mikä tahansa aikaisemmin mainituista algoritmeista olisi helppo soveltaa jäsentaulukkoon. Kuitenkin lähes kaikki oppimamme algoritmit olivat kompleksisuudeltaan O(n 2). Jos jäsenmäärä kasvaa paljon yli sadan, tarkoittaa tämä suhteellisen hidasta lajittelua.

C- kielen standardikirjasto stdlib.h tarjoaa valmiin QuickSort lajittelualiohjelman qsort, jonka kompleksisuus on O(n log n). Miten lajitteluohjelma voidaan tehdä yleiskäyttöiseksi? Idea on siinä, että lajiteltiin mitä aineistoa tahansa, niin lähes ainoa aineistosta riippuva seikka on se, miten päätetään kahdesta alkiosta kumpiko on toistaan suurempi vai ovatko ne samoja.

Siis alkioiden vertailun suorittava aliohjelma kirjoitetaan itse. Sitten tämän aliohjelman osoite viedään qsort aliohjelmalle, jolloin tarvittaessa qsort kutsuu tätä vertailijaa.


Ylös Edellinen Seuraava Otsikkosivu Hakemisto Sisällys