A Note on Average-Case Sorting |
| |
Authors: | Shay Moran Amir Yehudayoff |
| |
Institution: | 1.Department of Computer Science,Technion-IIT,Haifa,Israel;2.Max Planck Institute for Informatics,Saarbrücken,Germany;3.Department of Mathematics,Technion-IIT,Haifa,Israel |
| |
Abstract: | This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman’s algorithm which is a variant of insertion sort and provide a basically tight upper bound: If μ is a distribution on permutations on n elements, then one may sort inputs from μ with expected number of comparisons that is at most H(μ) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation π, the algorithm sorts π by using at most \(\log _{2}(\frac {1}{\Pr _{\mu }(\pi )})+2n\) comparisons. A lower bound on the expected number of comparisons of H(μ) always holds, and a linear dependence on n is also required. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|