Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)

zbMATH Open1355.68070MaRDI QIDQ2959907FDOQ2959907

Authors: James Allen Fill 

Publication date: 10 February 2017

Full work available at URL: http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0116

Recommendations

• Distributional convergence for the number of symbol comparisons used by QuickSort
• The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract).
• Distributional convergence for the number of symbol comparisons used by QuickSelect
• Rates of convergence for Quicksort
• A limit theorem for “quicksort”

zbMATH Keywords

couplingtamenessdistributional convergenceQuickSortprobabilistic sourcesymbol comparisons

Mathematics Subject Classification ID

Searching and sorting (68P10)

Cited In (8)

• The limiting distribution for the number of symbol comparisons used by QuickSort is nondegenerate (extended abstract).
• The Number of Symbol Comparisons in QuickSort and QuickSelect
• Towards a realistic analysis of the QuickSelect algorithm
• The number of bit comparisons used by quicksort: an average-case analysis
• Distributional convergence for the number of symbol comparisons used by QuickSort
• Towards a realistic analysis of some popular sorting algorithms
• Revisiting calculation of moments of number of comparisons used by the randomized quick sort algorithm
• Distributional convergence for the number of symbol comparisons used by QuickSelect

This page was built for publication: Distributional convergence for the number of symbol comparisons used by QuickSort (extended abstract)

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