Sunday 22 December 2013

probability - What is the expected number of swaps performed by Bubblesort?

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by
repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order)

until there are no remaining inversions. (Note that the number of swaps required does not
depend on the order in which the swaps are made.) Suppose that the input to Bubblesort is a
random permutation of the numbers $a_1, a_2, . . . , a_n$ , so that all $n!$ orderings are equally likely,
and that all the numbers are distinct. What is the expected number of swaps performed by
Bubblesort?

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...