Distributional analysis of swaps in quick select

DOI10.1016/J.TCS.2010.01.029MaRDI QIDQ964394zbMATH OpenOpenAlexFDO

Authors Hosam M. Mahmoud

Publication date 15 April 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.01.029

zbMATH Keywords

algorithmaverage-case analysisgrand averagerecurrencesortingcombinatorial probabilityperpetuityquick sort

Mathematics Subject Classification ID

Searching and sorting (68P10)

Recommendations

• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• A statistical view on exchanges in Quickselect
• Analysis of quickselect : an algorithm for order statistics
• Quickselect and the Dickman Function
• Analysis of swaps in radix selection

Cites work

• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 568880 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1540682 (Why is no real title available?)
• A general limit theorem for recursive algorithms and combinatorial structures
• A generating functions approach for the analysis of grand averages for multiple QUICKSELECT
• A limit theorem for “quicksort”
• Analysis of quickselect : an algorithm for order statistics
• Approximating perpetuities
• Asymptotic distribution theory for Hoare's selection algorithm
• Average-case analysis of moves in Quick Select
• Average-case analysis of multiple Quickselect: An algorithm for finding order statistics
• Comparisons in Hoare's Find Algorithm
• Hoare's Selection Algorithm: A Markov Chain Approach
• Moves and displacements of particular elements in quicksort
• Multiple Quickselect -- Hoare's Find algorithm for several elements
• QUICKSELECT revisited
• Quickselect and the Dickman Function
• Quicksort

Cited in

(7)

• A statistical view on exchanges in Quickselect
• Analysis of quickselect under Yaroslavskiy's dual-pivoting algorithm
• Measuring post-quickselect disorder
• Moves and displacements of particular elements in quicksort
• Perpetuities in fair leader election algorithms
• Analysis of swaps in radix selection
• On fluctuations of complexity measures for the FIND algorithm

Describes a project that uses

Uses Software

• Find
• Quicksort

This page was built for publication: Distributional analysis of swaps in quick select

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