Kakskümmend viis: sorteerimine

Eelmisel korral vaatasime tunni lõpus kui aega üle jäi üht ülesannet, mis osutus ootamatult keeruliseks.
Tegu oli sorteerimisega. Nagu ma näitasin, siis programmeerimiskeeltel on enamasti kaasas enda sorteerimisvahendid:

sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

Ehk siis kui meetodile sorted parameetriks anda mõni nimekiri numbritest, siis sorted annab vastu väiksemast suuremale järjekorras samad numbrid.
Samuti töötab sorteerimine teksti ja sõnadega, proovige näiteks IDLE’s:

sorted("See on test tekst mille kirjutas Adalbert".split())

.split() lahutab teksti (string, jutumärkides) tühikute alusel sõnade järjekorraks.
sorted sorteerib sõnad vastavalt tähestiku kooditabelile.

Tähelepanu: arvestab ka suurtähti ja see ei ole sama mis tähestiku järjekord!
Näiteks: “AAA ABB abb acc aaa ccc aBB abB BBB Ccc” sorteeritakse järjekorda “AAA ABB abb acc aaa ccc aBB abB BBB Ccc” – esmalt suurtähtedega algavad sõnad, siis väiketähtedega algavad. Põhjuseks see, et kooditabelis on suurtähed koos ja väiketähed koos, mitte läbisegi. Lisaks on järjekorras ka erisusi, enamus sellest küll kattub, aga täpitähed asuvad tähtede kooditabelites erinevas kohas ja seepärast ei pruugi nad sattuda samasse kohta kus tähestiku järgse sorteerimise korral nad olema peaks isegi siis kui tähtede suuruses erinevusi pole.

Näiteks programm:

#!/usr/bin/python
# -*- coding: utf-8 -*-
sorteeritud = sorted(u"äää üüü hädaldas Adalbert taga õues öösel žurnalistika Šurikut parajat juurikat".split())
for tekst in sorteeritud:
print tekst,

Programmi vastus:
Adalbert hädaldas juurikat parajat taga äää õues öösel üüü Šurikut žurnalistika
Eesti tähestik koos võõrtähtedega:
ABCDEFGHIJKLMNOPQRSŠZŽTUVWÕÄÖÜXY

Õ täht on kooditabelis peale Ä tähte ja enne Ö tähte ning ka Š ja Ž jäävad eesti tähestiku alusel valesse kohta.

Et sorteerimist parandada on Pythoni sorteerimisel päris head lisavõimalused, nimelt saab ette anda millise funktsiooni alusel sorteeritakse. Näiteks, et suur- ja väiketähti mitte eristada võib teha nii:

sorteeritud = sorted("AAA ABB abb aöc äaa ccc aBõ abB BBB Ccc".split(), key=str.lower)

key=str.lower tähendab, et enne sorteerimist tehakse mõtteliselt sõnad väiketähtedesse tekstitüübi str meetodiga lower.

Võib ka kasutada tagurpidi järjestamist, siis tuleb lisada parameetritesse, key=str.lower järele või asemele reverse=1

Python on lihtsalt kasutatav ja võimas keel, kuid mõned asjad käivad siin teistmoodi kui enamikus harjunumates vanemates keeltes. Olen vast juba maininud, et kui Pythonis võib järjekorras olla läbisegi numbreid ja teksti või muid objekte, siis enamikus teistes keeltes selline asi lubatud ei ole. Eelmisel tunnil ise sorteerida proovides mängis ka see väikese vingerpussi.

Näiteks võib Python sorteerida ka sedasi:
sorted((1, 3, "adalbert", "karu", 7, -5))

Vastuseks on: -5, 1, 3, 7, adalbert, karu

Mida siis ikkagi teha, et ise sorteerida?

Kõige lihtsam on käia nimekiri järjest läbi – esmalt leida kõige väiksem liige ja lisada see uude jadasse, siis sellele järgnev väike liige ja nii edasi kuni koos on kõik jada liikmed uues jadas (valikuga sorteerimine). See ei ole kindlasti matemaatiliselt ja praktiliselt kõige kiirem ja efektiivsem viis sorteerida. No kujutame ette kuidas õpilaste pikkuse järgi sorteerimine käib kehalise kasvatuse tunnis või veelparem spordilaagris, kus õpilased pole varem üksteisega tuttavad ega tea kui pikk keegi on umbkaudugi. Parem on ilmselt alguses paaridel omavahel võrrelda üksteist, siis paare omavahel ja nii edasi – paralleelselt. Sorteerimise kohta on hulgem omaette matemaatilisi teooriaid, ingliskeelses Wikipedias on väga põhjalik artikkel. Eesti keeles on väheseid selgitatud, kuid vaadake kindlasti mullsorteerimist, see vastabki ilmselt kõige paremini õpilaste pikkusepõhisele ise sorteerimisele. Võib uurida ka vahelepanemisega sorteerimist.

Ise sorteerimise ülesande üks võimalik versioon eelmise korra posti juurde:

#!/usr/bin/python
# -*- coding: utf-8 -*-
fail=open("KORD.SIS", "r")
numbrid = []
vastus = []
number=int(fail.readline()) #lugema veel numbri
tekstinumbrid=(fail.readline()).split() #lugema mitu numbrit realt tekstina
numbrid = []
for tekstn in tekstinumbrid:
    numbrid.append(int(tekstn))
while (len(numbrid)>0) :
    vaike = 100000
    for n in numbrid :
       if (vaike > n) :
          vaike=n
    vastus.append(vaike)
    numbrid.remove(vaike)
for i in vastus:
    print i,

Viimaks üks keerulisem objektipõhine näide:

#!/usr/bin/python
# -*- coding: utf-8 -*-
class Opilane:
    def __init__(self, nimi, hinne, vanus):
       self.nimi = nimi
       self.hinne = hinne
       self.vanus = vanus
   def __repr__(self):
      return repr((self.nimi, self.hinne, self.vanus))

   

Opilased = [
   Opilane('jaan', 'A', 15),
   Opilane('mari', 'B', 12),
   Opilane('art', 'B', 10),
]
print Opilased
print "nüüd sorteerime!"
print sorted(Opilased, key=lambda Opilane: Opilane.nimi)

Rubriigid: Uncategorized. Salvesta püsiviide oma järjehoidjasse.

Lisa kommentaar