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

#define NUMBERS 1000000

void print_arr(int[]);
void shellsort(int[], int);

void shellsort(int arr[], int n) {
  int temp;

  for (int gap = n / 2; gap > 0; gap /= 2)
    for (int i = gap; i < n; ++i)
      for (int j = i - gap; j >= 0 && arr[j] > arr[j + gap]; j -= gap) {
        temp = arr[j];
        arr[j] = arr[j + gap];
        arr[j + gap] = temp;
      }
}

int main() {
  int ind, numbers[NUMBERS];
  for (ind = NUMBERS; ind > 0; --ind) {
    numbers[ind] = rand();
  }

  shellsort(numbers, NUMBERS);
  // print_arr(numbers);
  return 0;
}

void print_arr(int numbers[]) {
  for (int ind = 0; ind < NUMBERS; ++ind) {
    if (ind >= 10 && ind % 10 == 0)
      printf("\n");
    printf("%d ", numbers[ind]);
  }
}