RAČUNALNIŠ TVO Klasični algoritmi za urejanje v bločnem programiranju Igor Pesek -> V prvi številki letošnjega Preseka smo predstavili program Blockly Games [?], s katerim lahko s pomočjo iger napravite prve korake v programiranje. V današnjem prispevku bomo predstavili spletni program Blockly [?], ki omogoča programiranje v vizualnem okolju s pomočjo blokov. Spletni naslov programa najdete na koncu prispevka med viri. Blockly nima v naprej pripravljenih nalog, kot je to bilo narejeno v Blockly Games, zato bomo delo v okolju Blockly predstavili s pomočjo algoritmov za urejanje. Priprava seznama za urejanje Preden se lotimo algoritmov urejanja, potrebujemo seznam naključno izbranih števil, ki jih bomo kasneje uredili. Postopek priprave seznama bomo uporabili tudi za razlago okolja Blockly. Delovno okolje Blockly je prikazano na sliki 1 in je razdeljeno na tri področja. Prvo, označeno s številko 1, je območje, kjer programiramo oz. sestavljamo programe. Območje 2 vsebuje vse bloke, ki jih lahko pri programiranju uporabimo. Bloki so razvrščeni v kategorije po njihovi namembnosti. Ko kakšen blok potrebujemo, ga povlečemo na območje 1. Na območju 3 pa so zavihki, ki prikažejo kodo izbranega programskega jezika; ta je ekvivalentna kodi našega bloč-nega programa. Skrajno desno je tudi rdeč gumb, ki začne izvajanje našega programa. Ce niste reševali Bločkly games, si lahko za delo s programom Bločkly pomagate s priročnikom, ki ga najdete na https ://gi thub. com/googl e/bl ockl y/wi ki [?]. Da ustvarimo seznam desetih naključnih števil, moramo najprej ustvariti spremenljivko, ki na začetku predstavlja prazen seznam. Sledi zanka, ki se izvede desetkrat in v vsaki ponovitvi naključno izbere število iz določenega obsega (v našem primeru med 1 in 100). Seznam smo s tem ustvarili, preostane nam še samo klič funkčije za urejanje. Celoten program je prikazan na sliki 2. SLIKA 1. Delovno okolje programa Blockly 24 PRESEK 44 (2016/2017) 3 27 RACUNALNIŠ TVO Preden nadaljujemo, bomo predstavili še funkcijo za zamenjavo dveh elementov v seznamu, saj jo pri urejanju večkrat potrebujemo in je zato smiselno, da jo sami sprogramiramo. Na sliki 3 je prikazan postopek za zamenjavo, kjer smo uporabili dodatno spremenljivko. Samostojno razmislite, kako zamenjati dva elementa v seznamu brez uporabe dodatne spremenljivke ali razširitve polja. Urejanje z mehurčki Algoritem urejanja z mehurčki (ang. Bubble sort) je eden najbolj znanih algoritmov za urejanje. Osnovna ideja algoritma je, da pregledujemo seznam od prvega elementa in paroma primerjamo sosedne elemente. Če je levi element para večji od desnega elementa, potem ju zamenjamo. Primerjanje nadaljujemo do konca seznama in postopek ponavljamo, dokler v celotnem seznamu nismo zamenjali nobenega elementa več. Zakaj pa ime urejanje z mehurčki? Ime izhaja iz dejstva, da izgleda tako, kot da levi element para damo v mehurček in ga premikamo desno, dokler je trenutni desni element manjši od elementa v mehurčku. Pomembno je omeniti, da element, ki ga premikamo v mehurčku, ne pride nujno na svoje kočno mesto v urejenem seznamu, torej je lahko večkrat v mehurčku. Časovna zahtevnost algoritma je O(n2), saj se v najslabšem primeru zunanja zanka izvede n-krat, notranja pa se vedno izvede n - 1 krat. UrejanjeZMehurcki(A, dno, vrh): zamenjan = true ponavljaj dokler zamenjan: zamenjan = false za vsak i = dno+1 do vrh ponavljaj: ce (A(i-1) > A(i)) potem zamenjaj(A, i-1, i) zamenjan = true Na sliki 4 je prikazan algoritem Urejanja z mehurčki še v Bločkly-ju. Hitro urejanje Hitro urejanje (ang. QuičkSort) [?] je predstavnik algoritmov strategije Deli in vladaj, o kateri smo v Pre- PRESEK 44 (2016/2017) 3 25 RAČUNALNIŠ TVO seku že pisali [?]. Algoritem deluje rekurzivno na seznamu A v dveh korakih. Deli. Preuredimo seznam A[dno, vrh] v dva seznama A[dno, q - 1] in A[q + 1,vrh] na takšen način, da so vsi elementi v seznamu A[dno, q - 1] manjši ali enaki od A[q] ter da so vsi elementi A[q + 1, vrh] večji od A[q]. Index q določimo med postopkom preurejanja. Vladaj. Rekurzivno uredimo podseznama A[dno, q - 1] in A[q + 1,vrh]. Pri strategiji deli in vladaj je običajno še tretji korak, kjer delne rešitve, ki smo jih v koraku deli razdelili, združimo. Pri algoritmu hitro urejanje ta korak ni potreben, saj je delna rešitev že urejena in na pravem mestu. Najprej bomo zapisali algoritem za korak vladaj. HitroUredi(A, dno, vrh): ce dno < vrh potem q = deli(A, dno, vrh) HitroUredi(A, dno, q-1) HitroUredi(A, q+1, vrh) Opazimo, da v rekurzivnih klicih HitroUredi ne urejamo elementa, ki je na q mestu v seznamu A. Zakaj? To je posledica metode deli, ki jo bomo zapisali v nadaljevanju. deli(A, dno, vrh): pivot = A[dno] i = dno j = vrh ponavljaj dokler (i < j): ponavljaj dokler (A[i] <= pivot) i ++ ponavljaj dokler (A[j] > pivot): j++ ce (i < j) potem: zamenjaj(A,i,j) ce (i > j) potem: zamenj aj(A,dno,j) rezultat = j Na začetku metode določimo pivotni element, običajno je to prvi ali zadnji element seznama; v našem primeru je to prvi. S pomočjo pivota bomo seznam A razdelili na dva podseznama. V prvem seznamu bodo elementi, ki so manjši od pivota, v drugem pa elementi seznama A, ki so večji od pivota. Prvi seznam gradimo od indeksa dno proti vrhu (od leve proti desni glede na seznam), drugi seznam pa gradimo od vrha proti dnu (od desne proti levi). Sam algoritem za delovanje ne potrebuje dodatnega po-mnilniškega prostora, saj neposredno preureja originalni seznam. Z zankami ponavljaj sedaj pregledujemo polje z leve in desne ter iščemo elemente, SLIKA4. Urejanje mehurčki z 26 PRESEK 44 (2016/2017) 3 27 RAČUNALNIŠ TVO ■ ki so večji od pivotnega elementa (prva notranja zanka ponavljaj) in ■ ki so manjši od pivotnega elementa (druga notranja zanka ponavljaj). Ko se obe zanki zaključita, sta možni dve situaciji in sicer, ■ da je i manjši od j ali ■ da je i večji od j. V prvem primeru imamo še vedno dva elementa, kjer je element na i-tem mestu večji od pivota in element na j-tem mestu manjši od pivota. Zato ju lahko takoj zamenjamo, saj na ta način na začetek seznama prestavljamo manjše elemente in na koneč večje elemente. V drugem primeru pa se indeksa i in j prekrižata, kar pomeni, da nismo našli več takšnega para elementov, ki bi na obeh indeksih stali na napačnih mestih. Zato menjave ne izvedemo, zaključimo pa zunanjo zanko ponavljaj, saj s trenutnim pivotom ne moremo več deliti seznama. V zadnjem koraku moramo umestiti pivotni element v seznam na tako mesto, da bodo levo od njega manjši elementi in desno od njega večji. Katero mesto v seznamu je to? Razmislek pokaže, da je to lahko ali indeks i ali indeks j. Ce bi menjali element na indeksu i, potem bi na indeks dno postavili element, ki je večji od pivota (element na i-tem indeksu namreč to je). Zaradi tega bi prišli v navzkrižje s pravilom, da so v levem podseznama vsi elementi manjši od pivota. Ce menjamo pivot z j-tim elementom (ta kaže na element, ki je manjši od pivota), pravila ne kršimo, zato menjamo pivot in j-ti element. Posledično pivotni element sedaj stoji na mestu, ki se do konča urejanja ne bo več spremenilo, saj so v seznamu levo od njega manjši in desno večji elementi in ga zato ni potrebno več urejati niti upoštevati pri rekurzivnih kličih. To je tudi odgovor na prej zastavljeno vprašanje, zakaj elementa na mestu q ne urejamo več. Časovna zahtevnost algoritma je v najslabšem primeru O(n2), vendar se je v testih pokazalo, da je praktična časovna zahtevnost O(n log n), kar ga uvršča med najhitrejše algoritme urejanja. Njegova prednost je tudi, da ne zahteva dodatnega prostora, saj čelotno urejanje poteka samo znotraj danega seznama. Algoritem Hitro urejanje bomo implementirali tudi v vizualnem okolju Bločkly. Kot smo to storili že pri urejanju z mehurčki, najprej z naključnimi števili napolnimo seznam (slika 5). Nato sledi klič funkčije HitroUredi, ki je prikazana na sliki 6. Ker funkčijo uporabljamo rekurzivno, je prisoten zaustavitveni pogoj, kjer preverimo, ali je potrebno urediti še kakšen podseznam. V primeru, da je dno = vrh, bi urejali samo en element, kar pa ni smiselno. SLIKA 5. Pripravimo seznam PRESEK 44 (2016/2017) 3 27 RAČUNALNIŠ TVO SLIKA 6. Hitro uredi SLIKA 7. Postopek deli V pogojnem stavku najprej pokličemo funkcijo deli, ki seznam na prej opisan način preuredi in kot rezultat vrne na mesto, kjer je pivotni element. Funkcija deli je prikazana na sliki 7. Kot smo že uvodoma zapisali, nam okolje Blockly omogoča, da algoritem, ki smo ga bločno sprogrami-rali, izpišemo tudi v različnih programskih jezikih. V nadaljevanju je na sliki 8 prikaz algoritma Hitro urejanje v programskem jeziku Python. Opazimo, da je sedaj razumevanje kode zapisane v Pythonu lažje, če ga lahko primerjamo z Bločkly različičo. Zaključek V prispevku smo predstavili program Bločkly, ki omogoča bločno programiranje tudi bolj zahtevnih algoritmov. Razložili smo delovanje dveh algoritmov za urejanje, urejanje z mehurčki ter hitro urejanje in jih sprogramirali v Bločkly-ju. Velika prednost Bločkly-ja pri učenju programiranja je, da uporabniku omogoča program, izdelan v bločnem načinu izpisati v različnih programskih jezikih, kar lahko koristi pri učenje izbranega programskega jezika. Literatura [1] I. Pesek, Naučimo se programiti s pomočjo vizualnega programiranja, Presek 44 (1), 2016/2017. [2] https://blockly-demo.appspot.com/ static/demos/code/, ogled 20. 11. 2016. [3] T. H. Cormen et al., Introduction to Algorithms, MIT Press, 2009. [4] https://github.com/google/blockly/ wi ki, ogled 20. 11. 2016. [5] A. Taranenko, Reševanje problemov s pristopom deli in vladaj, Presek 37 (4), 2009/2010. www.dmfa.si 28 PRESEK 44 (2016/2017) 3 27 RAZVE DRILO import random x = None j = None seznam = None i = None zamenjan = None vrh = None dno = None pivot = None s = None list2 = None """Funkcija v seznamu zamenja i-ti in j-ti element def zamenjaj(seznam, i, j): x = seznam[int(i - 1)] seznam[int(i - 1)] = seznam[int(j - 1)] seznam[int(j - 1)] = x """Funkcija z metodo Hitro Uredi uredi dano zaporedje""" def hitroUredi(seznam, dno, vrh): if dno < vrh: s = deli(seznam, dno, vrh) hitroUredi(seznam, dno, s - 1) hitroUredi(seznam, s + 1, vrh) """Funkcija preuredi seznam v dva manjša seznama, za katera velja, da so elementi levega seznama manjši od pivota ter elementi desnega seznama vecji od pivota.vrne mesto na katerem je postavljen pivotni element.""" def deli(seznam, dno, vrh): pivot = seznam[int(dno - 1)] i = dno j = vrh while i < j: while seznam[int(i - 1)] <= pivot and i < vrh: i = i + 1 while seznam[int(j - 1)] > pivot and j > dno: j = j - 1 if i < j: zamenjaj(seznam, i, j) if i > j: zamenjaj(seznam, dno, j) return j seznam = [] for j in range(1, 11): seznam[int(j - 1)] = pri nt(seznam) dno = 1 vrh = len(seznam hitroUredi(seznam, dno, pri nt(seznam) random.randint(1, 100 vrh) SLIKA 8. Hitro urejanje v Pythonu XXX vU sU vU 999 JJJ 999 999 999 s - s H 31 «r ffin « X h«? S P» S K X T I T A UJLH V e 'i T X SS T R B 0 V l J e Ili M A l G A J R 0 3l K A 5 V R 8h e V 0 l T ^— M 0 N A h" "ip _ A V 0 R «M I N X A \E K S C T T T R I č N 0 S T sss s "H* H IZ" SS » M M e K I N e s _N_ e 0 N ¡¡¡E' IE" K 0 s(Tir {ISSnje > rs "S" If - ►P" T T ¥ U T A C I J e R G S? m S I R Hf v R v ■S" T "P A N K A ¥ BmfaJ „S, S JI A L 0 i Z i J n P A T T HE 0 T X X MAX E 'V I D E N T x R A N J X - T i A T R A M D 2o L A R G E p A R D s m V I N JI T 0 K "J ►S L E D 1! — 0 v I R A S A T A M 3E F I •S" I K E 4d U E L A N T K L E A H S S 0 M Jfi s A 1< 0 D N 0 llf K X R N I J S I] E A L P E 9 J A T 0 - s T E "e V E ® K N E Z |§- R I s ir I N I C I A T 0 R vr A R I 7c A S E B T T H A R T E R 0 K j\L 0 ilj? 0 S T X N E K S # \R U B i JI T V S K 0 _c K A - C A m č U T U 'H T A w 6t A ¥ V 0 D K M S M ¿S T Š T A R JOLOVOL^ K V T X N 0 -ffl- E W S R A ¥ P A S š Č I ise N T A n s A 5; I v B t 5I T R A Ur 9e 0 n i! č e t T I K JBin I n C E S x A T M 0 X F e R A T" R 0 X K A «E K I H _0_ T 0MFA _Z_ I B T—» K_ _R_ T JI REŠITEV NAGRADNE KRIŠANKE PRESEK 44/2 Pravilna rešitev nagradne križanke iz druge številke 44. letnika Preseka je Holditchev izrek. Izmed pravilnih rešitev so bili izžrebani Urška Poje iz Ljubljane, Tadina Bence Virag iz Lendave in Lidija Mikec iz Novega mesta, ki so razpisane nagrade prejeli po pošti. _ XXX PRESEK 44 (2016/2017) 3 29