Pred vami je programček, s pomočjo katerega je prikazano delovanje algoritma za urejanje podatkov z zlivanjem, imenovanega Merge Sort. Programček prikazuje urejanje števil s pomočjo algoritma urejanje z zlivanjem ali Merge Sort.

Program je preveden. Originalen program najdete v programu NetLogo. Da pridete do njega, morate klikniti File, nato Model Library, izbrati Computer Science, nato mapo unverified in na končno še Merge Sort.

In order for this to work, this file, your model file (Merge Sort.nlogo), and the file NetLogoLite.jar must all be in the same directory. (You can copy NetLogoLite.jar from the directory where you installed NetLogo.)

On some systems, you can test the applet locally on your computer before uploading it to a web server. It doesn't work on all systems, though, so if it doesn't work from your hard drive, please try uploading it to a web server.

You don't need to include everything in this file in your page. If you want, you can just take the HTML code beginning with <applet> and ending with </applet>, and paste it into any HTML file you want. It's even OK to put multiple <applet> tags on a single page.

If NetLogoLite.jar and your model are in different directories, you must modify the archive= and value= lines in the HTML code to point to their actual locations. (For example, if you have multiple applets in different directories on the same web server, you may want to put a single copy of NetLogoLite.jar in one central place and change the archive= lines of all the HTML files to point to that one central copy. This will save disk space for you and download time for your user.)

Narejeno z NetLogo

Izvorna datoteka: Merge Sort.nlogo

KAJ JE TO?

Ta model je prikaz standardnega algoritma za urejanje, imenovanega 'urejanje z zlivanjem' (merge sort). Ta algoritem razporedi n števil v naraščajočem vrstnem redu. To dosežemo s tem, da razdelimo števila po urejenih skupinah - četah in nato zlivamo manjše čete v večje. Zaporedje je urejeno, ko ostane ena sama četa.

Z NetLogo-m je možno veliko enostavneje kot v tem modelu zapisati algoritem za urejanje z zlivanjem, vendar ker ta model predstavlja navidezno delovanje algoritma, je koda veliko bolj zapletena, kot če bi nam model zgolj uredil števila brez prikaza vmesnih korakov.

KAKO DELUJE?

Začnemo s toliko četami, kolikor imamo števil. Ko algoritem napreduje skozi seznam, zliva pare sosednjih čet. Tako se po vsakem sprehodu skozi seznam, število čet razpolovi.

Potek zlivanja dveh čet:
1. Primerja začetne elemente teh dveh čet
2. Prepiše manjši/večji element (odvisno od naraščajočega/padajočega vrstnega reda)iz teh dveh čet v tretjo četo
3. Izbriše ta element iz izvorne čete
4. Ponavlja dokler se ena od izvornih čet ne izprazni
5. Premesti vse preostale elemente iz 'neprazne' izvorne čete na konec tretje čete
6. Nadomesti izvorni dve četi s tretjo četo

To zlivanje ponavljamo za vsak par čet, dokler nam ne preostane ena sama četa.

Število korakov, ki so potrebni, da s pomočjo tega algoritma uredimo zaporedje n števil, je najbližje log(n) (z osnovo 2). Vsak korak ima največ n primerjav med števili. Zato je časovna zahtevnost algoritma približno enaka n log(n). Znanstveniki s področja računalništva to navadno zapišejo kot O(n log n), kjer n pove, koliko števil bomo razvrščali.

KAKO UPORABLJATI?

Število elementov, ki jih želimo urediti, spremenimo s pomočjo drsnika STEVILO_ELEMENTOV.

Pritisk na gumb NASTAVI ustvari toliko naključno izbranih elementov, ki jih želimo sortirati, kolikor smo jih določili z drsnikom STEVILO_ELEMENTOV.

KORAK (ŠTEVILO) zlije eno število v njegovo novo četo.
KORAK (VRSTICA)) naredi en poln krog zlivanj.

STVARI, KI JIH JE POTREBNO OPAZITI

Čete so predstavljene z barvami. Število iz iste čete ima isto barvo. Ko sta dve četi zliti, števila v novi četi dobijo barvo manjšega/večjega elementa.

Ali lahko predvidimo zadnjo barvo vseh elementov še pred začetkom sortiranja?

Ali bi zlivanje več kot dveh čet hkrati zmanjšalo število korakov pri urejanju?
Ali bi ta sprememba naredila algoritem hitrejši?

RAZŠIRJANJE MODELA

Ali lahko izpopolniš model tako, da elementi med razvrščanjem rišejo poti?

Poznamo veliko algoritmov za urejanje zaporedij. Nekaj si jih lahko ogledaš na naslednji povezavi http://en.wikipedia.org/wiki/Sorting_algorithm. Poizkusi zapisati različna urejanja v NetLog-u in za primerjavo uporabi 'BehaviorSpace'.

ZNAČILNOSTI NETLOGA

Ta model temelji na seznamih.

Upoštevajmo, da NetLogo vsebuje SORT in SORT-BY primitive; navadno uporabljamo te, rajši kot da sami sporograiramo kak algoritem. SORT razvrsti predmete v naraščajočem vrstnem redu; SORT-BY pa prepusti izbiro vrstnega reda uporabniku.