article

How many comparisons does Quicksort use?

Authors:

William F. Eddy,

Mark J. SchervishAuthors Info & Claims

Journal of Algorithms, Volume 19, Issue 3

Pages 402 - 431

https://doi.org/10.1006/jagm.1995.1044

Published: 01 November 1995 Publication History

Abstract

No abstract available.

Cited By

View all

Liu JKnowles CDavis A(2005)A cost optimal parallel quicksorting and its implementation on a shared memory parallel computerProceedings of the Third international conference on Parallel and Distributed Processing and Applications10.1007/11576235_51(491-502)Online publication date: 2-Nov-2005
https://dl.acm.org/doi/10.1007/11576235_51
Rösler URüschendorf L(2001)The contraction method for recursive algorithmsAlgorithmica10.1007/BF0267961129:1-2(3-33)Online publication date: 1-Feb-2001
https://dl.acm.org/doi/10.1007/BF02679611

Index Terms

How many comparisons does Quicksort use?
1. Mathematics of computing
  1. Discrete mathematics
  2. Mathematical software
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching
  2. Models of computation
    1. Probabilistic computation

Recommendations

Engineering quicksort

This paper describes the results of a large empirical study to measure the run-time behavior of Quicksort by using various methods of computing the pivot element for medium to large size randomly generated integer data. The results of our study ...
Some performance tests of “quicksort” and descendants

Detailed performance evaluations are presented for six ACM algorithms: quicksort (No. 64), Shellsort (No. 201), stringsort (No. 207), “TREESORT3” (No. 245), quickersort (No. 271), and qsort (No. 402). Algorithms 271 and 402 are refinements of algorithm ...
The Number of Symbol Comparisons in QuickSort and QuickSelect
ICALP '09: Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I

We revisit the classical QuickSort and QuickSelect algorithms, under a complexity model that fully takes into account the elementary comparisons between symbols composing the records to be processed. Our probabilistic models belong to a broad category ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of Algorithms Volume 19, Issue 3

Nov. 1995

171 pages

ISSN:0196-6774

Editors:
Zvi Galil
Columbia Univ., New York, NY and Tel Aviv Univ., Tel Aviv, Israel
,
David S. Johnson
At&T Bell Labs.,Murray Hills, NJ
,
Donald E. Knuth
Stanford Univ., Stanford, CA

Issue’s Table of Contents

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 November 1995

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu JKnowles CDavis A(2005)A cost optimal parallel quicksorting and its implementation on a shared memory parallel computerProceedings of the Third international conference on Parallel and Distributed Processing and Applications10.1007/11576235_51(491-502)Online publication date: 2-Nov-2005
https://dl.acm.org/doi/10.1007/11576235_51
Rösler URüschendorf L(2001)The contraction method for recursive algorithmsAlgorithmica10.1007/BF0267961129:1-2(3-33)Online publication date: 1-Feb-2001
https://dl.acm.org/doi/10.1007/BF02679611

Abstract

Cited By

Index Terms

Recommendations

Engineering quicksort

Some performance tests of “quicksort” and descendants

The Number of Symbol Comparisons in QuickSort and QuickSelect

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations