#include <conio.h>
#include <stdlib.h>
#include <stdio.h>
#define  true  1
#define  false 0

/* This is a demonstration of various sorting techniques
   An array is entered by the user, and  the computer
   uses all the algorithms discussed in the course to sort
   it.  This allows for comparison of the efficiency of
   methods. */


/* ncomp and nswap are global variables, and each sorting function
   will update them with the number of comparisons and swaps it did
   when it was called. */
short ncomp, nswap;


void swap(k, l)
short *k, *l;
{
  short temp;

  temp = *k;
  *k = *l;
  *l = temp;
}


void sort1(list, n)
short *list;
short n;
{
  short i, j;

  ncomp = 0;
  nswap = 0;
  for (i = 0; i <= n - 2; i++) {
    for (j = i + 1; j < n; j++) {
      ncomp++;
      if (list[i] > list[j]) {
     swap(&list[i], &list[j]);
     nswap++;
      }
    }
  }
}


void bsort1(list, n)
short *list;
short n;
{
  short i, k;

  ncomp = 0;
  nswap = 0;
  do {
    k = 0;
    for (i = 1; i < n; i++) {
      ncomp++;
      if (list[i - 1] > list[i]) {
     swap(&list[i - 1], &list[i]);
     nswap++;
     k = 1;
      }
    }
  } while (k != 0);
}


void bsort2(list, n)
short *list;
short n;
{
  short last, k, i;

  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]);
     nswap++;
     k = i;
      }
    }
    last = k;
  } while (k != 0);
}


void bsortr(list, l, m, k)
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]);
      nswap++;
      *k = i;
    }
  }
  *m = *k;
}


void bsortl(list, l, m, k)
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]);
      nswap++;
      *k = i;
    }
  }
  *l = *k;
}


void shake(list, n)
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);
    if (k != 0)
      bsortl(list, &left, &right, &k);
    i++;
  } while (i <= n && k != 0);
}



void shell(short list[], short n)
{
  short temp, a, b, h;
  nswap=0;
  ncomp=0;

  /* Outer loop varies the interval size */
  for (h = n/2 ; h > 0; h = h/2){

    /* This loop considers all sequences for a given interval size */
    for (a = h; a < n; a = a + 1){

      /* This loop sorts each individual sequence */
      b = a-h;
      while( b >= 0 ){
	 if( list[b] > list[b+h] ){
	    temp = list[b];
	    list[b]=list[b+h];
	    list[b+h]=temp;
	    nswap++;
	 }
      b = b - h;
      ncomp++;
      }
    }
  }
}


void printinfo()
{
  printf("number of comparisons = %5d\n", ncomp);
  printf("number of exchanges = %5d\n", nswap);
}

int main(void)

{
    short initial_list[1000];
    short list[1000];
    short n, i;

    clrscr();
    printf("This is a demonstration of sorting algorithms. \n\n");
    printf("  You will be prompted to enter how large of an array you\n");
    printf("to try sorting, and then enter the elements one by one.\n");
    printf("Then the computer will sort them using all the algorithms\n");
    printf("discussed under this section in the book, and will give\n");
    printf("a comparison of how efficient each algorithm was.\n\n");

    printf("Enter No. of Elements : ");
    scanf("%hd", &n);

    /* Now the computer must read in all the elements of the array.
       It will store them in two arrays, called initial_list[] and
       list[].  This is done so that after one technique sorts the
       list, there is a copy of the original, unsorted list for the
       next technique to work on, etc. */

    for( i=0; i<n; i=i+1){
       printf("Enter Element #%hd:",(i+1));
       scanf("%hd",&initial_list[i]);
       list[i] = initial_list[i];
       }

    sort1(list, n);
    printf("Selection sort : \n");
    printinfo();

    for( i=0; i<n; i++ )
       list[i] = initial_list[i];
    bsort1(list, n);
    printf("Bubble sort 1 : \n");
    printinfo();

    for( i=0; i<n; i++ )
       list[i] = initial_list[i];
    bsort2(list, n);
    printf("Bubble sort 2 (improved) : \n");
    printinfo();

    for( i=0; i<n; i++ )
       list[i] = initial_list[i];
    shake(list, n);
    printf("Cocktail shaker : \n");
    printinfo();

    for( i=0; i<n; i++ )
       list[i] = initial_list[i];
    shell(list, n);
    printf("Shell sort: \n");
    printinfo();

  return(0);
}

/* End. */