/************************************************************************/
/* Program sort technique                                               */
/************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <dos.h>
#include <alloc.h>

/* (!) Define Number of data to sort : <= 3000 */
#define  N   100

void insertion_sort(int *data, int totaldata);
void display_data(int *data, int n);
void init_data(int *data, int n, int option);
void display_time(char *str);
extern unsigned _stklen=(unsigned)0xFFFF;

void main(void)  {
  int data[N];

  init_data(data, N, 1);                  /* (!) set data value to sort  */
  display_data(data, N);                  /* display data before sorting */
  display_time("Before sorting time : "); /* display time before sorting */
  insertion_sort(data, N);                /* sorting data                */
  display_data(data, N);                  /* display data after sorting  */
  display_time("After sorting time  : "); /* display time after sorting  */
}

/************************************************************************/
/* Function initial value of data to test sorting function              */
/* Parameter : *data  - address of data array variable                  */
/*             n      - number of data                                  */
/*             option - define option to generate data by               */
/*                      1 for descending data[ N-1, ..., 1, 0]          */
/*                      2 for ascending data [ 0, 1, ..., N-1]          */
/*                      3 for random data [ {0 to N-1},..,{0 to N-1} ]  */
/************************************************************************/
void init_data(int *data, int n, int option)  {
  int i;

  randomize();
  for(i=0; i< n; i++)
  switch(option)  {
    case 1:  data[i]=n-i-1;
             break;
    case 2:  data[i]=i;
             break;
    default: data[i]=random(n);
             break;
  }
}

/************************************************************************/
/* Function display value of array data for n items                     */
/************************************************************************/
void display_data(int *data, int n)  {
  int i;

  printf("\n");
  for(i=0; i<n; i++)
    printf(" %4d", data[i]);
  printf("\n");
}

/************************************************************************/
/* Function display current time of computer system                     */
/* Parameter : *str - string to display                                 */
/* Format of display  [ HH:MM:SS:MM ]                                   */
/*                      H is Hour                                       */
/*                      M is Minute                                     */
/*                      S is Second                                     */
/*                      M is Milli second                               */
/************************************************************************/
void display_time(char *str) {
  struct time curtime;

  gettime(&curtime);
  printf(" %s %d:%d:%d:%d\n", str, curtime.ti_hour, curtime.ti_min,
	 curtime.ti_sec, curtime.ti_hund);
}

void insertion_sort(int *data, int totaldata)  {
  int tmp, i, j;

  for(i=1; i<totaldata; i++)  {
    tmp=data[i];
    j=i-1;
    while((j>=0)&&(data[j]>tmp))  {
      data[j+1]=data[j];
      j--;
    }
    data[j+1]=tmp;
  }
}