Bogosort, also known as
stupid sort
or
monkey sort
, is a rather (in)famous sorting technique known for its inefficiency. In bogosort, you shuffle the array randomly and check if it's sorted; if it isn't, you repeat the whole thing.
Since you're clever, you come up with a better version of bogosort. If some of the first and last few values (a prefix and a suffix of the array) are already correctly sorted, we don't need to include them in the shuffle; we can fix them in place. For example, suppose that we shuffle and get ; we can now fix the and only shuffle . Note that although are in the correct place, we still include them in the shuffle since they are not "first and last few values".
Let be the expected number of shuffles needed to sort the first natural numbers, given that none of the numbers are in the right place initially (so all numbers are included in the shuffle). If can be written as where and are coprime positive integers, what is the value of ?
Bonus Question What is the expected running time of the modified bogosort?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
If n ≥ 2 , the number of orderings where the first u (but not the first u + 1 ) are correct, and where the last v (but not the last v + 1 ) are correct, is (by the Inclusion-Exclusion Principle): ( n − u − v ) ! − ( n − u − v − 1 ) ! − ( n − u − v − 1 ) ! + ( n − u − v − 2 ) ! provided that u + v ≤ n − 2 . Thus the probability that, when n symbols are shuffled, precisely a symbols are fixed, leaving n − a symbols to be shuffled next time around, is p n , a = ⎩ ⎪ ⎨ ⎪ ⎧ n ! ( a + 1 ) [ ( n − a ) ! − 2 ( n − a − 1 ) ! + ( n − a − 2 ) ! ] 0 n ! 1 0 ≤ a ≤ n − 2 a = n − 1 a = n Using conditional expectations (and setting X ( 0 ) = 0 for convenience) X ( n ) = = = = a = 0 ∑ n p n , a ( 1 + X ( n − a ) ) = 1 + a = 0 ∑ n p n , a X ( n − a ) 1 + a = 0 ∑ n − 2 p n , a X ( n − a ) = 1 + a = 0 ∑ n − 2 n ! ( a + 1 ) [ ( n − a ) ! − 2 ( n − a − 1 ) ! + ( n − a − 2 ) ! ] X ( n − a ) 1 + a = 2 ∑ n n ! ( n + 1 − a ) [ a ! − 2 ( a − 1 ) ! + ( a − 2 ) ! ] X ( a ) 1 + a = 2 ∑ n n ! ( n + 1 − a ) ( a 2 − 3 a + 3 ) ( a − 2 ) ! X ( a ) for all n ≥ 2 , so that X ( 2 ) = 2 and X ( n ) = 2 n − 3 n ( n − 1 ) [ 1 + a = 2 ∑ n − 1 n ! ( n + 1 − a ) ( a 2 − 3 a + 3 ) ( a − 2 ) ! X ( a ) ] for all n ≥ 3 .
A quick computer calculation yields X ( 1 5 ) = 8 5 3 8 3 2 1 8 6 7 0 7 5 4 6 9 0 8 7 8 8 6 1 0 8 5 1 8 so the answer is 4 6 9 0 8 7 8 8 6 1 0 8 5 1 8 + 8 5 3 8 3 2 1 8 6 7 0 7 5 = 4 7 7 6 2 6 2 0 7 9 7 5 5 9 3 .