Menu
I have been reading about Quicksort and found that sometimes it' s referred to as "Deterministic Quicksort".
Is this an alternate version of the normal Quicksort ? What is the difference between a normal Quicksort and a Deterministic Quicksort ?
250
Deterministic Sort This is a sort algorithm that returns the same results each time. On the face of it, it would seem odd for any sort algorithm to not be deterministic, but there are examples of real-world sort algorithms that aren't.
Quicksort sorts an array A by partitioning it into subarrays using a pivot element, and recursively sorting the subarrays. In the randomized (Las Vegas) version, the pivot is chosen at random from the subarray.
The advantage of randomized quicksort is that there's no one input that will always cause it to run in time Θ(n log n) and the runtime is expected to be O(n log n).
Unlike merge sort, we don't need to merge the two sorted arrays. Thus Quicksort requires lesser auxiliary space than Merge Sort, which is why it is often preferred to Merge Sort. Using a randomly generated pivot we can further improve the time complexity of QuickSort.
The ordinary ("deterministic") Quicksort can have very poor behaviour on particular datasets (as an example, an implementation that picks the first unsorted element has O(n^2) time complexity on already-sorted data).
Randomized Quicksort (which selects a random pivot, rather than choosing deterministically) is sometimes used to give better expected performance over all datasets.
102
Quicksort runs in O(n log n) expected/average time, but O(n^2) worst case. This occurs if the pivot chosen is consistently either the minimum or the maximum.
Ideally, you want to select the median as your pivot. If finding the median directly is too costly (usually this is the case if you're trying to use quicksort), what's commonly done instead is to either take the median of three potential pivot elements, or else just pick a random element as your pivot.
The latter method renders quicksort nondeterministic because of the randomness inherent to the pivot selection process.
42
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
