登入
選單
返回
Google圖書搜尋
Smart Quicksort: adaptive algorithm for sorting geometric data
David Podgorelec
Borut Žalik
出版
Faculty of Electrical Engineering and Computer Science, Laboratory for geometric modelling and multimedia algorithms
, 2003
URL
http://books.google.com.hk/books?id=VVgROQAACAAJ&hl=&source=gbs_api
註釋
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 of a low number of monotone subarrays, no matter whether presortedness appears in desired or in reverse order. Besides this, the proposed combination is not much slower than quicksort in random case. Our work was inspired by the problems 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 name the 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.