| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Acceleration of sweep-line technique by employing smart quicksort
Avtorji:Podgorelec, David (Avtor)
Klajnšek, Gregor (Avtor)
Datoteke:URL http://dx.doi.org/10.1016/j.ins.2004.07.002
 
Jezik:Angleški jezik
Vrsta gradiva:Neznano ()
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis: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.
Ključne besede:computational geometry, quicksort, smart quicksort, sweep-line, smart quicksort, polygon triangualation, vertex sort
Leto izida:2005
UDK:004.92
COBISS_ID:9318934 Povezava se odpre v novem oknu
ISSN pri članku:0020-0255
NUK URN:URN:SI:UM:DK:1YSCAPMZ
Število ogledov:1203
Število prenosov:47
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Information sciences
Skrajšan naslov:Inf. sci.
Založnik:North-Holland
ISSN:0020-0255
COBISS.SI-ID:25613056 Novo okno

Sekundarni jezik

Jezik:Angleški jezik
Ključne besede:računalniška geometrija, triangulacija mnogokotnika, hitro urejanje, navihano hitro urejanje, skanirna premica, urejanje ogljišč


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici