1

I faced this problem on a website and I quite can't understand the output, please help me understand it :-

Bogosort, is a dumb algorithm which shuffles the sequence randomly until it is sorted. But here we have tweaked it a little, so that if after the last shuffle several first elements end up in the right places we will fix them and don't shuffle those elements furthermore. We will do the same for the last elements if they are in the right places. For example, if the initial sequence is (3, 5, 1, 6, 4, 2) and after one shuffle we get (1, 2, 5, 4, 3, 6) we will keep 1, 2 and 6 and proceed with sorting (5, 4, 3) using the same algorithm. Calculate the expected amount of shuffles for the improved algorithm to sort the sequence of the first n natural numbers given that no elements are in the right places initially.

Input:

2
6
10

Output:

2
1826/189
877318/35343

For each test case output the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions. I just can't understand the output.

Improve this question
5
  • What about the input? Is the initial sequence (2, 6, 10)? That is already sorted... Commented Jun 17, 2012 at 9:24
  • @SimeonVisser : 2 here means that the input would contain first 2 natural numbers, but unsorted offcourse similarly 6 means 1st 6 natural numbers Commented Jun 17, 2012 at 9:26
  • Could the output values be rational numbers? That is, is it saying that the the expected number of modified bogosorts required to get [1,2,3,4,5,6] into order is 186/189 ~= 9.66 times? I can't think of a good way to calculate those expected values, so I can't test this meaning, but the first value, 2 is the right answer for the sequence [1, 2] (it's 1 + sum(1/n^2 for n in 1..infinity)). Commented Jun 17, 2012 at 9:38
  • @Blckknght : For each test case output has to be, the expected amount of shuffles needed for the improved algorithm to sort the sequence of first n natural numbers in the form of irreducible fractions. Commented Jun 17, 2012 at 9:42
  • Er, my previous comment had a typo that I can't edit any more. I meant to say that 1826/189 is a fraction, which is approximately 9.66. I'm pretty sure that's the expected number of sorts for a sequence of length 6. The third output, 877318/35343 is about 24.82, which is presumably the expected number or sorts needed for a sequence of length 10. I can't think of how to do the calculation myself, but I think the output is understandable, at least. Commented Jun 17, 2012 at 9:47

2 Answers 2

Reset to default
1

I assume you found the problem on CodeChef. There is an explanation of the answer to the Bogosort problem here.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Yes Anders, I found the problem at Codechef, thanks for the link :)
0

Ok I think I found the answer, there is a similar problem here https://math.stackexchange.com/questions/20658/expected-number-of-shuffles-to-sort-the-cards/21273 , and this problem can be thought of as its extension

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.