Algoritmi za zunanje urejanje

BUDIHNA, ANEJ (author), Mihelič, Jurij (mentor)

V diplomskem delu je predstavljeno področje zunanjega urejanja. V nalogi je opisanih in primerjanih več algoritmov za zunanje urejanje, kako se obnašajo ter katere so njihove prednosti in slabosti. Algoritmi, ki jih primerjamo so navadno večsmerno zlivanje, navadno uravnoteženo zlivanje, naravno uravnoteženo zlivanje, polifazno zlivanje, kaskadno zlivanje, urejanje s porazdeljevanjem, urejanje z lijakom in dva algoritma za predurejanje. Namen diplomske naloge je opisati in predstaviti delovanje teh algoritmov v teoriji in v praksi. Algoritme smo implementirali v programskem jeziku C ter jih med seboj poskusno primerjali na osebnem računalniku z eno zunanjo napravo za shranjevanje podatkov.

• Language: Slovenian
• Keywords: urejanje, podatki, algoritmi
• Work type: Bachelor thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2015
• PID: 20.500.12556/RUL-72480
• Publication date in RUL: 21.09.2015

Secondary language

• Language: English
• Title: Algorithms for external sorting

Abstract

The thesis presents the field of external sorting. In the thesis we describe and compare multiple sorting algorithms for external sorting based on their behavior, their advantages and disadvantages. The algorithms we compare are the straight multiway merge sort, balanced multiway merge sort, natural multiway merge sort, polyphase merge sort, cascade sort, distribution sort, funnel sort and two pre-sorting algorithms. The purpose of the thesis is to describe and present how the algorithms work in theory and in practice. We implemented the algorithms in the C programming language and then experimentally compared them on a personal computer with one external storage device.

• Keywords: sorting, data, algorithms