Questions tagged [quicksort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
82
votes
2answers
59k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: ...
11
votes
2answers
2k views

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

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms ...
0
votes
2answers
338 views

Question regarding Hoare's partitioning scheme and a slight modification to it

This is the pseudocode on wikipedia for Hoare's partitioning scheme: ...
2
votes
2answers
827 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
10
votes
3answers
7k views

Trying to understand this Quicksort Correctness proof

This proof is a proof by induction, and goes as follows: P(n) is the assertion that "Quicksort correctly sorts every input array of length n." Base case: every input array of length 1 is already ...
4
votes
1answer
804 views

Hoare partitioning scheme in Quicksort

I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme. Wikipedia page says, that when choosing a pivot element one can use both ...
2
votes
2answers
218 views

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

I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example ...
0
votes
1answer
64 views

Which element is at its final position after the partitioning step in Quicksort?

In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position. The entry a[j] is in its final place in the array, for some j. No entry in a[lo] ...
6
votes
2answers
332 views

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

I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is ...
3
votes
1answer
845 views

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?

All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode. If p is what is returned by the ...
0
votes
1answer
221 views

Quicksort bounds

I found an implementation of Quicksort here, and now I cannot understand why it works with those left and right bounds. Right now the link above is unavailable due to some problems with their hosting ...
0
votes
2answers
424 views

What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?

If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at ...