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

struct compare_state {
  long long n_compares;
  double reliability;
};


int compare(int a, int b, struct compare_state *state)
{
  int ret;
  state->n_compares++;
  ret = b < a;

  if(drand48() >= state->reliability) {
    ret = !ret;
  }
  return ret;
}

int sorted(int *ar, int len)
{
  int badness = 0;
  int len_save = len;
  while(--len) {
    if(*ar > *++ar)
      badness++;
  }
  return badness <= log(len_save);
}


struct compare_state bozosort(int *ar, int len)
{
  struct compare_state stats;
  int i, j, tmp;

  stats.reliability = .99; 
  stats.n_compares = 0;

  while(!sorted(ar, len)) {
    i = random() % len;
    j = random() % len;
    if((i < j) &&  compare(ar[i], ar[j], &stats)) {
      tmp = ar[i];
      ar[i] = ar[j];
      ar[j] = tmp;
    }
  }
  return stats;
}

int *make_random_array(int len)
{
  int *base;
  int i;
  base = malloc(sizeof(int) * len);
  for(i = 0; i < len; i++) {
    base[i] = random() % len;
  }
  return base;
}

void print_array(int *ar, int len)
{
  int i;
  printf("%d", ar[0]);
  for(i = 1; i < len; i++)
    printf(", %d", ar[i]);
  printf("\n");
}

int main(int argc, char **argv)
{
  struct compare_state stats;
  int *ar;
  int len;

  if(argc != 2) 
    len = 20;
  else
    len = atoi(argv[1]);

  ar = make_random_array(len);
  stats = bozosort(ar, len);

  print_array(ar, len);
  printf("compares: %d\n", (int)stats.n_compares);
  return 0;
}