Eräs tärkeä algoritmien kirjoittamisen vaihe on yleistäminen. Tällöin valmiiksi tehdystä algoritmista pyritään paikantamaan kaikki alunperin annetusta tehtävästä riippuvat tekijät, ja pohditaan voitaisiinko ne kenties kokonaan poistaa tai korvata joillakin yleisemmillä tekijöillä.
Tarkastele edellä esitettyä algoritmia kahvin keittämiseksi ja luo vastaava algoritmi teen keittämiseksi. Vertaile algoritmeja: mitä samaa ja mitä eroa niissä on? Onko mahdollista luoda algoritmi, joka yksiselitteisesti selviäisi sekä kahvin että teen keitosta? Onko mahdollista luoda algoritmi, joka saman tien selviytyisi maitokaakosta ja rommitotista?
Esimerkkinä yleishyödyllisestä algoritmista olkoon algoritmi, jolla voidaan lajitella pakka pelikortteja. Lajittelu voidaan tehdä hyvin monella eri tavalla, mutta otetaan esimerkin lajittelutavaksi valintalajittelu:
Valintalajittelu pakalle pelikortteja:
1. Etsitään pakan pienin kortti:
1.1. Otetaan pakan päällimmäinen kortti ja laitetaan se erilleen.
1.2. Käydään loppupakka läpi kortti kerrallaan.
1.3. Jos käsiteltävänä oleva kortti on pienempi kuin erilleen
otettu kortti, vaihdetaan niiden paikat.
1.4. Kun koko pakka on käyty läpi, on erillään oleva kortti pienin.
2. Siirretään pienin kortti järjestettyjen pinoon.
3. Jatketaan alusta kunnes pakassa ei ole enää kortteja jäljellä.
Näin lajitellut kortit tulevat nousevaan järjestykseen eli pienin kortti on alimmaisena ja suurin kortti päällimmäisenä.
Miten muuttaisit edellistä lajittelualgoritmia, jos lopputuloksena oleva pakka haluttaisiin olevan laskevassa järjestyksessä eli pienin kortti päällimmäisenä?
Algoritmin tavoitteena on olla yksikäsitteinen kokonaisuus, joka toimii aukottomasti vallitsevista olosuhteista huolimatta. Esimerkiksi pakan lajittelun tulee toimia myös silloin, kun jokin korteista puuttuu tai kortit ovatkin valmiiksi järjestyksessä.
Algoritmien kirjoittaminen johtaa usein annetun ongelman asteittaiseen ratkaisuun tai asteittain tarkentuvaan ratkaisustrategiaan. Valintalajittelun tapauksessa algoritmin hahmottelu paljasti lisäkehittelyn tarpeen, sillä algoritmissa vertailtiin eri korttien suuruutta. Millä kriteerillä päätetään, että kortti on pienempi kuin jokin toinen kortti (esim. onko ässä suurin vai pienin)? Kuinka menetellään, jos samanarvoisia kortteja on useita (esim. pata-, hertta-, ruutu- ja ristiviitonen)?
Kun tarkastellaan edellä esitettyä valintalajittelun algoritmia, havaitaan, että se toimii täsmälleen samoin postikorttien, kirjeiden, rahojen, yms. lajitteluun. Näin ollen huomataan, että esitetty algoritmi voidaan irrottaa alkuperäisestä kehitysympäristöstä eli voidaan unohtaa, että kyse oli alunperin pelikorteista. Tarvitseeko lajittelun onnistumiseksi lajiteltavien olla pinossa, vai onnistuuko lajittelu, jos lajiteltavat ovat levällään esim. lattialla? Onko lajittelun alussa pakko ottaa pinon päällimmäinen? Näin alkaa muodostua yleistetty valintalajittelu:
Yleistetty valintalajittelu:
1. Etsitään joukon pienin alkio:
1.1. Otetaan joukosta erilleen yksi alkio.
1.2. Käydään loppuosa joukosta läpi alkio kerrallaan.
1.3. Jos käsiteltävänä oleva alkio on pienempi kuin erilleen
otettu alkio, vaihdetaan niiden paikat.
1.4. Kun koko joukko on käyty läpi, on erillään oleva alkio pienin.
2. Siirretään pienin alkio järjestettyjen joukkoon.
3. Jatketaan alusta kunnes lajiteltavien joukossa ei ole enää
alkioita jäljellä.
Onko lopputulos laskevassa vai nousevassa järjestyksessä? Kokeile lajittelua käytännössä.
Kyseinen algoritmi on kehityksensä suhteen alkutekijöissään, sillä sen askeleet sisältävät vielä useita määrittelemättömiä toimenpiteitä.
Tarkenna esitettyä yleistettyä valintalajittelua kirjoittamalla alialgoritmit alkioiden vertaamiselle ja alkioiden paikan vaihtamiselle.
Kuinka kaksi kellonaikaa vähennetään toisistaan? Kuinka kellonaikaan lisätään haluttu minuuttimäärä? Esitä algoritmit.