/************************************************************************/
/* 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 quick_sort(int *data, int left, int right);
int  partition(int *data, int left, int right);
void display_data(int *data, int n);
void init_data(int *data, int n, int option);
void display_time(char *str);
void swap(int *data, int fpos, int spos);
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 */
  quick_sort(data, 0, N-1);               /* 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);
}


/************************************************************************/
/* Function to change value of data[fpos] and data[spos]                */
/************************************************************************/
void swap(int *data, int fpos, int spos) {
  int temp;

  temp=data[fpos];
  data[fpos]=data[spos];
  data[spos]=temp;
}

void quick_sort(int *data, int left, int right)  {
  int pivot;

  if(left < right)   {
    pivot=partition(data, left, right);
    quick_sort(data, left, pivot-1);
    quick_sort(data, pivot+1, right);
  }
}

int partition(int *data, int left, int right)  {
  int i=left, j=right;

  while(1) {
    while(data[i]< data[right])
      i++;
    while((data[j]>=data[right])&&(j>=0) )
      j--;
    if(i>=j)
      break;
    swap(data, i, j);
  }
  swap(data, i, right);
  return i;
}