23 votes
Accepted

Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort ...
user avatar
22 votes
Accepted

Why don't we use quick sort on a linked list?

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result. At the same time the merge sort is ...
user avatar
  • 9,325
16 votes
Accepted

Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. ...
user avatar
  • 3,200
14 votes
Accepted

Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well ...
user avatar
14 votes
Accepted

Trying to understand this Quicksort Correctness proof

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with. The proof you describe is known as the ...
user avatar
  • 14.6k
11 votes
Accepted

Dual-pivot Quicksort reference implementation?

I tried to do exactly such a comparison in my master thesis, which thus naturally includes pseudo-code of “basic” versions of several dual-pivot Quicksorts (there is a list of them on page 9). Here ...
user avatar
  • 4,436
10 votes

Would using the mean as pivot speed up quicksort?

Using the mean for your partition does not prevent the $\Omega(n^2)$ worst-case behavior. It occurs when the input list is exponentially increasing. Consider the input: $1,n^2,n^3,\ldots,n^n$ The ...
user avatar
8 votes

Quicksort Partitioning: Hoare vs. Lomuto

Some comments added to the excellent Sebastian answer. I'm going to talk about the partition rearrangements algorithm in general and not about its particular use for Quicksort. Stability Lomuto's ...
user avatar
8 votes
Accepted

Hoare partitioning scheme in Quicksort

"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail. The part of code that are critical here are the following ...
user avatar
  • 34.1k
8 votes
Accepted

Isn't linear time O(n)?

Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$. When the presenter is speaking about linear time for ...
user avatar
  • 2,291
8 votes
Accepted

Stability of QuickSort Algorithm

One huge advantage of a stable sorting algorithm is that a user is able to first sort a table on one column, and then by another. Say that you have a website like Wikipedia with some tabular data, say ...
user avatar
  • 13.3k
7 votes

Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also ...
user avatar
7 votes

Trying to understand this Quicksort Correctness proof

This proof uses the principle of complete induction: Suppose that: Base case: $P(1)$ Step: For every $n > 1$, if $P(1),\ldots,P(n-1)$ hold (induction hypothesis) then $P(n)$ also holds....
user avatar
6 votes

Why does Randomized Quicksort have O(n log n) worst-case runtime cost

You were missing that these texts talk about "worst case expected run time", not "worst case runtime". They are discussing a Quicksort implementation that involves a random element. Normally you ...
user avatar
  • 25.2k
6 votes
Accepted

Implementation of QuickSort to handle duplicates

The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. In pseudocode, the algorithm ...
user avatar
  • 34.1k
6 votes

Is there a sorting algorithm of order $n + k \log{k}$?

The short answer is no, in the worst-case comparison based algorithms, for reasons stated here. Using a counting technique will at least take $O(n \log n)$ worst case and $O(n \log k)$ if you use a ...
user avatar
  • 4,371
5 votes
Accepted

Why does quicksort work well with virtual memory?

The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this: The hardware feature on modern computers that ...
user avatar
  • 1,230
5 votes
Accepted

Probabilty that quicksort partition creates an imbalanced partition

If $\alpha=0.5$, then $1-2 * 0.5 = 0$, which says that the smaller subarray cannot have length greater than half the original, since then it would be the larger subarray. If $\alpha=0$, then $1-2 * 0 ...
user avatar
5 votes

Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?

The term "Quicksort" stands for this abstract algorithmic idea: Pick a value $x$. Partition the input into $\{y\mid y \leq x\}$ and $\{y \mid y > x\}$. Recurse on the partitions (if they are non-...
user avatar
  • 70.9k
5 votes
Accepted

Solving Recurrence Relation (quicksort )

Your mistake is $2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace $\mathcal{O}(n)$ with $An$ for some constant $A$, which can be taken ...
user avatar
5 votes

Why don't we use quick sort on a linked list?

You can quick sort linked lists however you will be very limited in terms of pivot selection, restricting you to pivots near the front of the list which is bad for nearly sorted inputs, unless you ...
user avatar
5 votes

What is the worst case for C++ "sort" function?

The worst case for the Quicksort algorithm depends how a pivot is chosen and it can range from $\Theta(n \log n)$ (if you choose the pivot to be the median) to $\Theta(n^2)$ (if the pivot is always a ...
user avatar
  • 23.4k
5 votes
Accepted

Average number of exchanges during first partition stage in Quicksort

The partition method in the question, partition(a, lo, hi) is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort. Here ...
user avatar
  • 34.1k
4 votes
Accepted

Which measure of sortedness explains the phase transition in Quicksort's runtime?

Inversions are one way to measure "disorder" in a list: Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$. However,...
user avatar
  • 1,582
4 votes

Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

The relative costs of various operations are different on different machines, and compilers have varying degrees of ability to optimize various constructs. David Richerby goes into somewhat more ...
user avatar
  • 1,107
4 votes

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

The question you're asking deals with the topic of derandomization, and you're proposing a specific technique for derandomization, namely using pseudorandom number generators. There are other ...
user avatar
4 votes
Accepted

About a step in the analysis of Quicksort by Sedgewick and Wayne

Let $\rho_N = C_N/(N+1)$. The next to last equation shows that $$ \rho_N = \rho_{N-1} + \frac{2}{N+1}. $$ Therefore $$ \rho_N = \frac{2}{N+1} + \cdots + \frac{2}{2+1} + \rho_1. $$ Multiplying by $N+1$,...
user avatar
4 votes
Accepted

Why does the recurrence equation for QuickSort consider all the elements in the array?

When you're looking at the behaviour of the algorithm as $n\to\infty$, the difference between $n$ and $n-1$ becomes negligible. The simpler form is easier to deal with and it gives the same answer.
user avatar
4 votes

Why does the recurrence equation for QuickSort consider all the elements in the array?

As well for the general case: [recurrence with $q$] Note how $q$ remains a free variable here; that's bad. It's not the same $q$ for every recursive call, and either way you can not really solve the ...
user avatar
  • 70.9k
4 votes

Trying to understand this Quicksort Correctness proof

The missing part of the argument is transitivity of '<' - i.e the property that if a < b and b < c, then a < c. The proof that the final array is sorted goes something like this: Let A[i]...
user avatar
  • 41

Only top scored, non community-wiki answers of a minimum length are eligible