#include <stdio.h>
#define MAX 10

void shellSort(int array[MAX])
{
  for (int interval = MAX / 2; interval > 0; interval /= 2)
  {
    for (int index = interval; index < MAX; index++)
    {
      for (int prevIndex = index - interval, currentIndex = index; prevIndex >= 0; currentIndex -= interval, prevIndex -= interval)
      {
        if (array[prevIndex] < array[currentIndex])
          break;

        int temporary = array[prevIndex];
        array[prevIndex] = array[currentIndex];
        array[currentIndex] = temporary;
      }
    }
  }
}

void show(int index, int array[MAX])
{
    if (index != MAX)
    {
        printf("%d ", array[index]);
        show(index + 1, array);
    }
}

void main()
{
    int array[] = {3, 10, 4, 6, 8, 9, 7, 2, 1, 5};
    // int array[] = {1, 2, 3, 4, 5, 9, 7, 6, 8, 10};
    // int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    // int array[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    printf("Array\nBefore: ");
    show(0, array);

    shellSort(array);

    printf("\nAfter: ");
    show(0, array);
}