| KRATKA VSEBINA | In the report, we propose a combination of quicksort and a new sorting algorithm, which shows excellent time performance in sorting sorted arrays and nearly sorted arrays consisting ofa low number of monotone subarrays, no matter whether presortedness appearsin desired or in reverse order. Besides this, the proposed combination is not much slower than quicksort in random case. Our work was inspired by theproblems met during sorting polygon vertices in sweep-line algorithms of computational geometry, and therefore, we name the new algorithm vertex sort. It splits input array into three subarrays. Two of them are sorted already, 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 that the worst case time complexity does not exceed running times of quicksort, but the simplest case s are handled in linear time. Because ofthis desired property, we namethe combined algorithm smart quicksort. We approve its efficiency by employing it in the well-known sweep-line based polygon triangulation algorithm. In the last part of the report, we introduce some ideas that should improve the algorithm in near future. A nonrecursive versionis proposed among all. // V poročilu predlagamo kombinacijo hitrega urejanja in novega algoritma urejanja, ki se je izkazala za izreno učinkovito pri urejanja urejenih in skoraj urejenih zaporedij, ki sestojijo iz majhnega števila podzaporedij, urejenih v želenem ali v obratnem vrstnem redu. Predlagana kombinacija tudi v naključnih primerih ni veliko počasnejša od hitrega urejanja. K delu so nas vzpodbudili problemi, ki nastopijo pri urejanju oglišč mnogokotnikov v algoritmih računalniške geometrije, temelječih na prebirni premici, zato smo nov algoritem poimenovali kar urejanje oglišč (angl. vertex sort). Algoritem razdeli vhodno zaporedje v tri podzaporedja. Dve sta že urejeni, tretjega pa je treba obravnavati iterativno. Enostaven preizkus odloča, ali naj se urejanje oglišč izvede rekurzivno ali pa naj se v drugi iteraciji izvede hitro urejanje. Na ta način dosežemo, da najslabša časovna zahtevnost ne prekorači časov izvajanja hitrega urejanja, najenostavnejše primere pa rešimo v linearnem času. Zaradi te zaželene lastnosti smo predlagano kombinacijo obeh algoritmov poimenovali navihano hitro urejanje (angl. smart quicksort). Učinkovitost metode smo potrdili z uporabo v znanem algoritmu triangulacijemnogokotnikov, ki temelji na prebirni premici. V zadnjem delu poročila predstavimo nekaj zamisli, ki naj bi v bližni prehodnosti še izboljšale algoritem. Med drugim predstavimo tudi nerekurzivno verzijo. |