What is a Deterministic Quicksort?

algorithm sorting quicksort deterministic
Andreas Grech picture Andreas Grech · Feb 22, 2010 · Viewed 9.3k times · Source

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 ?

Answer

Anon. picture Anon. · Feb 22, 2010

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.

Related questions

Quicksort with Python

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code? I do not know how to concatenate the three arrays and printing them. def sort(array=[12,4,5,6,7,3,1,15]): less = [] …

Read More
Why is quicksort better than mergesort?

I was asked this question during an interview. They're both O(nlogn) and yet most people use Quicksort instead of Mergesort. Why is that?

Read More
Quicksort: Choosing the pivot

When implementing Quicksort, one of the things you have to do is to choose a pivot. But when I look at pseudocode like the one below, it is not clear how I should choose the pivot. First element of list? …

Read More