Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR13-106 | 13th January 2015 14:50

A note on average-case sorting

RSS-Feed




Revision #2
Authors: Shay Moran, Amir Yehudayoff
Accepted on: 13th January 2015 14:50
Downloads: 457
Keywords: 


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 $\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.


Revision #1 to TR13-106 | 12th April 2014 22:57

A note on average-case sorting





Revision #1
Authors: Shay Moran, Amir Yehudayoff
Accepted on: 12th April 2014 22:57
Downloads: 914
Keywords: 


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 $\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.



Changes to previous version:

Improved the analysis: Now we show that the algorithm uses less comparisons for more probable permutations


Paper:

TR13-106 | 29th July 2013 12:19

A note on average-case sorting





TR13-106
Authors: Shay Moran, Amir Yehudayoff
Publication: 30th July 2013 19:30
Downloads: 911
Keywords: 


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 \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.



ISSN 1433-8092 | Imprint