* vertailu ja lajittelu
* algoritmin kompleksisuus
* alkion etsiminen joukosta Kun ohjelman suunnittelu on edennyt siihen pisteeseen, että tarvitaan yksityiskohtaisia algoritmeja, meneekin jo monella sormi suuhun.
Vaikeudet johtuvat taas liian hankalasta ajattelutavasta ja siitä, että algoritmi yritetään nähdä osana koko ohjelmaa. Tästä ajattelutavasta on luovuttava ja osattava määritellä tarvittava algoritmi omana kokonaisuutenaan, jota suunniteltaessa sitten unohdetaan kaikki muu.
Voit tietysti antaa ohjeet myös muodossa "Tule osoitteeseen Ohjelmoijankuja 17 B 5". Tämäkin on varsin hyvä algoritmi. Kaverin vain oletetaan nyt osaavan enemmän. Kaverin oletetaan osaavan etsiä katuluettelosta kadun paikka ja keksivän itse menetelmän tulla asemalta sinne.
Toisaalta kaverisi saattaa hypätä taksiin ja sanoa kuskille osoitteen. Tämä on hyvä ja helppo algoritmi, mutta ehkä liian kallis opintovelkaiselle opiskelijalle. Mikäli algoritmia tarvitaan useasti, voidaan sitä myöhemmin parantaa tyyliin:
- kävele asemalta sinne ja sinne - hyppää bussiin se ja se - jneTarkennettu algoritmi voisi olla myös seuraavanlainen:
Valitse seuraavista: 1. Kello 7- 20: - kävele kirkkopuistoon - nouse bussiin no 3 joka lähtee 15 yli ja 15 vaille 2. Sinulla on rahaa tai saat kimpan: - ota taksi 3. Ei rahaa tai haluat ulkoilla: - käveleEdellä eri kohdat eivät ole toisiaan poissulkevia. Kello voi olla 9 ja rahaakin voi olla, mutta siitä huolimatta halutaan kävellä. Hyvässä algoritmissa ei saa olla tällaisia epätäsmällisyyksiä, vaan ohjelmoijan tulee etukäteen jo päättää mitä missäkin tapauksessa tehdään. Esimerkiksi:
1. Jos haluat ulkoilla, niin - kävele. 2. Muuten jos kello 7- 20: - kävele kirkkopuistoon - nouse bussiin no 3 joka lähtee 15 yli ja 15 vaille 3. Muuten jos sinulla on rahaa tai saat kimpan: - ota taksi 4. Muuten - käveleTässäkin algoritmissa jää vielä kaverillekin tehtävää: Miten kävellään? Miten astutaan bussiin jne..
No tätä ei kaverille ehkä enää selostetakaan. Lapsille nämä asiat on aikanaan opetettu ja myöhemmin ne kuitataan yhdellä tai kahdella sanalla. Sama pätee ohjelmoinnissakin. Kerran tehtyä ei joka kerran pureksita uudelleen (vrt. aliohjelma)!
Verrataanpa erilaisia nimiä:
A: Kassinen Katto B: Ankka AkuB on ensin aakkosissa. Miksi? Koska B:n ensimmäinen kirjain (A) on ennen nimen A ensimmäistä kirjainta (K).
A: Kassinen Katto B: Karhukopla 701107Nytkin B on ensin. Siis miten vertaamme kahta nimeä?
Vertaamme nimiä merkki kerrallaan kunnes vastaan tulee eri- suuret kirjaimet. Kumpi erisuurista kirjaimista on aakko- sissa ennen, määrää sen kumpi nimistä on aakkosissa ennen.Siinä meillä on algoritmi joka on varsin selvä. Jos algoritmi haluttaisiin vielä kirjoittaa "lausekieliseen"- muotoon, niin se olisi suurinpiirtein seuraavanlainen:
1. siirry kummankin nimen ensimmäiseen kirjaimeen 2. jos kummankin nimen viimeinen merkki on ohitettu, niin nimet ovat samat 3. jos toisessa nimessä viimeinen merkki on ohitettu, niin se on ennenTähän vielä pieni "viilaus enemmän strukturoidummaksi", niin meillä olisikin valmis (ali)ohjelma nimien vertaamiseksi.
aakkosissa 4. verrataan vuorossa olevia kirjaimia kummastakin nimestä - jos samat, niin siirrytään seuraaviin kirjaimiin ja jatketaan kohdasta
2. - jos erisuuret, niin se ensin aakkosissa, jonka kirjain on ensin
Siis kirjoita aina ensin sanallinen kuvaava kuvaus algoritmista ja vasta sitten sen yksityiskohtainen "lausekielinen" versio!
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.
Bubble sort:
Vertaa aina kahta peräkkäistä korttia keskenään. Mikäli ne ovat väärässä järjestyksessä, vaihda ne keskenään. Kun koko pakka on käyty lävitse, aloita alusta ja jatka kunnes yhtään kertaa ei tarvitse vaihtaa peräkkäisiä kortteja.
Mikäli laput järjestetään nimen mukaan, sanotaan nimen olevan lajitteluavaimena. Lajitteluavaimeksi voitaisiin valita myös osoite tai puhelinnumero. Mikäli kahdella henkilöllä olisi sama nimi, voitaisiin nämä kaksi järjestää osoitteen perusteella. Tällöin lajitteluavain muodostuisi merkkijonosta johon olisi yhdistettynä nimi ja osoite.
Entä jos kädessä olevien korttien järjestystä ei haluta muuttaa? Voisimme menetellä esimerkiksi seuraavasti (alkuarvaus ja arvauksen korjaaminen):
0. vedä kädessä olevan pakan ylin kortti hieman esille ota ensimmäinen kortti tutkittavaksi 1. vertaa tutkittavaa korttia ja esiinvedettyä korttia 2. mikäli tutkittava on pienempi, vedä se esiin ja työnnä edellinen takaisin 3. siirry tutkimaan seuraavaa korttia ja jatka kohdasta 1. kunnes olet tutkinut koko pakan
0. laita uusi kortti päällimmäiseksi lajiteltuun kasaan 1. vertaa uutta ja seuraavaa 2. mikäli väärässä järjestyksessä, niin vaihda ne keskenään ja jatka kohdasta 1.
Nimen hakeminen ei taas poikenne kortin etsimisestä järjestetystä korttipakasta vai mitä?
Ota seuraava kortti. Mikäli etsittävä niin lopeta, muuten ota taas seuraava.Algoritmi on OK 13 kortille, mutta kokeilepa Äystön etsimistä puhelinluettelosta tällä algoritmilla (muista lukea jokainen nimi ennen Äystöä)!
1. laita pakka pöydälle kuvapuolet ylöspäin 2. laita pakka puoliksi 3. laita molemmat pakat pöydälle kuvapuolet ylöspäin 4. kummassako kasassa etsittävä on? 5. heitä se pakka pois jossa etsittävä ei ole 6. jos etsittävä ei päällimmäinen, niin jatka kohdasta 1.Vaikuttaa tyhmältä 13 kortille, mutta kokeilepa 1000 kortilla! Tai kokeile nyt etsiä ÄYSTÖÄ puhelinluettelosta tällä algoritmilla.
Algoritmit kannattaa testata huolellisesti jossain tutussa ympäristössä. Hyvin moni ohjelmointiongelma vektoreiden (=taulukko, =kasa kortteja, =ruutupaperi, =sivunumeroitu kirja jne...) kanssa samaistuu johonkin jokapäiväiseen ilmiöön. Kuten etsiminen puhelinluettelosta, korttipakan järjestäminen jne. Yritä etsiä näitä yhteyksiä ja kokeile ensin ratkaista ongelma tällä tavoin. Siirrä ratkaisu sitten "lausekielelle" ja lopulta ohjelmointikielelle.
Äläkä yritä liikaa, vaan jaa aina ongelma pienempiin osiin, kunnes tulee vastaan sen kokoisia osaongelmia, jotka osataan ratkaista! Tällaista osaongelman ratkaisijaa sanotaan ohjelmointikielessä aliohjelmaksi.
Kun osaongelma on ratkaistu, unohda se miten sen ratkaisija toimii ja käsittele ratkaisijaa vain yhtenä yksinkertaisena toimenpiteenä (vrt. aikaisempi kävelyesimerkki). Tämä on myös eräs ohjelmoinnin "vaikeus". Kirjoittaja haluaa nähdä kaikkien osien toiminnan yhtäaikaisesti. Tämä on kuitenkin mahdotonta. Siis kun jokin osa tekee hommansa, niin tehköön se sen miten tahansa.
Huono on johtaja joka kyttää koko ajan alaisiaan, eikä luota siihen, että nämä tekevät heille annetun tehtävän. Tässä mielessä ohjelmointia voisi verrata yrityksen johtamiseen: Johtaja jakaa koko yrityksen pyörittämisessä tarvittavia tehtäviä alaisilleen (aliohjelmille). Nämä saattavat edelleen jakaa joitakin osatehtäviä omille alaisilleen (aliohjelma kutsuu toista aliohjelmaa) jne. Johtaja (=ohjelmoija ja pääohjelma) kokoaa alaisten tekemän työn toimivaksi kokonaisuudeksi ja firma tuottaa.