ECCC-Report TR13-106https://eccc.weizmann.ac.il/report/2013/106Comments and Revisions published for TR13-106en-usTue, 13 Jan 2015 14:50:35 +0200
Revision 2
| A note on average-case sorting |
Shay Moran,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2013/106#revision2This 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 $\mu$ is a distribution on permutations on $n$ elements, then one may sort inputs from $\mu$ with expected number of comparisons that is at most $H(\mu) + 2n$, where $H$ is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation $\pi$, the algorithm sorts $\pi$ by using at most
$\log_2(\frac{1}{\Pr_\mu(\pi)})+2n$ comparisons. A lower bound on the expected number of comparisons of $H(\mu)$ always holds, and a linear dependence on $n$ is also required.Tue, 13 Jan 2015 14:50:35 +0200https://eccc.weizmann.ac.il/report/2013/106#revision2
Revision 1
| A note on average-case sorting |
Shay Moran,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2013/106#revision1This 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 $\mu$ is a distribution on permutations on $n$ elements, then one may sort inputs from $\mu$ with expected number of comparisons
that is at most $H(\mu) + 2n$,
where $H$ is the entropy function.
Moreover, the algorithm uses less comparisons
for more probable inputs: For every permutation $\pi$, the algorithm sorts $\pi$ by using at most $\log_2(\frac{1}{\Pr_\mu(\pi)})+2n$ comparisons. A lower bound on the expected number of comparisons of $H(\mu)$ always holds, and a linear dependence on $n$ is also required.Sat, 12 Apr 2014 22:57:50 +0300https://eccc.weizmann.ac.il/report/2013/106#revision1
Paper TR13-106
| A note on average-case sorting |
Shay Moran,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2013/106This 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 \mu is
a distribution on permutations on n elements, then one may sort inputs from
with expected number of comparisons that is at most H(\mu) + 2n, where H is the
entropy function. A lower bound of H(\mu) always holds, and a linear dependence
on n is also required.Tue, 30 Jul 2013 19:30:24 +0300https://eccc.weizmann.ac.il/report/2013/106