find the average-case time complexity for bogosort where we are ordering the list a1, a2, . . . , an. We begin by finding the average number of shuffles needed to order the list. Problem: What is the probability that a list a1, a2, . . . , an is ordered?
This assignment is an exercise in finding the average-case complexity of an
Rather than looking at how long an algorithm can run in the worst case as in worst-
case analysis, we are looking at how long an algorithm runs on average. This is done
by computing the average number of comparisons and operations executed until the
algorithm ends.
Bogosort is a sorting algorithm that orders a list in increasing order by taking the
list, checking to see if the list is ordered increasingly, if the list is not ordered increasingly
then the list is randomly shuffled, and then repeating this process until the list is ordered
increasingly.
Expressed in pseudocode:
Algorithm 1 Bogosort
Require: list: a1, a2, . . . , an of real numbers
Ensure: list is sorted in increasing order
1: procedure bogo(list)
2: while not sorted(list) do ▷ Checks to see if list is sorted
3: shuffle(list) ▷ Shuffle the current list if not sorted
4: end while
5: end procedure
the list a1, a2, . . . , an. We begin by finding the average number of shuffles needed to
order the list.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
