Menu
Some of you might have stumbled upon this cute article - http://igoro.com/archive/quicksort-killer/ \
What is really interesting is how he fixes quick sort to perform in O(N log N) against the defined adversary.
the quicksort might choose the median element as the pivot at each step, thus always geting a perfect split of the input sequence into two halves. Median can be found deterministically in O(N) running time, and so the total running time is always O(N log N).
My question is won't the linear time median-finding algorithm end up using the same compare function and perform in O(N^2) instead of O(N)?
Edit:
To be precise: I am questioning the complexity of the partition-based-median-selection algorithm which uses a strategy similar to that of quick sort and it will use the same compare function as the one quick sort uses. How can it work in O(N) with this adversary?
624
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.
Quicksort: Quick sort is an Divide Conquer algorithm and the fastest sorting algorithm. In quick sort, it creates two empty arrays to hold elements less than the pivot element and the element greater than the pivot element and then recursively sort the sub-arrays.
Quick Sort is a sorting algorithm, which is commonly used in computer science. Quick Sort is a divide and conquer algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub arrays.
won't the linear time median-finding algorithm end up using the same compare function and perform in O(N^2) instead of O(N)?
No, by adding an O(N) function to find the median the complexity becomes
O((N+N) log N) == O(2N log N) == O(N log N)
But, as that article states, the increased constant makes it unattractive.
The standard technique is called median-of-3 and a full median search won't really improve over that.
If worst case is critical, just don't use Quicksort. Shellsort has a better upperbound.
91
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
