Menu
Suppose that you have a magic data structure that represents a linear sequence of elements that supports lookup, insertion, and deletion of any index in worst-case O(1) time. (I'm pretty sure that no such structure is possible given the memory model of modern machines, but let's just suppose that we have one for the fun of it).
A friend of mine pointed out that if you have this data structure, then you can build a cool sorting algorithm for integers that runs in expected O(n lg lg n) time as follows. First, create one of the magic data structures mentioned above. Next, for each element in the input array, use interpolation search to find, in expected O(lg lg n) time, the index in that magic array in which the element belongs, then in O(1) time insert the element. Finally, in O(n) time, read off the sorted magic data structure. This makes n calls to the O(lg lg n) interpolation search, which will run in O(n lg lg n) time.
I understand that this above approach is not going to give worst-case O(n lg lg n) time for sorting, since there are pathologically bad input arrays that if used in interpolation search would degenerate the search to O(n2) time. My question is, given this magic data structure, what is the fastest integer sorting algorithm that can be built, assuming we care only about the worst-case runtime of the algorithm?
(This may be a better fit on cstheory, but I'd figured I'd ask here first since I've gotten some great algorithms answers in the past.)
288
If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case. But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
Quick Sort is also known as Partition Sort. This sorting algorithm is faster than the previous algorithms because this algorithm uses the concept of Divide and Conquer.
Quicksort. Quicksort is one of the most efficient sorting algorithms, and this makes of it one of the most used as well. The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.
Quick sort is the fastest, but it is not always O(N*log N), as there are worst cases where it becomes O(N2). Quicksort is probably more effective for datasets that fit in memory. For larger data sets it proves to be inefficient so algorithms like merge sort are preferred in that case.
Counting sort is of O(n) complexity http://en.wikipedia.org/wiki/Counting_sort . However, it is not always convenient to use, because temporary array that is created by the algorithm has size of maximum integer value of sorted array.
143
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
