#include <stdio.h>

static void swap (int *i, int *j) {
  int temp = *i;
  *i = *j;
  *j = temp;
}

static int newGap(int gap) {
  gap = gap * 10 / 13;
  if (gap < 1)
    gap = 1;
  if (gap == 9 || gap == 10)
    gap = 11;
  return gap;
}

void combsort(int a[], int length) {
  int gap = length;
  for (;;) {
    int swapped = 0;
    int i;
    gap = newGap(gap);
    for (i = 0; i < length - gap; i++) {
      if (a [i] > a [i + gap]) {
	swap(a + i, a + i + gap);
	swapped = 1;
      }
    }
    if (gap == 1 && !swapped)
      break;
  }
}

int main() {
  int a[] = {1, 6, 5, 3, 8, 9, 7, 2, 4, 0};
  int length = sizeof(a) / sizeof(*a);
  int i;
  combsort(a, length);
  for (i = 0; i < length; i++)
    printf("%d\n", a[i]);
}