Search

V diplomski nalogi predstavljamo interaktivno aplikacijo, ki vizualizira delovanje nekaterih algoritmov za iskanje najkrajših poti na grafih. Iz precej širokega nabora algoritmov smo izbrali Dijkstrov, Bellman-Fordov, Floyd-Warshallov, D'Esopo-Papeov in Fredman-Tarjanov algoritem. V besedilu teoretično predstavljamo njihovo delovanje in uporabo na različnih področjih, navajamo pa tudi njihovo psevdokodo. Predstavljamo tudi delovanje aplikacije in primere delovanja za posamezne algoritme. Aplikacijo smo izdelali kot didaktički pripomoček, namenjen tako učiteljem kot študentom. In this diploma thesis, we present an interactive application for visualizing algorithms for finding shortest paths in graphs. From a fairly large set of algorithms, we selected the Dijkstra, Bellman-Ford, Floyd-Warshall, D'Esopo-Pape, and Fredman-Tarjan algorithm. We describe them informally and in pseudocode. Tha application was designed as a didactic tool, both for teachers and for students.

V svetu programiranja je urejanje podatkov zelo pomembno. Sčasoma so ljudje implementirali veliko različnih algoritmov, ki rešujejo ta problem ali pa izboljšujejo že obstoječe. Diplomsko delo obravnava problem urejanja podatkov na podlagi manj znanih algoritmov. Implementirani in analizirani so naslednji: sodo-liho urejanje (Odd-even sort), comb sort, ciklično urejanje (Cycle sort), pigeonhole sort, urejanje z drevesom (Tree sort) in timsort. Primerjava algoritmov je izvedena na podlagi prostorske in časovne zahtevnosti, dejanskega časa izvajanja, števila primerjav, števila prireditev in števila rekurzivnih klicev (če jih imajo). Da bi bila analiza realna, so vsi algoritmi analizirani na podlagi podobnih testnih podatkov, ki zajemajo večino možnih scenarijev pri urejanju. In the world of programming, sorting is very important. Over time, people have implemented many different algorithms that solve this problem or improve existing ones. The diploma thesis deals with the problem of data sorting using less known algorithms. Some of them have been implemented and analyzed: Odd-even Sort, Comb sort, Cycle sort, Pigeonhole sort, Tree sort, and Tim sort. The comparison of algorithms is based on the time and space complexity, the actual execution time, the number of comparisons, the number of assignments, and the number of recursive calls (if any). To make the analysis realistic, all algorithms are analyzed on similar test data. The test data cover most of the possible scenarios that could occur during sorting.