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 ...
- 9,425
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. ...
- 3,310
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 ...
- 14.8k
9
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 ...
- 119
9
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 ...
- 15.5k
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 ...
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 ...
- 38.6k
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 ...
- 2,364
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....
- 275k
7
votes
What is the space complexity of quicksort?
Here is quicksort in a nutshell:
Choose a pivot somehow.
Partition the array into two parts (smaller than the pivot, larger than the pivot).
Recursively sort the first part, then recursively sort the ...
- 275k
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 ...
- 28.4k
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 ...
- 38.6k
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 ...
- 4,431
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 ...
- 275k
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 ...
- 4,301
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 ...
- 28.3k
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 ...
- 38.6k
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 ...
- 72k
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.
- 81.4k
4
votes
Accepted
Proof that quicksort's running time is ∼1.39 n log n
it's claimed that the running time of QuickSort is $∼1.39\,n\log_2n$
I don't have the book handy, but it it most certainly does not claim this. That figure is the result of a close analysis of a very ...
- 72k
4
votes
Accepted
Confusion about the definition of the average-case running time of algorithms
The definition is a special case of a more general notion. Given probability distributions $\mu_1,\mu_2,\ldots$ on inputs, the average running time (with respect to the $\mu_i$) is defined as
$$
\...
- 275k
4
votes
Why are unbalanced partitions worse than balanced partitions in Quicksort?
for balanced partitions the work actually remains constant on all the steps
That's just false. Have another look at the algorithm: each recursive call gets an input that is properly smaller than the ...
- 72k
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]...
- 41
4
votes
quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$?
No, $\log_4 n$ is not the same as $\log_2 n$. $\log_4$ is exactly $\frac{\log_2 n}{2}$. At the end of the complexity computation you can obviously say that $O(\log_4 n) = O(\log_2 n)$. But at this ...
- 1,585
4
votes
Accepted
How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?
I've been looking into examples and sorting arrays myself via Hoare's quicksort. I think I've found another interesting pattern in Hoare's partition algo. Which may explain why Hoare's method works. ...
4
votes
Accepted
Is there a sorting algorithm of order $n + k \log{k}$?
Here is an approach:
Create a hash map (dictionary in python) with keys being the elements of the vector and the corresponding values being the number of times the the element occurs in the vector, i....
- 529
4
votes
Average Case Running Time of Quicksort Algorithm
The average case running time of quicksort satisfies the recurrence
$$
T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n),
$$
with base case $T(0) = \Theta(1)$.
In view of solving this ...
- 275k
4
votes
Accepted
Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array
I could do QuickSelect (j - i) times to get all the elements
Overkill. Two calls to QuickSelect and one linear pass are sufficient.
- 2,072
3
votes
quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$?
You should forward this question to the authors of the document you refer to. What the text you quote provides is intuition on the performance of quicksort on random inputs. Actual proofs use ...
- 275k
3
votes
Why are unbalanced partitions worse than balanced partitions in Quicksort?
Raphael's answer gives you a formal proof: the recurrence from using a balanced partition solves to $\Theta(n \log n)$ and the (arbitrarily) unbalanced one to $\Theta(n^2)$.
Quicksort's recursive ...
- 2,916
Only top scored, non community-wiki answers of a minimum length are eligible