ShellSort

#include <stdio.h>
#include <stdlib.h>
int *a; 
int fib(long long a){
  long long first = 0, second = 1, ans = 0;
  while (first + second < a) {
    ans = first + second;
    first = second;
    second = ans;
  }
  return ans;
}

int compare(unsigned long i, unsigned long j){
  if (a[i] < a[j]) return -1;
  if (a[i] == a[j]) return 0;
  return 1;
}
void swap(unsigned long i, unsigned long j){
  int save =a[i];
  a[i] = a[j];
  a[j] = save;
}
void shellsort(unsigned long nel,
        int (*compare)(unsigned long i, unsigned long j),
        void (*swap)(unsigned long i, unsigned long j))
{
  long long d = fib(nel);
  while (d>=1){
    int i = d;
    while (i < nel){
      int loc = i;
      while (loc-d >=0 && compare(loc-d, loc) > 0) {
        swap(loc-d,loc);
        loc-=d;
      }
    i++;
    }
    d = fib(d);
  }
}

int main(){
  int i, n; 
        scanf("%d", &n);
        a = (int*)malloc(n * sizeof(int)); 
        for (i = 0; i < n; i++) scanf("%d", a+i); 
        shellsort(n, compare, swap); 
        for (i = 0; i < n; i++) printf("%d ", a[i]); 
        printf("\n"); 
        free(a); 
        return 0; 
}