BogoSort o clasificación por permutación

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

Ejemplo:

Consideremos una array de ejemplo ( 3 2 5 1 0 4 )
4 5 0 3 2 1 (1er barajado)
4 1 3 2 5 0 (2do barajado)
1 0 3 2 5 4 (3er barajado)
3 1 0 2 4 5 ( 4to barajado)
1 4 5 0 3 2 (5to barajado)
.
.
.
0 1 2 3 4 5 (enésimo barajado)—— Array ordenada

Aquí, n es desconocido porque el algoritmo no sabe en qué paso se ordenará la permutación resultante.

// C++ implementation of Bogo Sort
#include<bits/stdc++.h>
using namespace std;
  
// To check if array is sorted or not
bool isSorted(int a[], int n)
{
    while ( --n > 1 )
        if (a[n] < a[n-1])
            return false;
    return true;
}
  
// To generate permutation of the array
void shuffle(int a[], int n)
{
    for (int i=0; i < n; i++)
        swap(a[i], a[rand()%n]);
}
  
// Sorts array a[0..n-1] using Bogo sort
void bogosort(int a[], int n)
{
    // if array is not sorted then shuffle
    // the array again
    while ( !isSorted(a, n) )
        shuffle(a, n);
}
  
// prints the array
void printArray(int a[], int n)
{
    for (int i=0; i<n; i++)
        printf("%d ", a[i]);
    printf("\n");
}
  
// Driver code
int main()
{
    int a[] = {3, 2, 5, 1, 0, 4};
    int n = sizeof a/sizeof a[0];
    bogosort(a, n);
    printf("Sorted array :\n");
    printArray(a,n);
    return 0;
}

// Java Program to implement BogoSort
public class BogoSort
{
    // Sorts array a[0..n-1] using Bogo sort
    void bogoSort(int[] a)
    {
        // if array is not sorted then shuffle the
        // array again
        while (isSorted(a) == false)
            shuffle(a);
    }
  
    // To generate permutation of the array
    void shuffle(int[] a)
    {
         // Math.random() returns a double positive
         // value, greater than or equal to 0.0 and
         // less than 1.0.
         for (int i=1; i <= n; i++)
             swap(a, i, (int)(Math.random()*i));
    }
  
    // Swapping 2 elements
    void swap(int[] a, int i, int j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
  
    // To check if array is sorted or not
    boolean isSorted(int[] a)
    {
        for (int i=1; i<a.length; i++)
            if (a[i] < a[i-1])
                return false;
        return true;
    }
  
    // Prints the array
    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)
    {
        //Enter array to be sorted here
        int[] a = {3, 2, 5, 1, 0, 4};
        BogoSort ob = new BogoSort();
  
        ob.bogoSort(a);
  
        System.out.print("Sorted array: ");
        ob.printArray(a);
    }
}

# 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]),

// C# implementation of Bogo Sort
using System; 
    
class GFG 
{ 
    // To Swap two given numbers
    static void Swap<T>(ref T lhs, ref T rhs)
    {
        T temp;
        temp = lhs;
        lhs = rhs;
        rhs = temp;
    }
      
    // To check if array is sorted or not 
    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;
    } 
        
    // To generate permutation of the array 
    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)]); 
    } 
        
    // Sorts array a[0..n-1] using Bogo sort 
    public static void bogosort(int[] a, int n) 
    { 
        // if array is not sorted then shuffle 
        // the array again 
        while ( !isSorted(a, n) ) 
            shuffle(a, n); 
    } 
        
    // prints the array 
    public static void printArray(int[] a, int n) 
    { 
        for (int i=0; i<n; i++) 
            Console.Write(a[i] + " "); 
        Console.Write("\n"); 
    } 
      
    // Driver code
    static void Main() 
    { 
        int[] a = {3, 2, 5, 1, 0, 4}; 
        int n = a.Length; 
        bogosort(a, n); 
        Console.Write("Sorted array :\n"); 
        printArray(a,n); 
    }
    //This code is contributed by DrRoot_
}

Producción:

Sorted array :
0 1 2 3 4 5 

Complejidad del tiempo:

• Peor caso: O(∞) (ya 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)

Echa un vistazo al curso de autoaprendizaje de DSA

Este artículo es una contribución de Rahul Agrawal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.