/*
  Shell Sort.
*/

#include <stdio.h>
#define true 1     /* Constant declaration */
#define false 0

typedef int listarray[1000]; /* Variable type declaration */

listarray list;           /* Global variable declaration */
int ncomp, nswap, n, i;

void swap(int *k, int *l)  /* Swap function declaration */
{
  int temp;

  temp = *k;
  *k = *l;
  *l = temp;
}  /* End swap function */


void shell(int *list, int n)   /* Shell subroutine declaration */
{
  int m, i, j;
  int done;

  ncomp = 0;
  nswap = 0;
  m = n;
  do
  {
    m = (m + 2) / 3;
    for (i = m + 1; i <= n; i++)
    {
      j = i;
      done = false;
      while (j > m && !done) {
     ncomp++;
     if (list[j - m - 1] < list[j - 1]) done = true;
     else
     {
     swap(&list[j - 1], &list[j - m - 1]); /* Call of Swap function */
     nswap++;
     }
     j -= m;
      }
    }
  }while(m > 1);
}


main()
{
  /*  Declaration Statements  */
  int n;
  int list[100];
  int FORLIM;

  clrscr();
  printf("C95.C -> Shell sort program\n");

  /*  Assignment Statements  */
  printf("Enter the number of elements: ");
  scanf("%hd", &n);
  FORLIM = n;

  printf("Enter elements (press ""enter"" between each entry)\n");

  for (i = 1; i <= FORLIM; i++)
  {
    printf("Enter element %d: ",i);
    scanf("%hd", &list[i - 1]);
  }
  printf("\n\nBefore Sorting\n\n");

  /* Print out initial array */

  for (i = 1; i <= FORLIM; i++) printf("%5d", list[i - 1]);
  printf("\n\n");

  /*  Sort with subroutines  */

  shell(list, n);  /* Call of shell subroutine */

  /* Print out sorted array */

  printf("\nAfter Sorting\n\n");

  for (i = 1; i <= FORLIM; i++) printf("%5d", list[i - 1]);
  printf("\n\nNumber of comparisons=%3d\n", ncomp);
  printf("Number of exchanges=%3d\n\n\n", nswap);

  return(0);
}
/*  End of main Program C95 */