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

MaRDI QIDQ2959907zbMATH OpenFDO

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

zbMATH Keywords

couplingtamenessdistributional convergenceQuickSortprobabilistic sourcesymbol comparisons

Mathematics Subject Classification ID

Searching and sorting (68P10)

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”

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)