Week12Activity.html CS400: BogoSort

BogoSort: What is it?

Bogo Sort is a sorting algorithm that generates many permutations of an input until it finds a permutation that is correctly sorted. For example, an array of numbers that should be in ascneding order. Bogo sort will create many different permutations of this array until it stumbles on an array that is correct. This sorting algorithm is definitely not useful but it is very fun!

Pseudocode for BogoSort and its Steps

Pseudocode

The pseudocode for this algorithm is essentially: while (not sorted(object)){ shuffle(object) }

Steps to actually implement BogoSort

  1. Given an array, the sort method will iterate through to check that the array is ordered
  2. If the array is unordered it will swap elements inside the array randomly through a random class or by mathematical algorithm
  3. The method will then check whether the array is ordered again, if not start again at step 2
  4. If the array is ordered it will return the ordered array

The actual time complexity for this method is unknown as there is no real way to accurately gauge when this method will return an ordered array.

As seen in this image, there is no set way each element moves, they are moved around randomly until they are put it into the correct order at some point. For an array like this it took less than 3 attempts, but it could also take more than 300 on another test with this exact same array.

Here is a webpage going into more detail about BogoSort