Zunanje urejanje

RIHAR, ERIK (avtor), Dobravec, Tomaž (mentor)

V diplomskem delu je predstavljeno področje urejanja podatkov na zunanjih pomnilniških napravah kot so trdi diski in tračne enote. V teoretičnem delu je opisanih več različnih algoritmov in njihovih temeljnih principov delovanja ter njihove poglavitne prednosti in slabosti. Algoritmi, izbrani za primerjavo, so navadno zlivanje, naravno uravnoteženo dvosmerno zlivanje, naravno uravnoteženo večsmerno zlivanje, polifazno zlivanje in tritonsko urejanje. V praktičnem delu izbrane algoritme med seboj primerjamo glede na čas izvajanja, število primerjav med elementi, količino prebranih podatkov z diska in količino zapisanih podatkov na disk. Primerjavo smo izvedli nad dvema različnima vrstama vhodnih podatkov, to so 32 bitna cela števila in nizi različnih dolžin ter petimi različnimi začetnimi porazdelitvami vhodnih podatkov. Izbrali smo naključno, normalno, delno urejeno, urejeno in obratno urejeno porazdelitev. Algoritme smo implementirali v programskem jeziku Java ter jih poganjali na osebnem računalniku z operacijskim sistemom Linux in enim trdim diskom.

• Jezik: Slovenski jezik
• Ključne besede: urejanje, zlivanje, čete, podatki, datoteke, algoritmi
• Vrsta gradiva: Diplomsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2020
• PID: 20.500.12556/RUL-114385
• COBISS.SI-ID: 1538539971
• Datum objave v RUL: 25.02.2020

RIHAR, ERIK, 2020, Zunanje urejanje [na spletu]. Diplomsko delo. [Dostopano 26 april 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=114385

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: External sorting

Izvleček

The thesis presents data sorting on external storage devices such as hard drives and tape drives. The theoretical part describes several different algorithms and their basic principles of operation, as well as their main advantages and disadvantages. For the comparison, the listed algorithms were selected: straight merge sort, natural balanced two-way merge sort, natural balanced multi-way merge sort, polyphase merge sort and triton sort. The practical part compares the selected algorithms by their runtime, the number of element compares, the amount of data read from the hard drive and amount of data written to the hard drive. We compared the algorithms on two different types of input data: 32-bit integers and strings of random length, as well as five different initial distributions of input data. The random, Gaussian, partly ordered, ordered and inverse ordered distribution were chosen. The algorithms were implemented in Java programming language and run on a personal computer with Linux operating system and one hard drive.

• Ključne besede: sorting, merging, runs, data, files, algorithms