// Dumbsort: even simpler than Gnomesort, but takes almost N³/6
// comparisons to sort an initially-reversed list of N items.

#include <stdlib.h>
#include <stdio.h>
int comparisons;

void
dumbsort(int *p, int n)
{
  for (int tmp, i = 1; i < n; i++) {
    comparisons++;
    if (p[i] < p[i-1]) tmp = p[i], p[i] = p[i-1], p[i-1] = tmp, i = 0;
  }
}

int
main(int argc, char **argv)
{
  int n = atoi(argv[1]);
  int v[n];
  for (int i = 0; i < n; i++) v[i] = 3*(n-i);
  dumbsort(v, n);
  for (int i = 0; i < n && i < 100; i++) printf("%d ", v[i]);
  printf("\n%d comparison%s to sort %d items\n",
         comparisons, comparisons == 1 ? "" : "s", n);
  return 0;
}