Bogosort

Bogosort (também conhecido como CaseSort ou Estou com Sort), é um algoritmo de ordenação extremamente ineficiente. É baseado na reordenação aleatória dos elementos. Não é utilizado na prática, mas pode ser usado no ensino de algoritmos mais eficientes. Seu nome veio do engraçado termo quantum bogodynamics e, ultimamente, a palavra bogus.

Esse algoritmo é probabilístico por natureza. Se todos os elementos a serem ordenados são distintos, a complexidade esperada é . O tempo exato de execução esperado depende do quantos diferentes valores de elementos ocorrem, e quantas vezes cada um deles ocorre, mas para casos não-triviais o tempo esperado de execução é exponencial ou super-exponencial a . Ele termina pela mesma razão do teorema do macaco infinito; existe alguma probabilidade de que aconteça a permutação correta, dado que em um infinito número de tentativas fatalmente a encontrará.

Deve-se notar que com os algoritmos geradores de números pseudo-aleatórios, que têm um número finito de estados e não são realmente aleatórios, o algoritmo pode nunca terminar para certos conjuntos de valores a serem ordenados.

Bogosort é um algoritmo de ordenação não estável.

Exemplo

Para se ordenar um baralho usando-se este Algoritmo, seria necessário jogar as cartas ao ar, juntá-las aleatoriamente, e então verificar se as mesmas estão ordenadas.

Algoritmo

 
função bogosort(array)
  enquanto não está_ordenado(array)
    array := permutação_aleatória(array)

Implementações

C

 
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
bool is_sorted(int *a, int n)
{
  while ( --n >= 1 ) {
    if ( a[n] < a[n-1] ) return false;
  }
  return true;
}
 
void shuffle(int *a, int n)
{
  int i, t, r;
  for(i=0; i < n; i++) {
    t = a[i];
    r = rand() % n;
    a[i] = a[r];
    a[r] = t;
  }
}
 
void bogosort(int *a, int n)
{
  while ( is_sorted(a, n) ) shuffle(a, n);
}
 
int main()
{
  int numbers[] = { 1, 10, 9,  7, 3, 0 };
  int i;
 
  bogosort(numbers, 6);
  for (i=0; i < 6; i++) printf("%d ", numbers[i]);
  printf("\n");
}

C++

 
 #include <algorithm>
 #include <vector>
 
 template<class T>
 void bogosort(std::vector<T>& array)
 {
     while (! is_sorted(array))
         std::random_shuffle(array.begin(), array.end());
 }
 
 template<class T>
 bool is_sorted(const std::vector<T>& array)
 {
     for (typename std::vector<T>::size_type i = 1; i < array.size(); ++i)
         if (array[i] < array[i-1]) return false;
     return true;
 }

Java

 
public static void bogoSort(int length, int range) {
	int []array = randomIntArray(length,range);
		
	while (! isSorted(array))
		array = randomArray(array);
		
	for (int i = 0; i < array.length; i++) {
		System.out.print(array[i] + " ");
	}
		
}
	
private static boolean isSorted(int [] array)
{
    for (int i = 0; i < (array.length - 1); ++i) {
    	if (array[i] > array[i+1])
    		return false;
    }
        
    return true;
}
	
private static int [] randomArray(int [] array) {
		 
    int size = array.length;
    int[] indices = new int[size]; 
    for (int i=0; i<size; i++) {
    	indices[i] = i;
    }
	      
    Random random = new Random();
    for (int i = 0; i < size; i++) {
      boolean unique = false;
      int nRandom = 0;
      while (!unique) {
        unique = true;
        nRandom = random.nextInt(size);
        for (int j = 0; j < i; j++) {
          if (indices[j] == nRandom) {
             unique = false;
             break;
          }
        }
      } 
	 
      indices[i] = nRandom; 
    }
	 
    int [] result = new int[size];
        for (int k = 0; k < size; k++) {
    result[indices[k]] = array[k];
    }

    return result;
}
	
private static int[] randomIntArray(int length, int n)
{
  int[] a = new int[length];
  Random generator = new Random();
  for (int i = 0; i < a.length; i++)
  {
      a[i] = generator.nextInt(n);
  }
  return a;
}

Pascal

 
 program bogosort (input, output);
 const max=10;   {*Tamanho do vetor *}
 type vetor=array[1..max] of integer;
 var lista, lista1: vetor;
     i: integer;
     j: boolean;
     pos: integer;
 
 	 function teste(var proto: vetor): boolean;     {*Verifica se o vetor NÃO está ordenado.*}
 	 var i: integer;
 	 begin
 		 teste:=true;
 		 for i:=2 to max do
 			 if (proto[i]<proto[i-1]) then
 				 break;
 		 if (i=max) and (proto[max]>=proto[max-1]) then
 			 teste:=false;
 	 end;
 
 begin
 	 randomize;    {*Inicializa o gerador de numeros aleatórios *}
 	 writeln('Escreva abaixo os ', max,' elementos do vetor:');
 	 for i:=1 to max do
 	 begin
 		 read(lista[i]);  
 		 lista1[i]:=lista[i];
 	 end;
 	 for i:=1 to max do           {*Escreve o vetor recebido *}
 		 write(lista1[i],' ');
 	 writeln;
 	 while teste(lista1) do    {*Enquanto o vetor nao esta ordenado...*}
 	 begin
 		 j:=true;
 		 for i:=1 to max do     {*Inicializa o vetor auxiliar *}
 			 lista1[i]:=0;
 		 for i:=1 to max do   {* Este loop preenche aleatoriamente o vetor auxiliar *}
 		 begin
 			 j:=true;
 			 while j do {* Este while garante que nenhum dado será sobrescrito *}
 			 begin
 				 pos:= random(max)+1;    {* Gera posição aleatória *}
 				 if lista1[pos]=0 then     {*Garante que a posição não está ocupada *}
 				 begin
 	 				 lista1[pos]:=lista[i];
 					 j:=false;
 				 end;
 			 end;
 		 end;
 		 for i:=1 to max do	{* Imprime na tela a tentativa *}	
 			 write(lista1[i],' ');
 		 writeln;		
 	 end;
 	 write('A LISTA FOI ORDENADA!');
 end.

Perl

 
 use List::Util qw(shuffle);
 
 sub bogosort {
    my @a = @_;
    my @sorted = sort @a;
    while("@a" ne "@sorted") {
       @a = shuffle(@a);
    }
    return @a;
 }

Python

 
import random

def bogosort(nums):
    def isSorted(nums):
        if len(nums) < 2:
            return True
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                return False
        return True

    while not isSorted(nums):
        random.shuffle(nums)
    return nums
num1 = input('Input  comma separated numbers:\n').strip()
nums = [int(item) for item in num1.split(',')]
print(bogosort(nums))

[1]

Ruby

 
def bogosort(seq)
 seq.shuffle! while not seq.each_cons(2).all? {|a,b| a <= b}
end

Fluxograma

Ver também

Referências
  1. «Python Data Structures and Algorithms: Sort a list of elements using Bogosort sort». w3resource (em inglês). Consultado em 24 de setembro de 2021

Ligações externas
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.