Linked Questions
13 questions linked to/from Why is quicksort better than other sorting algorithms in practice?
5
votes
2
answers
1k
views
Why quicksort instead of a B-tree construction? [duplicate]
As far as I know (despite some variations which provide empirical average-case improvements) quick-sort is worst case $O(n^2)$ with the original Hoare partition scheme having a particularly bad ...
- 387
0
votes
1
answer
369
views
Is quick sort the best algorithm in average case compared to other comparison-based sorting algorithms? [duplicate]
I know that quick sort has an average case of O(nlogn). And I also know that the average case of comparison-based sorting algorithms are Omega of nlogn. Can we say that quick sort is the best sorting ...
65
votes
8
answers
207k
views
What is a the fastest sorting algorithm for an array of integers?
I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are:
Which is the fastest ...
- 991
40
votes
7
answers
5k
views
Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms
In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity.
In practice, what is ...
- 22.7k
8
votes
4
answers
13k
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:
...
6
votes
3
answers
9k
views
Quicksort vs. insertion sort on linked list: performance
I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm.
Does anyone have any idea why this is?
Insertion sort has a ...
- 787
4
votes
4
answers
8k
views
What is the fastest online sorting algorithm?
Quoting Online algorithm from Wikipedia:
In computer science, an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to ...
- 151
8
votes
2
answers
2k
views
What constitutes one unit of time in runtime analysis?
When calculating runtime dependence on the input, what calculations are considered? For instance, I think I learned that array indexing as well as assignment statements don't get counted, why is that?
user8722
0
votes
4
answers
11k
views
Difference between Quick sort, Merge sort and Heap sort
We know all the above-mentioned sorting algorithms take $\mathcal{O}(\mbox{N log N})$. Merge sort and Heap sort algorithms take $\mathcal{O}(\mbox{N log N})$ time in worst-case where Quicksort takes $\...
- 21
5
votes
1
answer
4k
views
Quick Sort: Randomized Pivot vs Median of 3/'Ninther' Pivot vs Uniform Shuffle of Input
Is the jury still out on this or do we now know which of the above mentioned ways of randomizing Quick Sort is the most optimum as far as average case running time (averaged over all possible input ...
- 153
1
vote
2
answers
321
views
What do I need to know about algorithms?
Drawing from Are algorithms (and efficiency in general) getting less important?, I get that algorithms are more important than ever, but I need to know anything about them other than their ...
- 1,143
2
votes
2
answers
213
views
Problems that become far easier when restricted to only integer values
I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values.
One such example would be sorting ...
- 198
0
votes
1
answer
139
views
In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? [closed]
It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the ...
- 1