Permutation Sort or Bogo Sort

In Permutation Sort or Bogo Sort, you have been given one array, which consists of different values. You have to sort the array using BOGO sort. Let’s take an example:

Input-  { 2, 3, 0, 8, 4, 1, 7, 5, 6 }

Output- { 0, 1, 2, 3, 4, 5, 6, 7, 8 }

Explanation- We take an unsorted array and return the sorted array.

Algorithm:

Step 1: Start

Step 2: An array is created of size n. Then the value of the array size is taken from the user.

Step 3: The values of array elements are taken from the user.

Step 4: A function is called to calculate the answer.

Step 5: In this function, we take the array.

Step 6: This function processes all the array elements by permutation and sorts them.

Step 7: The answer is returned.

Step 8: The returned values will be printed.

Step 9: Stop.

Explanation of Algorithm: - So the basic concept behind this sorting algorithm is very simple and clear. We just have to do permutation. In the function, the numbers of the array will be permuted many times. After each permutation, it will be checked if the array is sorted or not. If the array is found sorted, the function returns the array or the permutation repeats.

Code:

Program in C++

// program in CPP to implement BOGO sort.
#include<bits/stdc++.h>
using namespace std;
bool sorted(int array[], int n)
{
	while ( n > 1 )
		if (array[n] < array[n-1])
			return false;
n--;
	return true;
}
void bn (int array[], int n)
{
	for (int i=0; i < n; i++)
		swap( array[i], array[rand() % n]);
}
void bogosort(int a[], int n)
{
	
	while ( !sorted(a, n) )
		bn(a, n);
}
int main()
{
	int a[] = { 2, 3, 0, 8, 4, 1, 7, 5, 6 };
	int n ;
cin>> n;
	bogosort(a, n);
	printf("Sorted array :\n");
	for (int i=0; i<n; i++)
		printf( "%d ", a[i]);
	printf("\n");


	return 0;
}

Program in Java:

// program in java to implement BOGO sort.
public class BogoS
{
	
	void bogoSort(int[] array)
	{
		
		while ( isSorted ( array ) == false)
			shuffle(array);
	}
	void shuffle(int[] a)
	{
		
		for (int i=1; i <= n; i++)
			swap(a, i, (int)(Math.random()*i));
	}
	void swap(int[] a, int i, int j)
	{
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	boolean isSorted(int[] array)
	{
		for (int i=1; i<array.length; i++)
			if (array[i] < array[i-1])
				return false;
		return true;
	}
	void printArray(int[] arr)
	{
		for (int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
		System.out.println();
	}


	public static void main(String[] args)
	{
		
		int[] a = { 2, 3, 0, 8, 4, 1, 7, 5, 6 };
		BogoSort ob = new BogoSort();


		ob.bogoSort(a);


		System.out.print("Sorted array: ");
		ob.printArray(a);
	}
}

Program in C#:

// C# implementation of Bogo Sort
using System;
class jtp
{
	static void Swap<T>(ref T LHS, ref T RHS)
	{
		T temp;
		temp = 
LHS;
		LHS = RHS;
		RHS = temp;
	}
	
	public static bool isSorted(int[] a, int n)
	{
		int i = 0;
		while(i<n-1)
		{
			if(a[i]>a[i+1])
				return false;
			i++;
		}
		return true;
	}
		
	public static void shuffle(int[] a, int n)
	{
		Random rnd = new Random();
		for (int i=0; i < n; i++)
			Swap(ref a[i], ref a[rnd.Next(0,n)]);
	}
	
	public static void bogosort(int[] a, int n)
	{
		
		while ( !isSorted(a, n) )
			shuffle(a, n);
	}
	
	public static void printArray(int[] a, int n)
	{
		for (int i=0; i<n; i++)
			Console.Write(a[i] + " ");
		Console.Write("\n");
	}
	
	static void Main()
	{
		int[] a = {2, 3, 0, 8, 4, 1, 7, 5, 6};
		int n = a.Length;
		bogosort(a, n);
		Console.Write("Sorted array :\n");
		printArray(a,n);
	}
}

Program in Python:

# Program in python to implement BOGO sort.
import random
def bogoSort(a):
	n = len(a)
	while (is_sorted(a)== False):
		shuffle(a)
def is_sorted(a):
	n = len(a)
	for i in range(0, n-1):
		if (a[i] > a[i+1] ):
			return False
	return True
def shuffle(a):
	n = len(a)
	for i in range (0,n):
		r = random.randint(0,n-1)
		a[i], a[r] = a[r], a[i]
a = [2, 3, 0, 8, 4, 1, 7, 5, 6]
Bogost(a)
print("Sorted array :")
for i in range(len(a)):
	print ("%d" %a[i]),

Output:

[0, 1, 2, 3, 4, 5, 6, 7, 8]

Complexity Analysis: -

Time complexity-

1. Best case: O (n) [when the array is sorted]
2. Average case: O (n*n!)
3. Worst case: O(8) [ the number of permutations may be infinite]

Space complexity-

Here, we need only constant memory. So, space complexity will be O ( 1 ).