Close menu
Close menu

Tunnistaudu

Kirjaudu

Etkö ole vielä jäsen?

Liity jäseneksi

5.2 Lajittelu

Yksi tunnetuimmista tietojenkäsittelyyn liittyvistä ongelmista on (listan) alkioiden lajittelu. Lajittelussa listan alkiot voidaan järjestää joko pienimmästä suurimpaan tai suurimmasta pienimpään. Lajittelualgoritmeja tunnetaan kymmeniä erilaisia.

Kuplalajittelun perusidea on yksinkertainen. Listaa käydään useita kertoja läpi alusta loppuun, ja aina kun kaksi vierekkäistä alkiota ovat toisiinsa nähden väärillä paikoilla, vaihdetaan niiden paikkoja. Tätä toistetaan kunnes lista on saatu järjestykseen.
Slide12.PNG
Seuraavassa esimerkissä lajitellaan lista, jonka alkiot ovat 3, 1, 5, 6, 2, 4, 7, 8, suuruusjärjestykseen.
Slide13.PNG
Tarkastellaan seuraavaksi kuplalajittelun toteutusta.

Funktio kuplalajittele saa argumenttina listan lista kokonaislukuja. Kuplalajittele-funktio kutsuu funktiota lajittelukierros ja saatu tulos sijoitetaan listaan lista2. Mikäli lista2 ja lista ovat samat, ei lajittelukierroksella tullut muutoksia, ja lista on lajiteltu. Muussa tapauksessa kutsutaan uudestaan kuplalajittele-funktiota argumentilla lista2.
Slide14.PNG
Lajittelukierros-funktio käy rekursiivisesti listan läpi alusta loppuun, ja mikäli alkiot first ja second ovat keskenään väärässä järjestyksessä, vaihdetaan niiden paikkoja.
Slide15.PNG
Kuplalajittelun toteutus oli yksinkertainen, mutta algoritmina se ei ole kovinkaan tehokas. Erilaisiin lajittelualgoritmeihin voi tutustua esimerkiksi Wikipedian Lajittelualgoritmi-artikkelin kautta.

Tehtäväsarja 1: Kuplalajittelu
5.3 Ahneet algoritmit