Programa Python para BogoSort o Permutation Sort

BogoSort, también conocido como clasificación por permutación, clasificación estúpida, clasificación lenta, clasificación de escopeta o clasificación de mono, es un algoritmo particularmente ineficaz basado en el paradigma de generación y prueba. El algoritmo genera sucesivamente permutaciones de su entrada hasta que encuentra una que está ordenada. ( Wiki ) 
Por ejemplo, si se utiliza bogosort para ordenar una baraja de cartas, consistiría en comprobar si la baraja estaba en orden y si no lo estaba. , uno tiraría la baraja al aire, recogería las cartas al azar y repetiría el proceso hasta que se ordenara la baraja. 
Pseudocódigo: 
 

while not Sorted(list) do
    shuffle (list)
done

# Python program for implementation of Bogo Sort
import random
 
# Sorts array a[0..n-1] using Bogo sort
def bogoSort(a):
    n = len(a)
    while (is_sorted(a)== False):
        shuffle(a)
 
# To check if array is sorted or not
def is_sorted(a):
    n = len(a)
    for i in range(0, n-1):
        if (a[i] > a[i+1] ):
            return False
    return True
 
# To generate permutation of the array
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]
 
# Driver code to test above
a = [3, 2, 4, 1, 0, 5]
bogoSort(a)
print("Sorted array :")
for i in range(len(a)):
    print ("%d" %a[i]),

Producción: 
 

Sorted array :
0
1
2
3
4
5

Complejidad del tiempo:

Peor caso: O(∞) (dado que este algoritmo no tiene límite superior)
Caso promedio: O(n*n!)
Mejor caso: O(n)(cuando la array dada ya está ordenada)

Espacio auxiliar: O(1)
Consulte el artículo completo sobre BogoSort o Permutation Sort para obtener más detalles.