/*
  Cocktail shaker sort.
*/

#include <stdio.h>

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

listarray list;            /* Global Variable Declaration */
short ncomp, nswap, n, i;

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

  temp = *k;
  *k = *l;
  *l = temp;
  return(0);
}  /*  End of swap function  */


void bsortr(list, l, m, k)  /* bsortr subroutine declaration */
short *list;
short *l, *m, *k;
{
/*  Right bubble sort  */

  short i, FORLIM;

  (*m)--;
  *k = 0;
  FORLIM = *m;
  for (i = *l; i <= FORLIM; i++)
  {
    ncomp++;
    if (list[i - 1] > list[i])
    {
    swap(&list[i - 1], &list[i]);  /* Call of swap function */
    nswap++;
    *k = i;
    }
  } /* End of for{} loop */
  *m = *k;
} /* End of bsortr subroutine */


void bsortl(list, l, m, k)  /* bsortl function declaration */
short *list;
short *l, *m, *k;
{
/*  Left bubble sort  */

  short i, FORLIM;

  (*l)++;
  *k = 0;
  FORLIM = *l;
  for (i = *m; i >= FORLIM; i--)
  {
    ncomp++;
    if (list[i - 1] < list[i - 2])
    {
    swap(&list[i - 1], &list[i - 2]); /* Call of swap function */
    nswap++;
    *k = i;
    }
  } /* End of for{} loop */
  *l = *k;
} /* End of bsortl subroutine */


void shake(list, n)  /* Shake subroutine declaration */
short *list;
short n;
{
  short left, right, i, k;

  ncomp = 0;
  nswap = 0;
  left = 1;
  right = n;
  i = 1;
  do
  {
    bsortr(list, &left, &right, &k); /* Call of subroutine */
    if (k != 0)
    bsortl(list, &left, &right, &k); /* Call of subroutine */
    i++;
  } while (i <= n && k != 0); /* End of while{} loop */

} /*  End of Shake subroutine  */


main()
{
  /*  Declaration Statements  */
  short FORLIM;

  clrscr();
  printf("C94.C -> Cocktail Shaker Sort\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("Element %d : ",i);
    scanf("%hd", &list[i - 1]);
  }
  printf("Press ""Enter"" to continue...\n");
  scanf("");
  printf("\n");

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

  /*  Sort with subroutines  */

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

  /* Print results */

  printf("\nAfter Sorting\n\n");
  FORLIM = 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 C94  */