Ks. Ohjelmointi++-monisteen luku 4 sekä Jori Mäntysalon kompleksisuusteksti (hyvä tietää -osastoa)
- jaetaan tehtävä osiin
- hajoita ja hallitse: merge sort
------
1. Etsi pienin
2. Laita se lajiteltujen kasaan
3. Etsitään jäljelle jääneistä pienin
4. Laita se alimmaiseksi laj. kasaan
5. Etsi taas pienin
Selection sort
1. Etsitään pienin jäljelläolevista
2. Laitetaan se valmiiden pinon alimmaiseksi
3. Jos jäljellä ei ole mitään, lopetetaan.
4. Jatketaan kohdasta 1.
Insertion sort
1. Ota pinon päällimmäinen
2. Laita se paikalleen valmiiden pinoon
3. Jos jäljellä ei ole mitään, lopetetaan.
4. Jatketaan kohdasta 1.
0. vedä kädessä olevan pakan ylin kortti hieman esille
ota ensimmäinen kortti tutkittavaksi
1. vertaa tutkittavaa korttia ja esiinvedettyä korttia
2. mikäli tutkittava on pienempi, vedä se esiin ja työnnä
edellinen takaisin
3. siirry tutkimaan seuraavaa korttia ja jatka kohdasta 1.
kunnes olet tutkinut koko pakan; tällöin pienin
on se, joka on esillä
(invariantti)
digit search
1. Etsi se alue, josta löytyy kaikki ne, joilla on sama
ensimmäinen kirjain kuin etsittävällä
2. sama juttu: etsitään tuosta alueesta ne, joilla on
sama toinen kirjain kuin etsittävällä
3. ...
binary search eli puolitushaku
1. Jos aineistossa on vain yksi alkio, ...
2. Jaa materiaali kahteen yhtäsuureen osaan.
3. Katso, kummassa haettava on; heitä metsään se,
jossa se ei ole
4. Hae etsittävää nyt tästä jäljelläolevasta puolikkaasta
Algoritmin kompleksisuus
- kuinka se algoritmi käyttäytyy kun aineistoa kasvatetaan
- luolamiehen järjestäminen on hyvin kompleksista
- merge sort vähemmän kompleksista
- etsi pienin: pahimman tapauksen kompleksisuus = 3n eli O(n)
- bogosort: keskimääräinen kompleksisuus = n! eli O(n!) (onko?)
- puolitushaku: 2 * log_2 n eli O(log n)
Viimeksi muutettu: ke 4 heinäkuu 2001 15:09:32
Antti-Juhani Kaijanaho <gaia@iki.fi>
Perustuu osittain Vesa Lappalaisen ja Kari Kärkkäisen tekemiin
kurssisivustoihin ja teksteihin.