/*
   An animated quick sort program.  Based on the recursive Quicksort
	algorithm in "Algorithms + Data Structures = Programs" by Niklaus Wirth,
	Prentice-Hall, Inc., 1976,  ISBN 0-13-022418-9.  See chapter 2, section
	2.2.6.

	Note that there are better ways of actually implementing the Quicksort
	algorithm.

	If you have a version of the compiler prior to TC++, you'll need to
	replace the calls to _setcursortype() with something else (or nothing).

	Released to the public domain by the author.
	Gary M. Blaine   CIS 70007,4659
*/

#include <stdlib.h>
#include <conio.h>
#include <time.h>
#include <bios.h>
#include <dos.h>

/* function prototypes */
void Quicksort(char* letters, int left, int right);
void inc(int* n);
void dec(int* n);
void display(char* letters, int i, int j);
void init_arrows(int i, int j);
void swap(char* letters, int i, int j);

#define SIZE 40

int main(void)
{
   char letters[SIZE];
   int  i;

   randomize();
	_setcursortype(_NOCURSOR);		
   clrscr();

   for(i = 0; i < SIZE; i++)                 /* initialize the array */
      letters[i] = random(26) + 'A';

   display(letters, 0, SIZE-1);              /* display the array */

   Quicksort(letters, 0, SIZE-1);            /* sort the array */

   gotoxy(1, 3);
	_setcursortype(_NORMALCURSOR);
   return 0;
}

/* sort an array of letters */
void Quicksort(char* letters, int left, int right)
{
   int  i, j;
   char x;

   /* display initial left and right pointers */
   init_arrows(left, right);

   i = left;
   j = right;
	x = letters[(left+right) / 2];

   /* do the partition */
   do
      {
      while(letters[i] < x)  inc(&i);
      while(letters[j] > x)  dec(&j);
      if(i <= j)
         {
         swap(letters, i, j);
         inc(&i);
         dec(&j);
         }
      }
   while(i <= j);

   /* sort left partition */
   if(left < j)
      Quicksort(letters, left, j);

   /* sort right partition */
   if(i < right)
      Quicksort(letters, i, right);

   /* clear away the little arrow pointers */
   gotoxy(1, 1);
   clreol();
}

/* increment a variable and update arrow position */
void inc(int* n)
{
   int row = 1;
   int col = *n * 2 + 1;

   gotoxy(col, row);       /* get rid of little arrow */
   putch(' ');

   (*n)++;                 /* increment the variable in calling function */

   col = *n * 2 + 1;       /* display the new arrow location */
   gotoxy(col, row);
   putch(0x19);            /* a down pointing arrow */

   delay(100);
}

/* decrement a variable and update arrow position */
void dec(int* n)
{
   int row = 1;
   int col = *n * 2 + 1;

   gotoxy(col, row);       /* get rid of little arrow */
   putch(' ');

   (*n)--;                 /* decrement the variable in calling function */

   col = *n * 2 + 1;       /* display the new arrow location */
   gotoxy(col, row);
   putch(0x19);            /* a down pointing arrow */

   delay(100);
}

/* display the array */
void display(char* letters, int i, int j)
{
   int n;
   int row = 1 + 1;

   for(n=i; n<=j; n++)
      {
      gotoxy(n*2+1, row);
      putch(letters[n]);
      }
}

/* swap array elements */
void swap(char* letters, int i, int j)
{
   int row  = 2;
   int rowi = 3;
   int rowj = 4;

   int mi, mj;

   char ci = letters[i];      			/* remember the characters at i, j */
   char cj = letters[j];

   char tmp   = letters[i];            /* swap array elements */
   letters[i] = letters[j];
   letters[j] = tmp;

   /* move ith character down */
   for(mi = row; mi < rowi; mi++)   
      {
      gotoxy(i*2+1, mi);
      putch(' ');
      gotoxy(i*2+1, mi+1);
      putch(ci);
      delay(100);
      }

   /* move jth character down */
   for(mj = row; mj < rowj; mj++)   
      {
      gotoxy(j*2+1, mj);
      putch(' ');
      gotoxy(j*2+1, mj+1);
      putch(cj);
      delay(100);
      }

   /* move characters horizontally */
   for(mi=i*2+1, mj=j*2+1; mi<j*2+1; mi++, mj--)
      {
      gotoxy(mi, rowi);
      putch(' ');
      gotoxy(mj, rowj);
      putch(' ');

      gotoxy(mi+1, rowi);
      putch(ci);
      gotoxy(mj-1, rowj);
      putch(cj);
      delay(20);
      }

   /* move ith character back up into jth position */
   for(mi = rowi; mi > row; mi--)
      {
      gotoxy(j*2+1, mi);
      putch(' ');
      gotoxy(j*2+1, mi-1);
      putch(ci);
      delay(100);
      }

   /* move jth character back up into ith position */
   for(mj = rowj; mj > row; mj--)
      {
      gotoxy(i*2+1, mj);
      putch(' ');
      gotoxy(i*2+1, mj-1);
      putch(cj);
      delay(100);
      }

   /* let the user quit by hitting any key */
   if( bioskey(1) )
      {
      bioskey(0);
      gotoxy(1, 3);
      cputs("User terminated");
		_setcursortype(_NORMALCURSOR);
      exit(1);
      }
}

/* display the little arrow pointers */
void init_arrows(int i, int j)
{
   gotoxy(1, 1);        /* get rid of any existing arrows */
   clreol();

   gotoxy(i*2+1, 1);
   putch(0x19);         /* a down pointing arrow */

   gotoxy(j*2+1, 1);
   putch(0x19);         /* a down pointing arrow */
}