/*BOGOSORT, o pior algoritmo ja existente O(n*n!)*/
/*Pra falar a verdade ele vai se apresentar... hehehehe*/
/*por Brivaldo Jr*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int main(int argc, char *argv[])
{
  register int i;                  /*Aqui estão as variaveis que eu preciso pra me ordenar...*/
  int FLAG=0, aux, mul;            /*Essas servem pra me controlar, ai que beleza!*/
  int *vet, TAM;                   /*Pra poder alocar o vetor que vao ter os numeros*/
  unsigned long int comp=0, troc=0;/*Essas contam o numero de vezes que eu troco e comparo*/
  clock_t ini, end;                /*Estas aqui sao pra marcar o tempo !*/
  float seg=0;
  if(argc<2)
    {
      printf("\nTem que entrar o tamanho do vetor dos numeros.\n");
      printf("Assim, o: bogosort <NUMERO>\n\n");
      exit(0);
    }
  TAM=atoi(argv[1]);
  vet=(int *)malloc(sizeof(int)*TAM);
  srand(time(0));                  /*Randomizo o tempo no Linux e no Windows*/
  ini=clock();                     /*Inicio o relógio pra mostrar minha velocidade*/

  for(i=0;i<TAM;i++)               /*Randomizo os meus valores*/
  {
    vet[i]=rand()%(2*TAM);
    printf("%d ",vet[i]);
  }
  printf("\n");
  while(!FLAG)
    {
      i=0;
      FLAG=1;                      /*Eu digo que to ordenado*/
      while(i<TAM-1 && FLAG)       /*Vou ver se eu to ordenado direitinho...*/
	{
	  if(vet[i]>vet[i+1])      /*Eu to ordenado ?*/
            FLAG=0;                /*Nao!*/
          comp++;                  /*Cada comparacao vale OURO!*/
          i++;                     /*E sigo inte teRRRminaRR...*/
	}
      if(!FLAG)                    /*Se eu nao to ordenado eu entro aqui!*/
	{
	  for(i=0;i<TAM;i++)       /*Dai, eu me embaralho denovo!!!*/
	    {
              mul=rand()%TAM;      /*MUL recebe um valor aleatorio*/
	      aux=vet[i];          /*Guardo o valor do vet[i] em aux, de auxiliar né!*/
	      vet[i]=vet[mul];     /*Ponho o louco do vet[MUL] em vet[i]*/
	      vet[mul]=aux;        /*E destroco o vet[MUL] com o aux*/
	      troc++;              /*Tem que contar as trocas, hehehe...*/
	    }
	}
    }

  end=clock();                     /*Depois de tanto trabalho acabou!*/

  for(i=0;i<TAM;i++)
    printf("%d ",vet[i]);
  printf("\n");
  seg=((double)(end-ini)/CLOCKS_PER_SEC);
  printf("\nTempo: %.3f\nComparacoes: %lu\nTrocas: %lu\n\n",seg,comp, troc);

  return (0);  
}