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
Java
// 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 = 0; i < a.length; 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);
}
}
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA