Revision #2 Authors: Shay Moran, Amir Yehudayoff

Accepted on: 13th January 2015 14:50

Downloads: 962

Keywords:

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 Authors: Shay Moran, Amir Yehudayoff

Accepted on: 12th April 2014 22:57

Downloads: 2106

Keywords:

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.

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

TR13-106 Authors: Shay Moran, Amir Yehudayoff

Publication: 30th July 2013 19:30

Downloads: 1992

Keywords:

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.