David Podgorelec (Author), Gregor Klajnšek (Author)

Abstract

Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm 'vertex sort'. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertexsort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (inlinear time) than random cases. We have named the combined algorithm 'smartquicksort' because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm.

Keywords

računalniška geometrija;triangulacija mnogokotnika;hitro urejanje;navihano hitro urejanje;skanirna premica;urejanje ogljišč;computational geometry;quicksort;smart quicksort;sweep-line;polygon triangualation;vertex sort;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
UDC: 004.92
COBISS: 9318934 Link will open in a new window
ISSN: 0020-0255
Views: 1616
Downloads: 75
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary keywords: računalniška geometrija;triangulacija mnogokotnika;hitro urejanje;navihano hitro urejanje;skanirna premica;urejanje ogljišč;
URN: URN:SI:UM:
Pages: str. 383-405
Volume: ǂVol. ǂ169
Issue: ǂiss. ǂ3/4
Chronology: Feb. 2005
ID: 8718466
Recommended works:
, no subtitle data available
, diplomska naloga univerzitetnega študijskega programa
, no subtitle data available
, no subtitle data available
, diplomska naloga visokošolskega strokovnega študijskega programa