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?
Sunday, 22 December 2013
probability - What is the expected number of swaps performed by Bubblesort?
Subscribe to:
Post Comments (Atom)
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}...
-
Self-studying some properties of the exponential-function I came to the question of ways to assign a value to the divergent sum $$s=\sum_{k=...
-
Ok, according to some notes I have, the following is true for a random variable $X$ that can only take on positive values, i.e $P(X<0=0)$...
-
Make a bijection that shows $|\mathbb C| = |\mathbb R| $ First I thought of dividing the complex numbers in the real parts and the c...
No comments:
Post a Comment