Zunanje urejanje

diplomsko delo

Erik Rihar (Avtor), Tomaž Dobravec (Mentor)

Povzetek

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.

Ključne besede

urejanje;zlivanje;čete;podatki;datoteke;algoritmi;računalništvo;računalništvo in informatika;visokošolski strokovni študij;diplomske naloge;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[E. Rihar]
UDK:	004(043.2)
COBISS:	1538539971
Št. ogledov:	1534
Št. prenosov:	143
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	External sorting
Sekundarni povzetek:	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.
Sekundarne ključne besede:	sorting;merging;runs;data;files;algorithms;computer science;computer and information science;diploma;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000470
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	51 str.
ID:	11416811