8. nädal

Lahendame ülesandeid listidega ja mõtleme sealjuures indeksite peale.

Ülesanne 1 Loendamine uuesti
Kui loendada on vaja mitme erineva väärtuse esinemist, siis mida teha? Abiks on list, kuhu kogutakse kõik loendurid. 
Listi indeksite ja loendatavate väärtuste vahel luuakse mingi seos. Lihtsamal juhul on indeks loendatav väärtus. Nii saab loendada edukalt täisarve. 
Keerulisemad olukorrad on Pythonis lahendatavad sõnastikuga (dictionary). Saab ka teha 2 listi - ühes loendatavad väärtused, teises vastavad loendurid.

Loendurite nullimiseks tuleb kõigepealt teha nullidest koosev list, mille elementide arv vastab loendatavale vahemikule. Selleks sobib Pythonis korrutamistehe: loendur = N * [0]

Ülesanne: genereeri juhuslike arvude generaatoriga palju arve (nt 100000 arvu) vahemikus 0 .. 100. Loenda arvud ja väljasta tabel arvude sagedustega. Et rohkem listidega sõbraks saada, võib arvud eelnevalt listi kirjutada ja seejärel uue
tsükli abil loendama hakata.

Ülesanne 2 Sorteerimine mullimeetodil
Mullimeetod (bubble sort) töötab järgmiselt: alustades 1. elemendist võrreldakse kahte kõrvuti asuvat elementi ja vahetatakse nad omavahel, kui väiksem on tagapool. Nii toimitakse järjest kõigi kõrvuti asuvate elementidega. Peale esimest korda listi lõppu jõudmist on kõige suurem arv listis viimane. Teised on aga suure tõenäosusega segamini.
Seega tuleb alustada uuesti algusest ja korrata sama tegevust. Mitu korda on sorteerimiseks vaja list läbi käia? Üle N korra (elementide arv) kindlasti
mitte. Tegelikult võib piisata ka vähemast. Andmed on sorteeritud, kui kogu listi läbimise ja paaride võrdlemise jooksul
ei ole vaja teha ühtegi vahetust. Kasuta seda korduste arvu määramiseks.
Sorteeritav list genereeri juhuslike arvude generaatoriga.
Tee programmist teine versioon, mis sorteeriks arvud mittekasvavasse järjekorda.

Ülesanne 3
Kuidas tuvastada, kas list on sorteeritud?
Tuleb hakata algusest peale kontrollima ja võrdlema kõrvuti asuvaid arve. Kui järgmine arv on väiksem kui eelmine, siis list ei ole sorteeritud.

Ülesanne 4
Sorteerime veel - seekord proovi läbi valikmeetod (selection sort).
Meetod töötab järgmiselt:
Alates esimesest elemendist leia üle kogu massiivi väikseim element, vaheta ta massiivis esimesele kohale (NB! esimesel kohal olnud element läheb vähima asemele!)
Korda tegevust alates 2., 3. jne elemendist, kuni jõuad välja massiivi lõppu.

Ülesanne 5
Kahendotsimine on efektiivne otsimismeetod, kuid sobilik siis, kui andmed on sorteeritud. Sorteeri list ja proovi seejärel teha kahendotsimist.
See toimub nii, et list poolitatakse, võrreldakse keskmist elementi otsitavaga ning otsustatakse, kummal poolel jätkata.
Kogu poolitamise töö toimub indeksite abil ja igal sammul on vaja teada, milline on järele jäänud vahemiku alguse ja lõpu indeksid. Kuidas nede abil leida keskmise elemendi indekit?

Ülesanne 6
Võtame taas ette üliõpilaste pikkused. Sorteeri üliõpilased pikkuse järgi mittekahanevasse järjekorda. Sorteerida saab pikkuse järgi, kuid nimede massiivis tuleb samuti teha vastavad ümbertõstmised. Otsusta ise, kumma eespool katsetatud meetodi sorteerimiseks valid. 
Kui asi selge, võid proovida järjestada üliõpilasi ka nime järgi tähestikulisse järjekorda.