uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
The number of bit comparisons used by Quicksort: an average-case analysis
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
2012 (English)In: Electronic Journal of Probability, ISSN 1083-6489, Vol. 17, 43- p.Article in journal (Refereed) Published
Abstract [en]

The analyses of many algorithms and data structures (such as digital search trees) for searching and sorting are based on the representation of the keys involved as bit strings and so count the number of bit comparisons. On the other hand, the standard analyses of many other algorithms (such as Quicksort) are performed in terms of the number of key comparisons. We introduce the prospect of a fair comparison between algorithms of the two types by providing an average-case analysis of the number of bit comparisons required by Quicksort. Counting bit comparisons rather than key comparisons introduces an extra logarithmic factor to the asymptotic average total. We also provide a new algorithm, "BitsQuick", that reduces this factor to constant order by eliminating needless bit comparisons.

Place, publisher, year, edition, pages
2012. Vol. 17, 43- p.
Keyword [en]
Quicksort, average-case analysis of algorithms, Poissonization
National Category
URN: urn:nbn:se:uu:diva-178654DOI: 10.1214/EJP.v17-1812ISI: 000305176000001OAI: oai:DiVA.org:uu-178654DiVA: diva2:542643
Available from: 2012-08-02 Created: 2012-08-01 Last updated: 2012-08-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Applied Mathematics
In the same journal
Electronic Journal of Probability

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 127 hits
ReferencesLink to record
Permanent link

Direct link