Questions tagged [quicksort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7
votes
1answer
3k views

Would using the mean as pivot speed up quicksort?

Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only ...
6
votes
2answers
358 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 ...
-2
votes
2answers
2k views

Probabilty that quicksort partition creates an imbalanced partition

I have come across this question: Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
-1
votes
1answer
200 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
3
votes
1answer
2k views

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

For Hoare's partitioning algorithm quicksort is implemented as such ...
-2
votes
1answer
251 views

Quicksort implementation unclear

This code is taken from wikipedia: ...
3
votes
1answer
859 views

Cost of partitioning in quicksort

I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple. When talking about ...
3
votes
2answers
4k views

Dual-pivot Quicksort reference implementation?

Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere? I would like to include that algorithm in a comparison among sorting algorithms for a ...
4
votes
2answers
364 views

Performance impact due to time required for shuffling in Quicksort

As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
7
votes
2answers
9k views

Why is Quicksort described as “in-place” if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?

Quicksort is described as "in-place" but using an implementation such as: ...
7
votes
4answers
10k views

QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens: ...
0
votes
2answers
182 views

Quicksort's asymptotic performance for array of [50,…,50,100,…100]

Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort. I think it it should be $O(n^2)$ as for array of ...
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
555 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 ...
89
votes
2answers
64k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: (the argument A is the array, and [p, r] is the range, inclusive,...
4
votes
2answers
524 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 ...

1 2
3