4 ms·

This is false. Quicksort can be made worst case O(n lg n) with linear time selection and pivoting around the median: http://www.cs.princeton.edu/~wayne/cs423/l

by vecter 16y ago

This is false. Quicksort can be made worst case O(n lg n) with linear time selection and pivoting around the median: http://www.cs.princeton.edu/~wayne/cs423/lectures/selection-4up.pdf http://www.cs.princeton.edu/~wayne/cs423/lectures/selection-... http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_.22Median_of_Medians_algorithm.22 http://en.wikipedia.org/wiki/Selection_algorithm#Linear_gene... http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/embed06 http://ocw.mit.edu/courses/electrical-engineering-and-comput...

baddox 16y ago
Is it true that quicksort is worst-case O(n lg n) if you always select the median? What if there are a lot of duplicate values at the median? My understanding has always been that for any quicksort algorithm on given hardware you can construct a pathogenic input that will be sorted in quadratic time.
- vecter 16y ago
  Hardware is irrelevant. The analysis is mathematical and abstract. The model that people typically work in when doing this analysis is the comparison model: one < comparison costs 1 (http://en.wikipedia.org/wiki/Comparison_sort http://en.wikipedia.org/wiki/Comparison_sort). There are other models that more closely resemble computers. For example, in the cell probe model (http://www.itl.nist.gov/div897/sqg/dads/HTML/cellProbeModel.html http://www.itl.nist.gov/div897/sqg/dads/HTML/cellProbeModel....) you have a word size (e.g. 32 bits, but the exact number is irrelevant) and you can construct radix sort in that model. If all values in your set of numbers to sort are unique, then quicksort is indeed O(n lg n) worst case if you pivot about the median. If there are duplicate values, can you think of a way to still guarantee worst case O(n lg n)?

by vecter 16y ago

baddox 16y ago

Is it true that quicksort is worst-case O(n lg n) if you always select the median? What if there are a lot of duplicate values at the median? My understanding has always been that for any quicksort algorithm on given hardware you can construct a pathogenic input that will be sorted in quadratic time.

vecter 16y ago
Hardware is irrelevant. The analysis is mathematical and abstract. The model that people typically work in when doing this analysis is the comparison model: one < comparison costs 1 (http://en.wikipedia.org/wiki/Comparison_sort http://en.wikipedia.org/wiki/Comparison_sort). There are other models that more closely resemble computers. For example, in the cell probe model (http://www.itl.nist.gov/div897/sqg/dads/HTML/cellProbeModel.html http://www.itl.nist.gov/div897/sqg/dads/HTML/cellProbeModel....) you have a word size (e.g. 32 bits, but the exact number is irrelevant) and you can construct radix sort in that model. If all values in your set of numbers to sort are unique, then quicksort is indeed O(n lg n) worst case if you pivot about the median. If there are duplicate values, can you think of a way to still guarantee worst case O(n lg n)?