/*
  Program to animate various sorting algorithms
 
  Author:  Tim Rolfe
 
  Animation can be paused in real-time and the speed of the animation
  can also be altered as the program runs:
*/
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
 
#ifdef __TURBOC__
#include <dos.h>      /* delay() */
#include <conio.h>    /* gotoxy() and clrscr(), if not included */
#include <alloc.h>
#else
/* #include <malloc.h>    /* VAX only */
#define delay(milli) usleep(milli*1000L)
#define RAND_MAX 0x7FFFL
#define random(num)     (int)(((long)(rand()&RAND_MAX)*(num))/(RAND_MAX+1))
#define randomize()     srand((unsigned)time(NULL))
void gotoxy (int, int);
void clrscr (void);
#endif
 
/* ----- Sorting subprograms (and function) ----- */
 
void Bubble (int, int *);             /*  Standard bubble sort          */
void Shaker (int, int *);             /*  Alt. direction bubble         */
void SelSort (int, int *);            /*  Selection sort                */
void InSort  (int, int *, int);       /*  Insertion sort, step h        */
void ShellSort (int, int *);          /*  Shell's opt. of InSort        */
void HeapSort  (int, int *);          /*  Heap sort, which uses:        */
void DownHeap  (int, int, int *);     /*  Regen. heap from Top to Bot   */
void MsortR    (int, int, int *);     /*  Recursive merge sort          */
void MsortI    (int, int *);          /*  Iterative merge sort          */
void MsortN    (int, int *);          /*  "Natural" merge sort          */
void Merge     (int, int, int, int *);/*  Array merge, with animation   */
void BinSort   (int, int *);          /*  Radix sort (base 2)           */
void QkSort     (int, int, int *);    /*  Standard QuickSort            */
int  Partition (int, int, int *);     /*  used by QuickSort             */

/* ----- Searching functions and driver ----- */
 
void Search_Demo (int, int *);        /*  Driver to search X            */
int  LinSrch     (int, int, int *);   /*  Linear/sequential search      */
int  BinSrch     (int, int, int *);   /*  Binary search */
 
/* ----- Statistics of the sort, and comparison-counter ----- */
 
void Stats(void);                     /*  Report compares, moves, swaps */
int  Compare     (int *, int, int);   /*  Compare AND count N compares  */

/* ----- Animation subprograms ----- */
 
void Init_Screen (int *, int, char *);/*  Display initial state         */
void Update (int, int, int *);        /*  Position value displays       */
void Clear_Pts (int, int, int *);     /*  Clear lower display area      */
void Pause(void);                     /*  Slow down the animation       */
void SwapIt      (int, int, int*);    /*  Animate swapping two cells    */
void ToHold      (int, int, char *);  /*  Move value TO hold area       */
void MoveIt      (int, int, int);     /*  Move value within array       */
void FromHold    (int, int);          /*  Move value FROM hold area     */
void Flag        (int, char *);       /*  Attach a flag to a cell       */
void UnFlag      (int, char *);       /*  Remove such a flag            */
char *Replicate  (int, char);         /*  String of N characters        */

/* ----- Exerciser utility routines  */

void Fill (int *, int);               /*  Fill array with data          */
void Copy (int *, int *, int);        /*  Copy one array to another     */
int Run_Opt (void);                   /*  Dialog on where to start      */

int   Bottom_Position, N_Swaps, N_Moves, N_Compares;
float Col_Adjust;
long  Loop_Lim;

int  *Scratch;
int   CharIn;      /* Just to avoid a couple of diagnostics */

int main()
{
   int *X, *Hold;
   int  N_Elements, Loop_Hold;
   char Ans[10];

   clrscr();
   gotoxy(20, 9);

   printf ("How large an array?  Default -- 26  ");
   fgets  (Ans, 10, stdin);
   N_Elements = atoi(Ans);
   if (N_Elements <= 0 || N_Elements > 26)
   N_Elements = 26;
   gotoxy (41, 9);
   printf ("%d%s", N_Elements, Replicate(30, ' '));
 
   X    = (int *) calloc ( N_Elements+1, sizeof *X);
   Hold = (int *) calloc ( N_Elements+1, sizeof *X);
   Scratch = (int *) calloc ( N_Elements+1, sizeof *X);
 
   gotoxy (10, 12);
   printf ("Delay loop iteration count (0 for manual):  ");
   fgets  (Ans, 10, stdin);
   Loop_Lim = atoi(Ans);

   if (!Loop_Lim)
   {
      gotoxy (10, 13);
      printf ("Press Enter to advance the simulation.");
      gotoxy (10, 14);
      printf ("Hold the key down to move more quickly.");
   }

   gotoxy (10, 16);
   printf ("At the end of an animation you are prompted for an Enter;");
   gotoxy (10, 17);
   printf ("to change the delay loop count, enter new value here.");
   gotoxy (10, 19);
   printf ("Press Enter to continue:  ");
   while ( (CharIn = getchar()) != '\n')
      ;

   Bottom_Position = 25;
   Col_Adjust = (float) (Bottom_Position - 12) / 100;

   Fill(Hold, N_Elements);

   Bottom_Position = Bottom_Position - 1;

   switch (Run_Opt())
   {
      case 1:

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Bubble Sort");
         Bubble(N_Elements, X);
         Stats();

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Cocktail Shaker Sort");
         Shaker(N_Elements, X);
         Stats();

      case 2:

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Select Sort");
         SelSort(N_Elements, X);
         Stats();

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Insert Sort");
         InSort(N_Elements, X, 1);
         Stats();

      case 3:

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Shell's Sort");
         ShellSort(N_Elements, X);
         Stats();

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Heap Sort");
         HeapSort(N_Elements, X);
         Stats();

      case 4:

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Quick Sort");
         QkSort(1, N_Elements, X);
         Stats();

      case 5:

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Recursive Merge Sort");
         MsortR(1, N_Elements, X);
         Stats();

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "Iterative Merge Sort");
         MsortI(N_Elements, X);
         Stats();

         Copy(X, Hold, N_Elements);
         Init_Screen(X, N_Elements, "\"Natural\" Merge Sort");
         MsortN(N_Elements, X);
         Stats();

      case 6:

         Copy(X, Hold, N_Elements);
/*       Force manual advance during Radix sort */
         Loop_Hold = Loop_Lim;
         Loop_Lim  = 0;
         Init_Screen(X, N_Elements, "Radix (bin) Sort");
         gotoxy (1, 3);
         fputs ("Press <Enter> for each successive screen", stdout);
         BinSort(N_Elements, X);
         Loop_Lim  = Loop_Hold;
         Stats();
   }

   Search_Demo(N_Elements, X);

   return 0;
}

int BinSrch (int V, int N, int X[])
/*
   Binary search --- without early exit on equality
   On failure, return a negative index (which will be where the
   item sought WOULD go to be in proper position).
*/
{
   int Lo, Mid, Hi;
   Lo = 1;
   Hi = N;
   X[0] = V;
   while (Hi > Lo)
   {
      Mid = (Hi + Lo) >> 1;
      Flag(Mid, "M");
      if (Compare(X, 0, Mid) > 0)
         Lo = Mid + 1;
      else
         Hi = Mid;
   }
   Flag(Hi, "M");
   return ! Compare(X, 0, Hi) ? Hi : -Hi;
}
 
void Bubble (int N, int *X)
{
   int Lim, Idx, Last;
 
   for (Lim = N; Lim >= 2; Lim--)
   {
      Flag(Lim, "Lim");
      Last = 0;
      for (Idx = 1; Idx < Lim; Idx++)
      {
         if (Compare(X, Idx, Idx + 1) > 0)
         {
            Last = Idx + 1;
            SwapIt(Idx, Last, X);
         }
      }
      UnFlag(Lim, "Lim");
      if (! Last) break;
   }
}
 
#define SWAP(X,Y) {int T; T = X; X = Y; Y = T;}
 
int Compare (int X[], int Left, int Right)
{
   int J1, R1, J2, R2, J3;
   int Idx;
 
   N_Compares = N_Compares + 1;
 
   if (Left > 0)
   {
      J1 = 3 * Left - 1;
      R1 = 6;
   }
   else
   {
      J1 = 1;
      R1 = 2;
   }
   if (Right > 0)
   {
      J2 = 3 * Right - 1;
      R2 = 6;
   }
   else
   {
      J2 = 1;
      R2 = 2;
   }
 
   if (J1 > J2)
   {
      SWAP(J1, J2);
      SWAP(R1, R2);
   }
   J3 = (J1 + J2) / 2;
   J2 = J2 + 1;
   gotoxy (J1, 4);
   if(J1 == J2 || J2 == J3)
      printf ("CMP");
   else
      printf ("%s", Replicate (J2-J1 + 1, '-'));
 
   if (R1 == 2)
      gotoxy (J1, 3);
   else
      gotoxy (J1, 5);
   putchar ('|');
   gotoxy (J1, 4);
   putchar ('+');
   gotoxy (J2, 5);
   putchar  ('|');
   gotoxy (J2, 4);
   putchar ('+');
   gotoxy (J3, 4);
   printf ("CMP");
 
   if (Loop_Lim == 0)
      Pause();
   else
      for (Idx = 0; Idx < 10; Idx++)
     Pause();
 
   if (R1 == 2)
      gotoxy (J1, 3);
   else
      gotoxy (J1, 5);
   putchar (' ');
   gotoxy (J2, 5);
   putchar (' ');
   gotoxy (J1, 4);
   printf ("%s", Replicate(J2-J1 + 3, ' '));
 
   return X[Left] - X[Right];
}
 
void Copy(int *A, int *Hold, int N)
{
   *A++ = *Hold++;  /* In fact we want Hold[1] on up copied */
   for ( ; N-- > 0 ; *A++ = *Hold++ )
      ;
}
 
void DownHeap (int Idx, int Lim, int X[])
{
   int This, Child, More;
 
/* Keep a copy of the item being positioned in heap */
   ToHold(Idx, X[Idx], "Position");
   X[0] = X[Idx];
   This = Idx;
   Child = This * 2;
   More = (Child <= Lim);
 
/* Structure:  while position for Hold not found . . . */
 
   while (More)
   {
      if (Child < Lim)
/*       Go down the LARGER sub-heap */
         if (Compare(X, Child, Child + 1) < 0)
            Child = Child + 1;
/*    ?Move item up in the heap? */
      if (Compare(X, Child, 0) > 0)
      {
         MoveIt(Child, X[Child], This);
         X[This] = X[Child];
         This = Child;
         Child = This * 2;
         More = (Child <= Lim);
      }
      else
         More = 0;
   }
   FromHold(This, X[0]);
   X[This] = X[0];
}

void Fill (int A[], int N)
{
   int  Used[99], Value;
   int  Opt, Idx, Top;
   char Ans[10];


   clrscr();
   Top = 8;
   gotoxy (10, Top);
   printf ("Array fill options:  ");
   gotoxy (15, Top + 2);
   printf ("1:  fill the array in forward order");
   gotoxy (15, Top + 4);
   printf ("2:  fill the array in backwards order");
   gotoxy (15, Top + 6);
   printf ("3:  fill the array with random values (default)");
   gotoxy (10, Top +8);
   printf ("Which option (1-3)  ");
   fgets  (Ans, 10, stdin);
   Opt = atoi(Ans);
   Opt = Opt ? Opt : 3;
   while (Opt < 1 || Opt > 3)
   {
      gotoxy (10, Top + 12);
      printf ("%d is not between 1 and 3; please try again.", Opt);
      gotoxy (30, Top + 8);
      printf ("                 ");
      gotoxy (30,Top + 8);
      fgets  (Ans, 10, stdin);
      Opt = atoi(Ans);
      Opt = Opt ? Opt : 3;
   }

   gotoxy (10, Top + 12);
   printf ("%s", Replicate(60, ' '));
   switch (Opt)
   {
   case 1:
      for (Idx = 1; Idx <= N; Idx++)
         A[Idx] = 10 + Idx * 89 / N;
      break;
   case 2:
      for (Idx = 1; Idx <= N; Idx++)
         A[Idx] = (N + 1 - Idx) * 89 / N + 10;
      break;
   case 3:
   case 0:
      randomize();
      for (Value = 0; Value  < 100; Value++)
         Used[Value] = 0;
      for (Idx = 1; Idx <= N ; Idx++)
      {
         do
           Value = random(90) + 10;
         while (Used[Value]);
         Used[Value] = 1;
         A[Idx] = Value;
      }
   }
}

void Flag (int Idx, char *Txt)
{
/* Attach a flag (with Txt$ as label) to a cell */
   int Jdx;

   Jdx = 3 * Idx;
   gotoxy (Jdx, 8);
   putchar ('|');
   gotoxy (Jdx, 9);
   putchar ('|');
   gotoxy (Jdx, 10);
   printf ("%s", Txt);
}

void FromHold (int Psn, int Value)
{
/* Move the indicated Value from the Hold area (screen row 2) and */
/* place it in the Idx cell. */

/* In the animation, propagate the value rightward into position, */
/* then drop it from row 2 to row 6 */

   int Idx, Jdx, Row;
   int Loop_Hold;
   char D[4];

   N_Moves = N_Moves + 1;

   Jdx = 3 * Psn - 1;
   sprintf (D, "%2d", Value);
   gotoxy (6, 2);
   printf ("%s", Replicate(40, ' '));
   Loop_Hold = Loop_Lim;
   Loop_Lim = (Loop_Lim + 1) / 2;
   for (Idx = 2;  Idx <= Jdx; Idx++)
   {
      gotoxy (Idx-1, 2);
      printf (" %s", D);
      Pause();
   }
   Loop_Lim = Loop_Hold;

   for (Row = 2; Row <= 5; Row++)
   {
      gotoxy (Jdx, Row);
      printf ("   ");
      gotoxy (Jdx, Row + 1);
      printf ("%s", D);
      Pause();
   }
   Row = Bottom_Position - Value * Col_Adjust;
   gotoxy (Jdx, Row);
   putchar ('*');
}

void HeapSort (int N, int X[])
{
   int Top, Lim;
 
   for (Top = N / 2; Top >= 1; Top--)
   {
      Flag(Top, "Top");
      DownHeap(Top, N, X);
      UnFlag(Top, "Top");
   }
 
   for (Lim = N - 1; Lim > 0; Lim--)
   {
      Flag(Lim, "Lim");
      SwapIt(1, Lim + 1, X);
      DownHeap(1, Lim, X);
      UnFlag(Lim, "Lim");
   }
}
void Init_Screen (int X[], int N, char *Title)
{
   int Size, Idx, Jdx, Row;
 
   clrscr();
   gotoxy ((80 - strlen(Title)) / 2, 1);
   printf ("%s", Title);
   gotoxy (1, 6);
   printf (" +");
   Update (1, N, X);
}
 
void Update (int Lo, int Hi, int X[])
{
   int  Idx, Jdx, Row;
   char D[5];
 
   for (Idx = Lo; Idx <= Hi; Idx++)
   {
      Jdx = 3 * Idx - 1;
      sprintf (D, "%2d ", X[Idx]);
      gotoxy (Jdx, 6);
      printf ("%s", D);
      gotoxy (Jdx, 7);
      printf ("--+");
      Row = (Bottom_Position - X[Idx] * Col_Adjust);
      gotoxy (Jdx, Row);
      putchar ('*');
   }
}
 
void Clear_Pts (int Lo, int Hi, int X[])
{
   int Idx, Jdx, Row;
 
   for (Idx = Lo; Idx <= Hi; Idx++)
   {
      Jdx = 3 * Idx - 1;
      Row = (Bottom_Position - X[Idx] * Col_Adjust);
      gotoxy (Jdx, Row);
      putchar (' ');
   }
}
 
void InSort (int N, int X[], int H)
{
   int Lim, Hole, Test;
 
   for (Lim = H + 1; Lim <= N; Lim++)
   {
      Flag(Lim, "Lim");
      Hole = Lim;
      X[0] = X[Hole];
      ToHold(Hole, X[Hole], "Position");
      Test = Hole - H;
      while (Compare(X, Test, 0) > 0)
      {
         MoveIt(Test, X[Test], Hole);
         X[Hole] = X[Test];
         Hole = Test;
         Test = Hole - H;
         if (Test < 1)
            break;
      }
      FromHold(Hole, X[0]);
      X[Hole] = X[0];
      UnFlag(Lim, "Lim");
   }
}
 
int LinSrch (int V, int N, int X[])
{
/* Linear alias sequential search.  Negative result on failure. */
 
   int Idx, Tst;
 
   X[0] = V;
   for (Idx = 1; Idx <= N; Idx++)
   {
      Tst = Compare(X, 0, Idx);
      if (Tst == 0)
     break;
   }
   return (Idx > N) ? -1 : Idx;
}
 
void MoveIt (int Start, int Value, int Finish)
{
/* Move the indicated Value from the Start cell to the Finish cell. */
 
/* In the animation, levitate the value from row 6 to row 3, then */
/* propagate it in the appropriate direction until it stands over */
/* the Finish cell.  Drop it from row 3 to row 6. */
 
   int  Idx, Jdx, Incr, Row;
   char D[5];
 
   N_Moves = N_Moves + 1;
 
   if (Start == Finish) return;
 
   Jdx = 3 * Start - 1;
   Row = Bottom_Position - Value * Col_Adjust;
   gotoxy (Jdx, Row);
   putchar (' ');
   sprintf (D, "%2d", Value);
   for (Row = 5; Row >= 3; Row--)
   {
      gotoxy (Jdx, Row + 1);
      printf ("  ");
      gotoxy (Jdx, Row);
      printf ("%s", D);
      Pause();
   }
   Incr = (Finish > Start) ? 1 : -1 ;
   for (Idx = Jdx; Idx != 3 * Finish - 1; Idx += Incr)
   {
      gotoxy (Idx - 1, 3);
      printf (" %s ", D);
      Pause();
   }
   gotoxy (Idx - 1, 3);
   printf (" %s ", D);
   for (Row = 3; Row <= 5; Row++)
   {
      gotoxy (Idx, Row);
      printf ("  ");
      gotoxy (Idx, Row + 1);
      printf ("%s", D);
      Pause();
   }
   Row = Bottom_Position - Value * Col_Adjust;
   gotoxy (Idx, Row);
   putchar ('*');
}
 
int Partition (int L0, int H1, int X[])
{
/* Rearrange the X[] array so that a single element is properly */
/* positioned:  all elements to the left of the "partitioning */
/* element" (or pivot) belong on the left; all to the right */
/* belong on the right.  The position of this partitioning */
/* element is then the value of the Partition function. */
 
/* This version of partition based on Thomas Naps, "Introduction */
/* to Data Structures and Algorithm Analysis"; the Median of Three */
/* improvement is taken from Robert Sedgewick, "Algorithms." */
 
   int Lo, Mid, Hi;
 
   Lo = L0;
   Hi = H1;
   Flag(Lo, "Lo");
   Flag(Hi, "Hi");
 
/* "Median of Three" --- middle element becomes the actual element. */
/*                       Insure that ends up in X[Lo]. */
 
   Mid = (Lo + Hi) / 2;
   if (Compare(X, Lo, Hi) < 0)            /* abc acb bac */
      if (Compare(X, Lo, Mid) < 0)        /* otherwise bac */
      {
         if (Compare(X, Mid, Hi) < 0)     /* abc */
            SwapIt(Lo, Mid, X);
         else                             /* acb */
            SwapIt(Lo, Hi, X);
      }
   else                                   /* bca cab cba */
      if (Compare(X, Lo, Mid) > 0)        /* otherwise bca */
         if (Compare(X, Mid, Hi) > 0)     /* cba */
        SwapIt(Lo, Mid, X);
         else                             /* cab */
            SwapIt(Lo, Hi, X);
 
/* Open up a "hole" at X[Lo], with X[Mid] as pivot value. */
 
   ToHold(Lo, X[Lo], "Pivot");
   X[0] = X[Lo];
 
/* The loop has two exits:  the two places where the Lo and the Hi */
/* indexes have come together.  In lieu of extra flags or logical */
/* comparisons, this code uses an explicit EXIT DO at those two places. */
 
   while (1)
   {
/*    Search for the value from Hi downward to plug the hole at X[Lo] */
      while (Compare(X, 0, Hi) < 0 && Lo < Hi)
         Hi = Hi - 1;
/*    If we've come together, we're done */
      if (Lo == Hi) break;
/*    Otherwise plug the hole at Lo with the value at Hi */
      MoveIt(Hi, X[Hi], Lo);
      X[Lo] = X[Hi];
/*    The hole is now at Hi and Lo is guaranteed good w.r.t. Pivot */
      Lo = Lo + 1;
 
/*    Search for the value from Lo upward to plug the hole at X[Hi] */
      while (Compare(X, Lo, 0) < 0 && Lo < Hi)
         Lo = Lo + 1;
/*    If we've come together, we're done */
      if (Lo == Hi) break;
/*    Otherwise plug the hole at Hi with the value at Lo */
      MoveIt(Lo, X[Lo], Hi);
      X[Hi] = X[Lo];
/*    The hole is now at Lo and Hi is guaranteed good w.r.t. Pivot */
      Hi = Hi - 1;
   }
 
/* Plug the remaining hole (which is guaranteed to be in Hi = Lo) */
/* with the pivot value, making this the partitioning element. */
 
   FromHold(Hi, X[0]);
   X[Hi] = X[0];
 
   UnFlag(L0, "  ");
   UnFlag(H1, "  ");
 
   Flag(Hi, "#");
   return Hi;
}
 
void Pause()
{
/*  Subprogram to pause the simulation. */
 
/*  If the delay loop has a zero value, use manual control -- Enter */
 
   if (Loop_Lim != 0)
      delay(Loop_Lim);
   else
      while ( (CharIn = getchar()) != '\n')
         ;
   return;
}
 
void QkSort (int Lo, int Hi, int X[])
{
/*  Basic QuickSort algorithm: */
 
/*     1)  Check for exit condition:  if Hi does not come after Lo, */
/*         there is nothing left to sort. */
/*     2)  Let the "Partition" function position one element to its */
/*         exact position:  everything to its left belongs on the */
/*         left, everything to its right belongs on its right. */
/*     3)  QuickSort can then call itself to sort everything to the */
/*         left as a sub-array. */
/*     4)  Rather than recursively calling itself for the right */
/*         sub-array, QuickSort can just update Lo and stay within */
/*         the current call. */
 
/*  Note:  Almost _all_ of the work for QkSort is embedded in the */
/*         Partition routine. */
 
   int Mid;
 
   while (Lo < Hi)
   {
      Mid = Partition(Lo, Hi, X);
      QkSort(Lo, Mid - 1, X);   /* Recursive part for left */
      Lo = Mid + 1;            /* "Tail" recursion on right */
   }
   if (Lo == Hi) Flag(Hi, "o");
}
 
void Search_Demo (int N, int X[])
{
/*  Using the sorted data on the screen, demonstrate the two kinds of */
/*  searches --- linear/sequential and binary. */
 
   static char Title[] = "Search Demonstration";
   char D[5];
   int  L_Pos, V, K, Idx, Loop_Hold;

   Init_Screen (X, N, Title);
/* REMOVE if not needed:
   gotoxy (1, 1);                 Init_Screen(X, N_Elements, "Bubble Sort");
   printf ("%s", Replicate(80, ' '));
   gotoxy ((80 - strlen(Title)  ) / 2, 1);
   printf ("%s", Title);
/*  Wipe out all tick marks and values below the line */
   do
   {
      for (L_Pos = 8; L_Pos <= Bottom_Position; L_Pos++)
      {
     gotoxy (1, L_Pos);
     printf ("%s", Replicate(79, ' '));
      }

      gotoxy (1, 12);
      printf ("Item sought:  ");
      fgets  (D, 5, stdin);
      V = atoi(D);
      N_Compares = 0;
      printf ("Doing a linear/sequential search");
      sprintf (D, "%2d", V);
      gotoxy (1, 2);
      printf ("%s  <== Sought", D);
      Idx = LinSrch(V, N, X);
      gotoxy (1, 14);
      if (Idx > 0)
         printf ("%d required to find at index %d\n",
                  N_Compares, Idx);
      else
         printf ("%d required to fail\n", N_Compares);

      printf ("Press Enter to continue: ");
      gets (D);

      gotoxy (1, 15);
      printf ("%s", Replicate(40, ' '));
      N_Compares = 0;
      Loop_Hold = Loop_Lim;
      Loop_Lim = 0;
      printf ("\nDoing a binary search --- <Enter> to advance");
      Idx = BinSrch(V, N, X);
      Loop_Lim = Loop_Hold;
      gotoxy (1, 17);
      if (Idx > 0)
         printf ("%d required to find at index %d\n",
                 N_Compares, Idx);
      else
         printf ("%d required to fail\n", N_Compares);
      putchar ('\n');
      printf ("Press Q <Enter> to quit, <Enter> to continue  ");
      K = getchar();
      if (K != '\n')
         gets (D);
      gotoxy (1, 2);
      printf ("%s", Replicate(15, ' '));
   } while (toupper(K) != 'Q');
   gotoxy (1, 22);
}

char *Replicate(int N, char Fill)
{
   static char Buffer[130];
   int Idx;

   for (Idx = 0; Idx < N; Idx++)
      Buffer[Idx] = Fill;
   Buffer[Idx] = '\0';
   return &Buffer[0];
}
 
void SelSort (int N, int X[])
{
   int Lim, Idx, Hi;
 
   for (Lim = N; Lim >= 2; Lim--)
   {
      Flag(Lim, "Lim");
      Hi = 1;
      for (Idx = 2; Idx <= Lim; Idx++)
         if (Compare(X, Idx, Hi) > 0) Hi = Idx;
      SwapIt(Lim, Hi, X);
      UnFlag(Lim, "Lim");
   }
}
 
void Shaker (int N, int X[])
{
   int Inc, Top, Idx, Lim, Last, Lo, Hi;

   Inc = 1;
   Top = 1;
   Lim = N;
   while (Lim > Top)
   {
      Last = 0;
      if (Inc == 1)
      {
         Lo = Top;
     Hi = Lim - 1;
      }
      else
      {
         Lo = Lim - 1;
         Hi = Top;
      }
      Flag(Top, "Lo");
      Flag(Lim, "Hi");
 
      Idx = Lo;
      while (1)
      {
     if (Compare(X, Idx, Idx + 1) > 0)
         {
            Last = Idx;
            SwapIt(Idx, Idx + 1, X);
         }
         if (Idx == Hi)
            break;
         else
            Idx += Inc;
      }
      UnFlag(Top, "Lo");
      UnFlag(Lim, "Hi");
      if (Last == 0) break;
      if (Inc == 1)
         Lim = Last;
      else
         Top = Last + 1;
      Inc = -Inc;
   }
}
 
void ShellSort (int N, int X[])
{
   int  H;
 
   H = 1;
   while (H <= N)
      H = H * 2 + 1;
   H = (H > 4) ? H / 4 : 1;
   while (H > 0)
   {
      InSort(N, X, H);
      H = H / 2;
   }
}
 
void Stats()
{
   char Line[20];
   int  Nval, Tst;
 
   gotoxy (1, 11);
   printf ("%4d comparisons\n", N_Compares);
   printf ("%4d data swaps\n", N_Swaps);
   printf ("%4d single moves\n", N_Moves);
   N_Compares = 0;
   N_Swaps = 0;
   N_Moves = 0;
 
   gotoxy (20, Bottom_Position - 1);
   printf ("Press Enter to continue:  ");
   gets (Line);
   Tst = sscanf(Line, "%d", &Nval);
   if (Tst > 0)
      Loop_Lim = Nval;
}
 
void SwapIt (int P1, int P2, int X[])
{
/*  Swap position P1 with position P2 in X[] */
 
/*  In the animation, levitate Val1 from row 6 to row 3 and Val2 from */
/*  for 6 to row 2 (choosing the left-most as Val1).  Then propagate */
/*  both in the appropriate directions until they stand over their */
/*  target cells.  Drop them row 6. */
 
   char D1[5], D2[5];
   int  Pos1, Pos2, Val1, Val2, J1, J2, Row, Idx, Lim, R1, R2;
 
   N_Swaps = N_Swaps + 1;
 
   if (P1 == P2) return;
 
   if (P1 < P2)
   {
      Pos1 = P1; Val1 = X[P1]; Pos2 = P2; Val2 = X[P2];
   }
   else
   {
      Pos1 = P2; Val1 = X[P2]; Pos2 = P1; Val2 = X[P1];
   }
   J1 = 3 * Pos1 - 1;
   sprintf (D1, "%2d", Val1);
   J2 = 3 * Pos2 - 1;
   sprintf (D2, "%2d", Val2);
   for (Row = 5; Row >= 3; Row--)
   {
      gotoxy (J1, Row + 1);
      printf ("  ");
      gotoxy (J1, Row);
      printf ("%s", D1);
      gotoxy (J2, Row + 1);
      printf ("  ");
      gotoxy (J2, Row);
      printf ("%s", D2);
      Pause();
   }
   gotoxy (J2, Row + 1);
   printf ("  ");
   gotoxy (J2, Row);
   printf ("%s",D2);
   Pause();
 
   Lim = J2;
   for (Idx = J1; Idx <= Lim; Idx++)
   {
      gotoxy (J1 - 1, 3);
      printf (" %s", D1);
      gotoxy (J2, 2);
      printf ("%s ", D2);
      J1 = J1 + 1;
      J2 = J2 - 1;
      Pause();
   }
   J1 = J1 - 1;
   J2 = J2 + 1;
   gotoxy (J2, Row);
   printf ("  ");
   gotoxy (J2, Row + 1);
   printf ("%s", D2);
   for (Row = 3; Row <= 5; Row++)
   {
      gotoxy (J1, Row);
      printf ("  ");
      gotoxy (J1, Row + 1);
      printf ("%s", D1);
      gotoxy (J2, Row);
      printf ("  ");
      gotoxy (J2, Row + 1);
      printf ("%s", D2);
      Pause();
   }
 
   J1 = 3 * P1 - 1;
   J2 = 3 * P2 - 1;
   R1 = Bottom_Position - X[P1] * Col_Adjust;
   R2 = Bottom_Position - X[P2] * Col_Adjust;
   gotoxy (J1, R1);
   putchar (' ');
   gotoxy (J2, R2);
   putchar (' ');
   gotoxy (J2, R1);
   putchar ('*');
   gotoxy (J1, R2);
   putchar ('*');
 
   SWAP(X[P1], X[P2]);        /* Do the actual data swap */
}
 
void ToHold (int Idx, int Value, char *Txt)
{
/*  Move the indicated Value from the Idx cell and place it in the */
/*  Hold area (screen row 2), labeling it with the indicated Txt. */
 
/*  In the animation, levitate the value from row 6 to row 2, then */
/*  propagate it leftward into position. */
 
   int   Jdx, Row, Loop_Hold;
   char  D[5];
 
   N_Moves = N_Moves + 1;
 
   Jdx = 3 * Idx - 1;
   sprintf (D, "%2d", Value);
   for (Row = 5; Row >= 2; Row--)
   {
      gotoxy (Jdx, Row + 1);
      printf ("  ");
      gotoxy (Jdx, Row);
      printf ("%s", D);
      Pause();
   }
   Row = Bottom_Position - Value * Col_Adjust;
   gotoxy (Jdx, Row);
   putchar (' ');
 
   Loop_Hold = Loop_Lim;
   Loop_Lim = (Loop_Lim + 1) / 2;
   while (Jdx > 1)
   {
      Jdx = Jdx - 1;
      gotoxy (Jdx, 2);
      printf ("%s ", D);
      Pause();
   }
   Loop_Lim = Loop_Hold;
   gotoxy (6, 2);
   printf ("%s", Replicate(40, ' '));
   gotoxy (6, 2);
   printf ("<--- %s", Txt);
}

void UnFlag (int Idx, char *Txt)
{
/*  Remove an earlier flag from a cell (Txt has proper size for label) */

   int Jdx;

   Jdx = 3 * Idx;
   gotoxy (Jdx, 8);
   putchar (' ');
   gotoxy (Jdx, 9);
   putchar (' ');
   gotoxy (Jdx, 10);
   printf ("%s", Replicate(strlen(Txt), ' '));
}
 
#ifndef __TURBOC__         /* NOT Borland:  use ANSI terminal graphics */
void gotoxy(int X, int Y)
{
   printf ("\033[%d;%dH", Y, X);
}

void clrscr()
{
   gotoxy(1,1);
   printf ("\033[J");
}
#endif
 
void Merge (int Lo, int Mid, int Hi, int X[])
{
   int  Idx0, Idx1, Idx2;
   int  N;
 
   Idx0 = Lo;
   Idx1 = Lo;
   Idx2 = Mid;
   Flag(Lo, "L");
   Flag(Mid, "M");
   Flag(Hi, "H");
   while (Idx1 < Mid && Idx2 <= Hi)
   {
      if (Compare(X, Idx1, Idx2) <= 0)
      {
         Scratch[Idx0] = X[Idx1];
         Idx1 = Idx1 + 1;
      }
      else
      {
         Scratch[Idx0] = X[Idx2];
         Idx2 = Idx2 + 1;
      }
      Idx0 = Idx0 + 1;
      N_Moves = N_Moves + 1;
   }
   while (Idx1 < Mid)
   {
      Scratch[Idx0] = X[Idx1];
      Idx1 = Idx1 + 1;
      Idx0 = Idx0 + 1;
      N_Moves = N_Moves + 1;
   }
   while (Idx2 <= Hi)
   {
      Scratch[Idx0] = X[Idx2];
      Idx2 = Idx2 + 1;
      Idx0 = Idx0 + 1;
      N_Moves = N_Moves + 1;
   }
   Clear_Pts(Lo, Hi, X);
   Update(Lo, Hi, Scratch);
   for (Idx0 = Lo; Idx0 <= Hi; Idx0++)
   {
      X[Idx0] = Scratch[Idx0];
      N_Moves = N_Moves + 1;
   }
   UnFlag(Lo, "L");
   UnFlag(Mid, "M");
   UnFlag(Hi, "H");
}
 
void MsortR (int Lo, int Hi, int X[])
{
   int Mid;
 
   if (Hi <= Lo) return;
   Mid = (Lo + Hi + 1) / 2;
   MsortR(Lo, Mid - 1, X);
   MsortR(Mid, Hi, X);
   Merge(Lo, Mid, Hi, X);
}

void MsortI (int N, int X[])
{
   int  H, Lo, Mid, Hi;

   for (H = 1; H < N; H <<= 1)
   {
      for (Lo = 1; Lo < N; Lo += H << 1)
      {
         Mid = Lo + H;
         if (Mid > N)
            break;
         Hi = Mid - 1 + H;
         if (Hi > N)
            Hi = N;
         Merge(Lo, Mid, Hi, X);
      }
   }
}

void MsortN (int N, int X[])
/*
   I.e., take advantage of existing order within the data ---
         many more comparisons are often required, but the number
         of data movements is reduced.

   Also, as the data becomes closer to ordered this approaches an
   Order(N) algorithm.
*/
{
   int Lo, Mid, Hi,     /* Markers in delimited ordered regions */
       Idx;

   Idx = Lo = 1;
   Flag (Lo, "L");
   while (1)
   {
      while (++Idx <= N)
	 if (Compare(X, Idx-1, Idx) > 0)
	    break;
      if (Idx > N)
	 if (Lo > 1)
	 {
	    UnFlag (Lo, "L");
	    Lo = Idx = 1;
	    Flag (Lo, "L");
	    continue;
	 }
	 else
	    break;         /* <=== Yea, I know.  NOT structured! */
      Mid = Idx;
      Flag (Mid, "M");
      while (++Idx <= N)
         if (Compare(X, Idx-1, Idx) > 0)
            break;
      Hi = Idx - 1;
      Flag (Hi, "H");
      Merge(Lo, Mid, Hi, X);
      UnFlag (Lo, "L");
      UnFlag (Mid, "M");
      UnFlag (Hi, "H");
      if (Idx <= N)
         Lo = Idx;
      else
         if (Lo == 1)
            break;
         else
	    Lo = Idx = 1;
      Flag (Lo, "L");
   }
   UnFlag (Lo, "L");
}

void BinSort (int N, int X[])
{
   int Div, Bit, Check, Idx, Idx1, Idx2;
 
   Div = 1;
   Bit = 0;
   gotoxy (1, 1);
   fputs ("Press <Enter> to begin", stdout);
   do
      Idx = getchar();
   while (Idx != '\n');
   gotoxy (1, 1);
   fputs ("                      ", stdout);
   while (1)
   {
      Idx1 = 0;
      Idx2 = N + 1;
      for (Idx = 1; Idx <= N; Idx++)
      {
         Check = (X[Idx] / Div) & 1;
         if (Check == 0)
         {
            Idx1 = Idx1 + 1;
            Scratch[Idx1] = X[Idx];
         }
         else
         {
            Idx2 = Idx2 - 1;
            Scratch[Idx2] = X[Idx];
         }
         N_Moves = N_Moves + 1;
      }
      if (Idx2 > N)
         break;
      Clear_Pts(1, N, X);
      Idx = N;
      while (Idx2 <= N)
      {
         X[Idx] = Scratch[Idx2];
         Idx = Idx - 1;
         Idx2 = Idx2 + 1;
         N_Moves = N_Moves + 1;
      }
      while (Idx1 >= 1)
      {
         X[Idx] = Scratch[Idx1];
         Idx1 = Idx1 - 1;
         Idx = Idx - 1;
         N_Moves = N_Moves + 1;
      }
      Update(1, N, X);
      gotoxy (1, 1);
      printf ("Bit %d ordering", Bit++);
      if (Loop_Lim == 0)
         Pause();
      else
         for (Idx = 1; Idx <= 10; Idx++)
            Pause();
      Div <<= 1;
   }
}

int Run_Opt()
{
   int  Top, Opt, Row;
   char Ans[10];

   clrscr();
   Top = 6;
   gotoxy (10, Top);
   puts ("Execution start-points:");
   gotoxy (15, Top + 2);
   puts ("1:  Bubble and Shaker sorts");
   gotoxy (15, Top + 4);
   puts ("2:  Select and Insert sorts");
   gotoxy (15, Top + 6);
   puts ("3:  Shell's sort and the N lg(N) sorts");
   gotoxy (15, Top + 8);
   puts ("4:  Quick sort");
   gotoxy (15, Top + 10);
   puts ("5:  Merge sorts");
   gotoxy (15, Top + 12);
   puts ("6:  Radix sort (default)");
   gotoxy (10, Top + 14);
   fprintf (stdout, "Which option (1-6)");
   fgets  (Ans, 10, stdin);
   Opt = atoi(Ans);
   Opt = Opt ? Opt : 6;
   while (Opt < 1 || Opt > 6)
   {
      gotoxy (10, Top + 17);
      printf ("%d is not between 1 and 6; please try again.",
              Opt);
      gotoxy (28, Top + 14);
      fputs (Replicate (40, ' '), stdout);
      gotoxy (28, Top + 14);
      fgets  (Ans, 10, stdin);
      Opt = atoi(Ans);
      Opt = Opt ? Opt : 6;
   }

   return Opt;
}