A note on average-case sorting

DOI10.1007/S11083-015-9347-YMaRDI QIDQ5965138zbMATH OpenOpenAlexFDO

Authors Shay Moran, Amir Yehudayoff

Publication date 2 March 2016

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-015-9347-y

zbMATH Keywords

average-case complexitycomparison based sortingShannon's entropy

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Measures of information, entropy (94A17)

Recommendations

• Optimal average case sorting on arrays
• Algorithms – ESA 2004
• Presorting algorithms: an average-case point of view
• Average-Case Analysis of Perfect Sorting by Reversals
• Average-case analysis of perfect sorting by reversals
• The average-case parallel complexity of sorting
• On the average-case complexity of Shellsort
• Efficient sample sort and the average case analysis of PEsort
• A new algorithm for Jordan sorting: Its average-case analysis

Cites work

• Balancing poset extensions
• Elements of Information Theory
• Entropy and sorting.
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)

Cited in

(4)

• On the distribution of comparisons in sorting algorithms
• Average-case analysis of perfect sorting by reversals
• The entropy of lies: playing twenty questions with a liar
• Efficient sample sort and the average case analysis of PEsort

This page was built for publication: A note on average-case sorting

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