Aseta vastauksesi tiedostoihin pikalaj.h ja pikalaj.c.

Tämä tehtävä on jatkoa kolmijako-tehtävälle, mutta tehtävän voi periaatteessa tehdä, vaikkei olisikaan vielä tehnyt kyseistä tehtävää. Kolmijakoa koskeva tehtävänanto kuitenkin oletetaan tunnetuksi.

Ns. pikalajittelu ("quicksort") on eräs käytännössä nopea ja yleisesti käytetty lajittelualgoritmi. Esimerkiksi niin C-kielen standardikirjasto kuin mm. Javan Arrays-luokka sisältävät pikalajitteluun pohjautuvat lajittelualgoritmit. Perinteisestä pikalajittelusta hieman poikkeavan, kolmijakoon pohjautuvan pikalajittelun (jota mm. Oraclen Java 8 käyttää) toimintaidea on varsin yksinkertainen ja voidaan esittää seuraavanlaisella pseudokoodilla:

    Pikalajittele(alku, loppu, t): taulukon t indeksien alku...loppu alkioiden lajittelu.
        Jos alku >= loppu, palaa tekemättä mitään.
        Valitse jotkut indeksit a ja b väliltä alku...loppu. Aseta jako1 = min{t[a], t[b]} ja jako2 = max{t[a], t[b]}.
            ANSI C ei tarjoa minimi/maksimifunktioita, joten laske nuo edellä mainitut minimi ja maksimi itse.
            Huomio: valittujen indeksien a ja b pitää olla keskenään erisuuret. Eli varmista, ettet valitse vahingossa kahta keskenään samaa indeksiä!
        Järjestä välin alku...loppu alkiot arvojen jako1 ja jako2 suhteen siten, että:
            Alkiot t[a] ja t[b] eli jako1 ja jako2 siirtyvät taulukossa lopullisen lajitellun järjestyksen mukaisiin kohtiinsa. Olkoon näiden paikkojen indeksit talletettu muuttujiin x ja y.
            Muut alkiot ovat sellaisessa osittaisessa järjestyksessä, että:
                t[i] < jako1, jos i < x.
                jako1 <= t[i] < jako2, jos x < i < y.
                t[i] >= jako2, jos i > y.
            Huomio: tämän askeleen 3 tekemä toimenpide on lähes identtinen sen kanssa, mitä kolmijakoa koskevassa tehtävässä toteutettu funktio kolmijako tekee. Esimerkiksi indeksit a ja b vastaavat parametreja vipu1 ja vipu2 ja muuttujiin x ja y talletettavat indeksit vastaavat funktion kolmijako palauttamia arvoja pienet1 ja pienet2.
        Toista sama toimenpide rekursiivisesti niihin kolmeen toistaiseksi vasta osittain järjestettyihin osiin, joiden rajat indeksit x ja y määrittävät:
            Vasen osa: Pikalajittele(alku, x-1, t).
            Keskiosa: Pikalajittele(x+1, y-1, t).
            Oikea puoli: Pikalajittele(y+1, loppu, t).

Toteuta yllä annettua pseudokoodia vastaava funktio void pikalajittele(int alku, int loppu, int t[]), joka lajittelee saamansa int-taulukon käyttäen kolmijakoon perustuvaa pikalajittelualgoritmia. Koska parametrit alku ja loppu määrittävät sen osataulukon alku- ja loppuindeksit, joka taulukosta t lajitellaan, tapahtuisi esimerkiksi koko-alkioisen taulukon t kaikkien alkioiden lajittelu kutsulla pikalajittele(0, koko-1, t).
Ohjeita toteutukseen

Pseudokoodin askel 3 pitää toteuttaa kutsumalla kolmijakoa koskevassa tehtävänannossa kuvattua funktiota kolmijako, jonka toteutuksen oletetaan löytyvän erillisistä tiedostoista kolmijako.h/kolmijako.c. WETO tarjoaa nämä tiedostot valmiina, joten tehtävän ratkaisu on sinänsä mahdollista, vaikket olisikaan vielä ehtinyt toteuttamaan kyseistä funktiota. Omalla koneella testaus ei toki onnistu ellet ensin toteuta myös funktiota kolmijako. Muista joka tapauksessa sisällyttää otsaketiedosto "kolmijako.h" tiedostoon pikalaj.c, jotta voit kutsua funktiota kolmijako funktiosta pikalajittele.

Yksi erityishuomio koskee sitä, että askeleessa 3 tehtävä jako-operaatio koskee taulukon t indeksien alku...loppu muodostamaa osataulukkoa eikä taulukkoa kokonaisuudessaan. Sen sijaan kolmijakoa koskevan tehtävän funktio kolmijako näyttäisi päällisin puolin haluavan parametreikseen "kokonaisen" taulukon sekä sen koon. Tämä ei kuitenkaan muodostu ongelmaksi, koska C-kielessä taulukon käsittely pohjautuu ainoastaan seuraaviin kahteen asiaan: (1) osoitin ensimmäiseen alkioon sekä (2) tieto alkioiden lukumäärästä. Näin ollen pelkästään indekseihin alku...loppu rajoittuva jako-operaatio saadaan aikaan antamalla funktiolle kolmijako taulukoksi osoitin alkion t[alku] kohdalle (käytä osoitinaritmetiikkaa tai osoiteoperaattoria) ja välittämällä taulukon kooksi kyseisen osataulukon koko (eli intervallin alku...loppu pituus). Tällöin funktion kolmijako näkökulmasta kyseessä on int-taulukko, jonka ensimmäinen alkio on t[alku] ja viimeinen alkio t[loppu].

Edellä mainitun osataulukkoon kohdistuvan jako-operaation yhteydessä pitää lisäksi muistaa huomioida seuraavat kaksi asiaa:

    Kun funktiolle kolmijako välitetään pseudokoodin askeleessa 2 valitut jakoindeksit a ja b, ne pitää ennen funktiokutsua vielä muuntaa parametrina välitetyn osataulukon alku...loppu indekseiksi: a vastaa indeksiä a-alku ja b indeksiä b-alku.
    Funktion kolmijako palauttamat arvot pienet1 ja pienet2 (pseudokoodissa indeksit x ja y) pitää vastaaavalla tavalla muuntaa takaisinpäin: osataulukon indekseistä koko taulukon indekseiksi.

Tässä tehtävässä tarvitsee loppujen lopuksi tuottaa varsin vähän uutta koodia: esimerkiksi WETOn käyttämän esimerkkiratkaisun tiedostot pikalaj.h ja pikalaj.c sisältävät yhteensä noin 20 riviä.