Posted by Nathan on Saturday, February 23, 2013 at 8:52pm.
The sorting algorithm known as bogosort can be described in pseudocode as:
while not isSorted(input):
shuffle(input)
If we feed bogosort a shuffled array of length n of unique items the distribution of the number of times
bogosort checks if the array is sorted (henceforth called `an iteration') is Geo( 1/n! ).
(a) What is the expected number of iterations it will take bogosort to run for an array of k unique
values?
(b) When writing this question I ran bogosort many times. I wanted to nd a case where I was using
an array of 5 items and it took bogosort more than 500 iterations to sort the array. What is the
probability that if I run bogosort on an array of 5 items that bogosort will take more than 500
iterations to sort it? (Write out the sum you would need to evaluate and evaluate the sum. Write
the answer to 4 decimal places)
(c) When feeding in a shued array of 3 unique values into bogosort the probability that it takes less
than or equal to 2 iterations to sort the array is 11/36. If I use bogosort to sort 20 random arrays
each with 3 unique values - What is the distribution of the number of arrays it takes less than or
equal to 2 iterations to sort?
(d) What is the probability that for the same situation as in the previous part that exactly 2 out of the
20 arrays took less than or equal to 2 iterations to sort?
No one has answered this question yet.
Answer this Question
Related Questions
pseudocode programming - Develop an algorithm or write pseudocode to determine ...
computers - The recursive algorithm of the 4th Section of the chapter "...
Math - Can you help me with the following Input and Output values? Input 0 ...
7 th grade math - What is the rule for this function? input 1 output 3 input 2 ...
Programming Logic - I need help creating a program to compare the value in input...
math - What is the rule for this function? Input 1 output 3 Input 2 output 5 ...
math - What is the rule for this function? Input 1 output 3 Input 2 output 5 ...
Programming - I need help creating a program to compare the value in input[0] ...
Information Technology - Develop an algorithm, flow chart and pseudocode that ...
math - i need help with patterns and equations i cant find the rule it goes like...
For Further Reading
