C/C++

Ker vemo, da je najmanjši element že na vrhu, postopek ponovimo, vendar se ustavimo en zapis pred vrhom. Sedaj vemo, da je na drugem mestu drugi naj manjši element. Postopek ponavljamo, dokler padajoče ne uredimo cele tabele. Tako nam elementi kot nekakšni mehurčki plavajo proti vrhu. Od tod ime. Mehurčno urejanje ni občutljivo na vhodne podatke. Urejanje je enako dolgo, ne glede na vhodne podatke. Časovna kompleksnost je n*n , kar urejanje uvršča med počasnejše. Čas urejanja narašča kvadratno z dolžino vhodnih podatkov. Ta podatek je recept za časovno bombo. Kar pomeni, da bi program odlično in hitro deloval pri npr. 1000 vhodnih podatkih. Pri npr. 100.000 vhodnih podatkih bi povsem zablokiral računalnik.

zlivanje.c

Zlivanje (Vir:3) je metoda urejanja, ki ni odvisna od vhodnih podatkov, sama hitrost ni odvisna od razporeditve podatkov. Časovna kompleksnost je n*ln(n). Časovna kompleksnost ima veliko konstanto, zato se hitrost urejanja v primerjavi z mehurčnim urejanjem pozna šele pri velikih n.

Mehurčno urejanje deli vhodno tabelo na polovico. Te polovice na četrtine in tako naprej, dokler ne ostaneta samo dve števili. Rekurzivno pisanje programov močno obremenjuje zalogovnik (stack). Rekurzivni programi so kratki in jasni. Preostali dve števili uredimo z enostavnim if stavkom. Sedaj zlivamo najprej dvojice, potem po štiri, osem do vrha. Po končanem postopku imamo urejeno tabelo.

C je prevajalnik. Prvič morate pritisnit gumb »Prevedi in poženi«. Ko je enkrat program preveden, lahko za ponovni zagon programa pritisnemo gumb »Poženi«

vstavljanje.c

Urejanje z vstavljanjem (Vir:4) je neodvisno od podatkov. Ima časovno kompleksnost n*n. Je nevaren za tempirane bombe ob prevelikem povečanju vhodnih podatkov.

Urejanje z vstavljanjem začne na drugem mestu in si zapomni vrednost. Najprej izberemo podtabelo spodnjih dveh elementov. Zapomnimo si zgornji element podtabele. Poiščemo prvo mesto, kjer je zgornji element večji kot element na trenutnem mestu. Zgornji element podtabele vpišemo na mesto kamor spada, preostali del podtabele pa prestavimo za eno navzgor. Podtabela prvi, drugi element je s tem postopkom urejen.  Sedaj si zapomni tretji element in ga vstavi v podtabelo prvi, tretji element. Ustavimo zopet na mesto, ki ustreza velikosti tretjega elementa. Vstavljanje pomeni, da najprej poiščemo mesto, kamor moramo ustaviti element. Potem vse elemente desno prestavimo za ena, in na koncu zapišemo zadnji element na izpraznjeno mesto. Ko ta postopek ponovimo za celotno tabelo, je le-ta urejena.

hitro.c

Hitro urejanje (Vir:5) je odvisno od vhodnih podatkov. Takemu urejanju lahko podtaknemo take podatke, da ureja po časovni kompleksnosti n*n ali pa po n*ln(n). Zaradi male konstante je v povprečju učinkovit pri kratkih ali dolgih vhodnih tabelah.

Vaja uporabi knjižnico stdlib. Ime urejanja je qsort (quick sort). Uporaba standardnih in preizkušenih knjižnic je dobra izbira, zaradi male verjetnosti napake in verjetno naj boljših rezultatov.

Je pa tale vaja odlična za malo bolj radovedne. Če si pogledate na Vir:5, boste našli zapis algoritma za hitro urejanje. Poizkusite namesto standardne knjižnice uporabita ta algoritem

meritev.c

Pri urejanju se ukvarjamo s časovno kompleksnostjo in eventualno odvisnostjo od vhodnih podatkov.

Na primerih smo si pogledali štiri najbolj uporabljane algoritme. Nekaj malega smo si ogledali teoretično ozadje, za razširjeno poznavanje so navedeni viri. Na primerih smo vedno dali enake vhodne podatke in na koncu dobili le-te lepo urejene. Sedaj nas zanimajo konkretni časi urejanja naključnih vhodnih podatkov ob različnih dolžinah le-teh.

Najprej nekaj o merjenju časa. Seveda uporabimo knjižnico za to. Najprej se moramo zavedati, da smo v več opravilnem operacijskem sistemu, z osrednjim dodeljevalnikom opravil. Vsako opravilo je lahko kadarkoli naključno prekinjeno za naključno dolžino časa. Zadnjič smo ugotovili, da se to dogaja v časovnem okviru cca. 2ms. Kratki časi izvajanja programa (kar v našem primeru pomeni kratka vhodna tabela), lahko pri meritvah, ki se izvajajo na vgrajenih števcih procesorskih jeder, velika stresanja rezultata. Dodeljevalnik opravil že lahko poskrbi, da se programi , ki so v delovanju, čedalje manj prekinjajo v primerjavi s programi, ki uporabljajo sleep metodo, vendar je pri kratkih programih vsega konec, preden se opravi optimizacija. Pomaga , da test izvedemo večkrat in primerjamo rezultate.

Iz tabele lahko razberemo časovno kompleksnost in izvajanje merjeno v mikrosekundah. Kot smo napovedali, se iz rezultatov vidi časovna kompleksnost n*n pri mehurčnem urejanju in urejanju z vstavljanjem. Časovno kompleksnost n*ln(2) prepoznamo iz rezultatov urejanja z zlivanjem in pri hitrem urejanju. Zanemarljive niso konstante, ki določijo zmagovalca v obeh kategorijah časovne kompleksnosti. Absolutni zmagovalec je pričakovano uporaba standardne knjižnice za hitro urejanje. Vendar tudi urejanje z zlivanjem ni slabo. Upoštevati moramo, da smo ga napisali enkrat za vajo, ga nismo nič optimizirali (npr. uporaba registrov) in ni bil izpostavljen optimizacijam, kar se je standardni knjižnici zagotovo dogajalo. Za zaključek naloga. Poizkusite optimizirati urejanje z zlivanjem. Urejanje z zlivanjem ni odvisno od vhodnih podatkov, zato ima najslabšo možnost, daleč boljšo od hitrega urejanja. Obstaja ogromno problemov, kjer nas zanima najslabša možnost in ne povprečje. Če najdete super rešitev, bomo popravili vajo in dodali ime avtorja

Naslednjič

Naslednjič se vračamo na Python. Čakajo nas tri nadaljevanja osnov. Python je prvi po uporabi s strani programerjev , zato je prav, da ga spoznamo temeljito, preden udarimo v realne projekte. Vse kar berete je na slovenski izdaji in je osnova novi mehatroniki, ki sledi tehnološki revoluciji.

Viri

1. http://si.raspberryip.com/c/programi/
2. https://en.wikipedia.org/wiki/Bubble_sort
3. https://en.wikipedia.org/wiki/Merge_sort
4. https://en.wikipedia.org/wiki/Insertion_sort
5. https://en.wikipedia.org/wiki/Quicksort

Avtor:Mag. Boštjan Šuhel

Email:bostjan.suhel@gmail.com

2021-294