Zunanje urejanje

diplomsko delo

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

Abstract

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.

Keywords

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

Data

Language:	Slovenian
Year of publishing:	2020
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[E. Rihar]
UDC:	004(043.2)
COBISS:	1538539971
Views:	1534
Downloads:	143
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	External sorting
Secondary abstract:	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.
Secondary keywords:	sorting;merging;runs;data;files;algorithms;computer science;computer and information science;diploma;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000470
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	51 str.
ID:	11416811