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?

## 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 "...
- programming - Consider the following input and output: INPUT: (((5 + 1) – (7 – 4...
- Intro to Computer Programming - Pseudocode - This assignment (below) jumped way ...
- Computer Programming - I was wondering if someone could review my pseudocode to ...
- Information Technology - Develop an algorithm, flow chart and pseudocode that ...
- Computers - Problem-Solving 1. Develop an algorithm or write pseudocode to ...
- Programming Logic - I need help creating a program to compare the value in input...
- Simple Array Process - need help with this generate only the pseudocode. No ...
- Ms Visio - • 2. Construct a data dictionary and draw a hierarchy chart and ...