4.2.6 Algoritmin
parantaminen
Kaikki
edelliset algoritmit ovat kompleksisuudeltaan normaalitapauksessa samanlaisia.
Tehtävä
4.6
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.7
QuickSortin
kompleksisuus
- Jos
algoritmin kompleksisuus on esimerkiksi 2n
2+n,
sanotaan että kompleksisuus on O(n
2),
eli usein kiinnostaa vain kompleksisuuden suurin "potenssi".
QuickSortin
keskimääräinen kompleksisuus on O(n log
2n).
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.8
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
