Python Program for BogoSort or Permutation Sort

The BogoSort or permutation sort is the most inefficient sorting algorithm. Here, BOGO itself means bogus. The sorting technique generates all possible permutations of a given list and determines whether or not it is sorted.

In, this tutorial, we are going to perform a BogoSort algorithm to sort an array by two different approaches.

BogoSort - Basic Introduction

Bogo sort is also known as Permutation sort, Shotgun sort, or Monkey sort and is based on the creating and test paradigm. It's that easy, and it plainly takes a long time to execute, especially for tiny arrays. It's just a case of trial and error.

We can implement bogus sort using two different approaches which are as follows:

1. Generating Least permutations
2. Shuffling Elements

We will discuss each approach one by one.

Approach 1 - Generating Least Permutations

This method creates all permutations and checks to see whether they are in the correct sequence. If the answer is true, the list is returned.

Algorithm

As discussed above let's now have a look at the algorithm:

1. Import random
2. Create a function bogo_sort()
3. Pass array as a parameter
4. define a function sort() to check if it is sorted or not
5. define a function permutation() to generate the permutations
6. Check the array returned
7. If sorted print the array

Program

Let us now dive deep into the programming part influenced by the algorithm discussed above:

import random

def bogo_sort(array):
	a = len(array)
	while (sort(array)== False):
		permutation(array)

def sort(array):
	a = len(array)
	for i in range(0, a-1):
		if (array[i] > array[i+1] ):
			return False
	return True

def permutation(array):
	a = len(array)
	for i in range (0,a):
		p = random.randint(0,a-1)
		array[i], array[p] = array[p], array[i]

array = [9,8,7,6,5,4,3,2,1]
print("The original array is: ", array)
bogo_sort(array)
print("The Sorted array is :", array)

The original array is: [9, 8, 7, 6, 5, 4, 3, 2, 1]
The Sorted array is : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Approach 2 - Shuffling Elements

Here, we take random numbers from the array, put them into a new array, and check if it is sorted or not.

Algorithm

As discussed above let's now have a look at the algorithm:

1. Import random
2. Define a function reorder()
3. Pass array as a parameter
4. It is used to rearrange the sorted permutation
5. Define a function bogo_sort()
6. Pass array as a parameter
7. Take reorder as a consent
8. If a permutation is sorted return
9. Print the sorted array

Program

Let us now dive deep into the programming part influenced by the algorithm discussed above:

import random
def reorder(array):
    a = len(array)
    for i in range(a):
        r = random.randint(0,a-1)
        array[i],array[r] = array[r],array[i]
    return array    

def bogo_sort(array):
    while(True):
        for n in range(len(array)-1):
            if array[n]<=array[n+1]:
                pass
            else:
                break
        else:    
            return array
        array = reorder(array)

array=[2,1,3,5]
print("The original array is: ", array)
bogo_sort(array)
print("The sorted array is: ", array)

The original array is: [2, 1, 3, 5]
The sorted array is: [1, 2, 3, 5]

Conclusion

In this tutorial, we have performed the bogoSort method to sort an array with two different approaches. The first approach is by generating the least permutation and the second approach is by shuffling the elements. The time complexity of this algorithm is O(n) and the space complexity is O(1).