/*
  Improved version of the bubble 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;
} /*  End of swap function  */


void bsort2(list, n)  /*  bsort2 subroutine declaration  */
short *list;
short n;
{
  short last, k, i, kk;

  printf("Sorting\n");
  ncomp = 0;
  nswap = 0;
  last = n - 1;
  do {
    k = 0;
    for (i = 1; i <= last; 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 */

    for (kk = 0; kk < n; kk++) printf("%5d", list[kk]);
    putchar('\n');
    last = k;
  } while (k != 0);

} /* End of bsort2 subroutine */

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

  clrscr();
  printf("C93.C -> Improved version of the bubble sort\n");

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

  for (i = 1; i <= FORLIM; i++)
  {
    printf("Element %d : ",i); /* Read element from keyboard entry */
    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  */

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

  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 C93  */