Computer Science – Data Structures and Algorithms
Scientific paper
2009-07-07
Computer Science
Data Structures and Algorithms
Scientific paper
In this paper, we present a framework based on a simple data structure and parameterized algorithms for the problems of finding items in an unsorted list of linearly ordered items based on their rank (selection) or value (search). As a side-effect of answering these online selection and search queries, we progressively sort the list. Our algorithms are based on Hoare's Quickselect, and are parameterized based on the pivot selection method. For example, if we choose the pivot as the last item in a subinterval, our framework yields algorithms that will answer q<=n unique selection and/or search queries in a total of O(n log q) average time. After q=\Omega(n) queries the list is sorted. Each repeated selection query takes constant time, and each repeated search query takes O(log n) time. The two query types can be interleaved freely. By plugging different pivot selection methods into our framework, these results can, for example, become randomized expected time or deterministic worst-case time. Our methods are easy to implement, and we show they perform well in practice.
Gupta Ankur
Kispert Anna
Sorenson Jonathan P.
No associations
LandOfFree
Online Sorting via Searching and Selection does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Online Sorting via Searching and Selection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Sorting via Searching and Selection will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-319447