(N) Merkkijonon järjestäminen¶

Tavoite: Harjoittelen rekursion toteuttamista.

Ohjeita: Hae ohjelmakoodipohja: templates/02/string_sort/ -> student/02/string_sort/. Pohjassa on automaattitestausta varten määrittelyt RECURSIVE_FUNC_IOS ja RECURSIVE_FUNC_SORT. Niistä ei tarvitse välittää, eikä niille saa tehdä mitään.

Toteuta ohjelmakoodipohjaan kaksi funktiota: index_of_smallest ja sort. Näistä ensiksi mainittu palauttaa indeksin, josta löytyy merkkijonon pienin merkki, kun vertailu perustuu merkkien ASCII-koodijärjestykseen. Tämä on merkkien oletusjärjestys, jota käyttävät operaattorit <, >, <= ja >=. Toinen funktio järjestää merkkijonon merkit niiden ASCII-koodien mukaiseen järjestykseen kutsumalla ensiksi mainittua funktiota.

Koska tarkoituksena on kirjoittaa rekursiivisia funktioita, ohjelmassa ei sallita silmukkarakenteita (for tai while).

Halutessasi voit toteuttaa myös apufunktion swap(string& s, unsigned int ind1, unsigned int ind2), joka toimii samalla periaatteella kuin aikaisemmassa tehtävässä toteutettu swap-funktio, mutta tässä parametriksi annetaan merkkijono, jonka merkkejä vaihdetaan, sekä kaksi indeksiä, joiden sisältämät merkit vaihdetaan. (Tämä funktio ei ole rekursiivinen, eikä toistolauseitakaan tarvita.)

Esimerkkejä ohjelman toiminnasta:

Enter a string: 3746
Index of smallest character: 0
Sorted string: 3467

Enter a string: palindrome
Index of smallest character: 1
Sorted string: adeilmnopr

Vinkkejä tehtävän tekemiseen:

• Aloita miettiminen siitä, mikä on triviaalitapaus ja miten se kirjoitetaan ohjelmakoodiksi.

• Tämän jälkeen mieti, miten tämän ongelman voi jakaa pienemmäksi mutta samanmuotoiseksi osaongelmaksi.

• Voit olettaa, että pienin merkki löytyy merkkijonosta vain yhdestä indeksistä.

• Koska funktio index_of_smallest etsii indeksin, josta pienin merkki löytyy, niin todennäköisesti substr-funktiosta ei ole hyötyä, sillä sen kutsuminen muuttaisi alkuperäisiä indeksejä. Sen sijaan tarvitset todennäköisesti kaksi indeksiparametria: toinen kertoo, mitä merkkijonon indeksiä ollaan kulloinkin käsittelemässä, ja toinen taas kertoo siihen mennessä käsittellyistä indekseistä sen, jonka sisältämä merkki on pienin.

• Toteuttamalla pelkästään funktion index_of_smallest voit saada osapisteitä. Toisaalta sort-funktio ei vaadi kovinkaan monta koodiriviä, ainakaan jos toteutat swap-funktion. (Kolmekin suoritettavaa riviä riittää.)