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

void dumbsort(long *a, long n);
void inssort(long *a, long n);
void gnomesort(long *a, long n);

enum { n = 16, m = 16 };

int main(int argc, char **argv)
{
  long a[n];
  bool something_failed = false;
  char *name;
  void (*sort)(long*, long);
  if (argc == 1) {
    name = "dumbsort";
    sort = dumbsort;
  } else if (argv[1][0] == 'g') {
    name = "gnomesort";
    sort = gnomesort;
  } else {
    name = "inssort";
    sort = inssort;
  }

  printf("Testing %s:\n", name);

  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) a[j] = j;

    for (int j = 0; j < n; j++) {
      int k = j + random() % (n - j);
      long t = a[k];
      a[k] = a[j];
      a[j] = t;
    }

    printf("{ ");
    for (int j = 0; j < n; j++) {
      if (j) printf(", ");
      printf("%ld", a[j]);
    }
    printf(" } → { ");

    sort(a, n);

    bool failed = false;
    long prev = -1;

    for (int j = 0; j < n; j++) {
      if (j) printf(", ");
      printf("%ld", a[j]);
      if (a[j] != prev + 1) failed = true;
      prev = a[j];
    }

    if (failed) something_failed = true;
    printf(failed ? " } FAILED\n" : " }\n");
  }

  return something_failed;
}