previous next Up Title Contents Index

4.2.3 Numeroiden järjestäminen


Näin ollen on aivan yksi lysti opettelemmeko järjestämään nimiä vai numeroita. Siksi paneudummekin seuraavassa numeroiden järjestämiseen. Kuulostaako vaikealta?

Otapa käteesi korttipakka ja ota sieltä esiin vaikkapa vain kaikki padat. Nyt sinulla on joukko "numeroita" (A=14, K=13, Q=12, J=11), yhteensä 13 kappaletta. Sekoita kortit! Yritä järjestää kortit suuruusjärjestykseen siten, ettet tarvitse pöytätilaa kuin yhden kortin verran, loput kortit pidät kädessäsi.

Millaisen algoritmin saat? Ehkäpä seuraavan (insertion sort):

	Pöydällä on lajiteltujen kasa.  Aluksi tietysti tyhjä.  Ota
	kädestäsi seuraava kortti ja laita pöydällä olevaan kasaan 
	omalle paikalleen.  Jatka kunnes kädessä ei enää kortteja. 
"Lausekielisenä":
	1. ota kädessä olevan kasan päällimmäinen kortti
	2. sijoita se pöydällä olevaan kasaan paikalleen
	3. mikäli kortteja vielä jäljellä, niin jatka kohdasta 1. 
Algoritmisi voi olla myös seuraava (selection sort):
	Etsitään aina pienin kortti ja laitetaan se pöydälle olevan 
	kasan päällimmäiseksi.  Jatketaan kunnes kädessä olevat 
	kortit on loppu. 
Eli "lausekielisenä":
	1.  etsi kädessäsi olevista korteista pienin
	2.  laita se pöydällä olevan pinon päällimmäiseksi
	3.  mikäli vielä kortteja jäljellä, niin jatka kohdasta 1. 

Tehtävä 4.9 Muita lajittelualgoritmeja

Mitä muita mahdollisia "lajittelumenetelmiä" keksit?
Siinä eräitä ratkaisuja tähän "hirveän vaikeaan" ongelmaan. Ratkaisuissa on tiettyjä huonoja puolia, mutta ne ovat todella yksinkertaisia ja jokaisen itse keksittävissä.

Tehtävä 4.10 Algoritmin kompleksisuus

Mikäli kahden kortin vertaaminen lasketaan yhdeksi "operaatioksi", niin kuinka monta "operaatiota" joudumme tekemään, jotta pakka on lajiteltu?
Edellisen tehtävän vastausta sanotaan algoritmin kompleksisuudeksi.

Tehtävä 4.11 Lajittelujärjestys

Edellinen algoritmi (selection sort) toimi siten, että kortit jäivät pöydälle suurin päällimmäiseksi. Miten algoritmia pitää muuttaa, jotta pienin saataisiin päällimmäiseksi?
Ei siis ole suurtakaan väliä pitääkö lajitella nouseva vai laskeva järjestys!


previous next Up Title Contents Index