Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [quicksort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
14
votes
4answers
4k views

Is transitivity required for a sorting algorithm

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators? Background: A sorting algorithm generally ...
1
vote
0answers
14k views

Best and worse case inputs for heap sort and quick sort? [duplicate]

So given a input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts? ...
2
votes
0answers
538 views

Quick Select explanation

I have been looking for a quick and easy explanation on Quick Select and stumbled upon this. It's quick and easy to follow, but there's a part which I am not following quite well: The uploader is ...
0
votes
1answer
110 views

what does it mean by problem of size $0$?

I am having problems understanding a basic concept in CLRS, it is about worst case partitioning during quicksort -- The worst-case behavior for quicksort occurs when the partitioning routine ...
82
votes
2answers
59k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: ...
4
votes
2answers
479 views

From Whence the Randomization in Randomized Quicksort

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is ...