Sunday, 22 December 2013

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

The well-known Bubblesort algorithm sorts a list a1,a2,...,an 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 a1,a2,...,an , 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 limhrightarrow0fracsin(ha)h

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