The number of bit comparisons used by Quicksort, an average-case analysis

zbMATH Open1317.68292MaRDI QIDQ5501271FDOQ5501271

Authors: James Allen Fill, Svante Janson 

Publication date: 3 August 2015

Recommendations

• The number of bit comparisons used by quicksort: an average-case analysis
• Analysis of the expected number of bit comparisons required by quickselect
• Analysis of the expected number of bit comparisons required by quickselect
• How Many Comparisons Does Quicksort Use?
• A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Searching and sorting (68P10)

Cited In (13)

• On a Constant Arising in the Analysis of Bit Comparisons in Quickselect
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Towards a Realistic Analysis of Some Popular Sorting Algorithms
• Analysis of Branch Misses in Quicksort
• Modelling thermal transients from magmatic underplating -- an example from the Vøring margin (NE atlantic)
• The number of bit comparisons used by quicksort: an average-case analysis
• Compact Hilbert indices: space-filling curves for domains with unequal side lengths
• Analysis of the expected number of bit comparisons required by quickselect
• Analysis of swaps in radix selection
• A Machine-Checked Proof of the Average-Case Complexity of Quicksort in Coq
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm
• How Many Comparisons Does Quicksort Use?

This page was built for publication: The number of bit comparisons used by Quicksort, an average-case analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501271)