Ohjelmointi++ - 4.2.6 Algoritmin parantaminen

4.2.6 Algoritmin parantaminen

Tehtävä 4.13 Loppuminen erikoistapauksessa
Tehtävä 4.14 QuickSortin kompleksisuus
Tehtävä 4.15 Lisäys oikealle paikalleen vaiko lisäys loppuun ja lajittelu?

Kaikki edelliset algoritmit ovat kompleksisuudeltaan normaalitapauksessa samanlaisia.

Tehtävä 4.13 Loppuminen erikoistapauksessa

Mikä edellisistä algoritmeista loppuu nopeasti, mikäli kortit jo olivat järjestyksessä?

Ohjelman toimintaan saattamisen kannalta olisi riittävää löytää jokin toimiva algoritmi. Myöhemmin, mikäli ohjelman toiminta todetaan hitaaksi ko. algoritmin kohdalta, voidaan algoritmia yrittää tehostaa. Lajittelussa tehostus saattaisi olla vaikkapa QuickSort (mukana mm. C- kielen standardikirjastossa).

Tehtävä 4.14 QuickSortin kompleksisuus

Jos algoritmin kompleksisuus on esimerkiksi 2n²+n, sanotaan että kompleksisuus on O(n²), eli usein kiinnostaa vain kompleksisuuden suurin "potenssi". QuickSortin keskimääräinen kompleksisuus on O(n log₂n). On olemassa myös erikoistapauksissa toimivia lajitteluja, joissa kompleksisuus on O(n). Piirrä kuva jossa on Selection Sortin, QuickSortin ja lineaarisen lajittelun käyttämä "aika" piirrettynä lajiteltavien alkioiden (n=10,100,1000,10000,1000000) funktiona.

Tehtävä 4.15 Lisäys oikealle paikalleen vaiko lisäys loppuun ja lajittelu?

Tutki kumpiko on työmäärältään edullisempaa jos järjestettyyn taulukkoon tulee lisättäväksi suuri määrä uusia alkiota
1): lisätä alkio aina taulukkoon oikealle paikalleen
2): lisätä alkio aina taulukon loppuun ja kun kaikki alkiot on lisätty, niin lajitella taulukko