SuperHack/SuperHack CD.bin/CODING/C/CSORT.ZIP/CSORT.C

C/C++ Source or Header | 1995-07-15 | 20.6 KB | 726 lines

/************************************************************************

 Title: csort.c

  A program which demonstrates the action of six sort algorithms using
animated graphics.

 Date:  9/22/88

 Author: Mark Weisz   72057,1566

 Compiler: Turbo C 1.5

           This program must be run from a project which includes
           graphics.lib. It issumes that the CGA and Hercules
           drivers are in graphics.lib.

 Notes:
   Modeled after the program "SEESORT.BAS" written by John P. Grillo
   and J.D. Robertson. Published in "More Color Computer Applications"
   Wiley Press, 1984.

   All the algorithms except the Quicksort were adapted from the
   original BASIC code in SEESORT.

   The Quicksort is taken from Ray Duncan's "Power Programming" column
   in PC Magazine, September 13, 1988, p. 343. That algorithm in turn
   was adapted from "Algorithms 2nd Edition" by Robert Sedgewick,
   Addison-Wesley, 1988.

   The gprintf and Initialize functions were lifted from BGIDEMO.C
   which comes with Turbo C v. 1.5 from Borland International.


**************************************************************************/

#include <conio.h>
#include <ctype.h>
#include <dos.h>
#include <graphics.h>
#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>

#define MAXNUM   200    /* maximum number of array elements to sort */
#define XAXIS    260    /* x coordinate on graphics screen          */
#define YAXIS    15     /* y coordinate on graphics screen          */
#define MAXPICKS 8      /* maximum menu picks given to user         */
#define TIMES    3      /* how many times to perform...             */

int xaxis = XAXIS;
int yaxis = YAXIS;

enum sort {bubble, delayed, shell, shell_metzner,
           quick, insertion, all, stop};

char *sorts[MAXPICKS] =
                 {"Bubble Sort", "Delayed Exchange Sort", "Shell Sort",
                  "Shell-Metzner Sort", "QuickSort", "Insertion Sort",
                   "All", "Exit to Dos"};

/*****  function prototypes  *************************/

void main( void );
void driver( enum sort atype, int *m, int elements,
             int random, int delay_factor );
enum sort pick_sort( int *elements, int *random, int *delay_factor );
void Initialize( void );
void Setscreen( int *m, int elements, int random );
int  Swap_Pixels( int *m, int i, int j, int delay_factor );
int  gprintf( int *xloc, int *yloc, char *fmt, ... );
void print_menu( char *mysorts[] );
void get_number( int *elements, int *times, char *tstring, int *x, int *y );
void Showdata ( int *m );

void Bubble( int *m, int elements, int delay_factor );
void Delayed( int *m, int elements, int delay_factor );
void Shell_Metzner( int *m, int elements, int delay_factor );
void Quicksort( int *m, int left, int right, int delay_factor );
void Insertion( int *m, int elements, int delay_factor );
void Shell( int *m, int elements, int delay_factor );


/*****  main  ***************************************/
/*                                                  */
/****************************************************/

void main( void )
{
 int array[MAXNUM];    /*  the array to be sorted  */
 int elements;         /*  how many elements       */
 int random;           /*  random or worst case    */
 int delay_factor;     /*  delay factor 0-1000     */

 enum sort stype = all;
 Initialize();
 while( stype != stop )
   {
    random = 0;
    elements = 0;
    delay_factor = 0;
    stype = pick_sort( &elements, &random, &delay_factor );
    if ( stype != stop )
      {
       driver( stype, array, elements, random, delay_factor );
       /* Showdata( array ); */
       delay( 1350 );
      }
   }
 closegraph();
}


/*****  pick_sort  *******************************************************

  Displays a simple menu and prompts the user for four choices.

  called by:  main

  calls: print_menu
         gprintf
         get_number


  returns  :  the sort desired (could be all sorts or quit)

  parameters:

    *elements
    *random
    *delay_factor
*************************************************************************/

enum sort pick_sort( int *elements, int *random, int *delay_factor )
{
 static char query1[] = "Which Sort (1-8)?";
 static char query2[] = "How Many Elements < 200?";
 static char query3[] = "(R)andom or (W)orst Case?";
 static char query4[] = "Delay Factor (0-1000)?";

 static char achar[2] = "x";
 char bchar = 0;
 char nstring[TIMES + 1];  /* string equivalent of elements  */
 int tens = TIMES; /* power of ten we're using       */
 int *tpower;
 int x = 50;
 int y = 30;
 char pick = 0;
 int x2;
 int i;    /* scratch variable */
 tpower = &tens;

 cleardevice();
 print_menu( sorts );

 /************** pick the sort *************************/
 gprintf( &x, &y, query1 );
 while ( pick <= 48 || pick >= 57 )  /* allow digits 1-8 */
  {
   pick = getch();
  }
 achar[0] = pick;
 x2 = x + 4 + textwidth( query1 );
 outtextxy( x2, y, achar );

 if ( pick != 56 )
   {
    y = 100;

    /******** get number of elements desired *****/
    gprintf( &x, &y, query2 );
    x2 = x + 4 + textwidth( query2  );
    for ( i = 0; i < TIMES + 1; i++ )
      nstring[i] = 0;        /* used to initialize string to nulls */

    get_number( elements, tpower, nstring, &x2, &y );
    if ( *elements == 0 || *elements > MAXNUM ) *elements = MAXNUM;

    y += textheight("H" ) + 1;

    /****** get random or worst case ***********/
    gprintf( &x, &y, query3 );
    bchar = 0;
    while( bchar != 82 && bchar != 87 )
      {
       bchar = toupper( getch( ) );
       if ( bchar == 13 ) bchar = 82;
      }
    *random = ( bchar ^ 87 ); /* XOR checks for (W)orst */
    achar[0] = bchar;
    x2 = x + 4 + textwidth( query3 );
    outtextxy( x2, y, achar );

    y += textheight( "H" ) + 1;

    /****** get delay factor  ******************/
    gprintf( &x, &y, query4 );
    x2 = x + 4 + textwidth( query4 );
    *tpower = TIMES;
    for ( i = 0; i < TIMES + 1; i++ )
      nstring[i] = 0;        /* used to initialize string to nulls */

    get_number( delay_factor, tpower, nstring, &x2, &y );

   }
  switch( pick - 48 )
    {
     case 1:
        return( bubble );
     case 2:
        return( delayed );
     case 3:
        return( shell );
     case 4:
        return( shell_metzner );
     case 5:
        return( quick );
     case 6:
        return( insertion );
     case 7:
        return( all );
     default:
        return( stop );
    }
}

/*****  print_menu  *****************************************

   prints the selection menu to the graphics
    screen like so:

                   1. Bubble Sort
                   2. Delayed Exchange Sort
                   3. Shell Sort
                   4. Shell Metzner Sort
                   5. Quicksort
                   6. Insertion Sort
                   7. All
                   8. Exit to Dos

    called by: pick_sort

*************************************************************/

void print_menu( char *mysorts[] )
{
 int x, y;   /* screen coordinates */
 int i;
 x = 240;
 y = 10;

 for ( i = 0; i < MAXPICKS; i++ )
   {
    gprintf( &x, &y, "%d. %s", i+1, mysorts[i] );
    y += textheight ( "H" ) + 1;
   }
}

/*****  get_number  ******************************************************

A recursive routine that accepts numbers using the getch() function, and
displays them on the graphics screen. Only the characters '0' to '9' and
CR are accepted -- the rest are ignored.

    called by: pick_sort, get_number

    parameters:

    int *a_number   holds the integer and returns it to the
                    calling function

    int *times      maximum number of times that get_number
                    will be called. acts as a flag to stop
                    the routine when the user enters the maximum
                    allowed digits or hits Carriage Return (CR).

    char *tstring   Returns the string equivalent of *a_number
                    i.e. if *a_number = 123, *tstring = "123".
                    It is initialized to all nulls before the initial
                    pass and its length is used to determine the
                    power of ten needed for each digit that is entered.

    int *x, *y      coordinates on the graphics screen to display
                    the digits as they are entered. *x is increased with
                    each call by the width of a character using the
                    textwidth function.

*************************************************************************/

void get_number( int *a_number, int *times, char *tstring, int *x, int *y )
{
int power;         /* power of 10 to multiply a digit by */
char achar[2];
char bchar = 0;
achar[1] = 0;

while ( bchar <= 47 || bchar >= 59 )  /* allow digits 0-9 */
  {
   bchar = getch();
   if ( bchar == 13 )   /* 13 = CR; if the user hits ENTER  */
     {
      bchar = 48;
      *times = 0;
      break;
     }
  }

 if ( *times )
   {
    achar[0] = bchar;

    outtextxy( *x, *y, achar );
    *x = *x + textwidth( achar );
    tstring[TIMES - ( (*times)--)] = achar[0];
    if ( *times )
    get_number( a_number, times, tstring, x, y );
   }

    power = (int)( pow10(( strlen( tstring ) - ((*times) + 1))));
    bchar = tstring[*times];
    *a_number += ( power  * ( bchar - 48 ));
    (*times )++;
}


/*****  driver  **********************************************************

   driver runs the sorts using parameters sent to it.

   It gets a sort type, the address of the array to sort, the number of
elements, the random/worst case status and the delay factor and sets them
in motion.

    called by: main

    calls: Setscreen, gprintf, all the sort functions

    parameters:

    enum sort atype    the desired sort

    int *array         the address of the array to sort

    int elements       how many elements

    int random         random = 1  worst case = 0

    int delay_factor   0 = no delay;  1000 = 1 second delay for
                       each switching of elements. The idea is to slow
                       down the animation so the user gets a feel for
                       what's going on. 1000 is _very_ slow.

*************************************************************************/

void driver( enum sort atype, int *array, int elements,
            int random, int delay_factor )
{

switch( atype )
  {
   case all    :

   case bubble :
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + bubble) );
            Bubble( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );

   case delayed:
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + delayed) );
            Delayed( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );

   case shell  :
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + shell ));
            Shell( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );

   case shell_metzner:
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + shell_metzner) );
            Shell_Metzner( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );

   case quick  :
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + quick) );
            Quicksort( array, 0, elements - 1, delay_factor );
            if ( atype != all ) break; else delay( 1350 );

   case insertion:
            Setscreen( array, elements, random );
            gprintf( &xaxis, &yaxis, *(sorts + insertion) );
            Insertion( array, elements, delay_factor );
            if ( atype != all ) break; else delay( 1350 );

   case stop:

   default:;
  }
}


/*****  initialize  *********************************/
/*                                                  */
/*  Initializes the Borland graphics drivers.       */
/*                                                  */
/****************************************************/

void Initialize( void )
{
 int    GraphDriver; /* The Graphics device driver   */
 int    GraphMode;   /* The Graphics mode value      */
 int    ErrorCode;   /* Reports any graphics errors  */

 // if( registerbgidriver(  )  < 0 ) exit(1);
 /* if( registerbgidriver( Herc_driver ) < 0 ) exit(2);
 if( registerbgidriver( EGAVGA_driver ) <0 ) exit(3); */

 GraphDriver = DETECT;              /* Request auto-detection */
 initgraph( &GraphDriver, &GraphMode, "" );
 ErrorCode = graphresult();   /* Read result of initialization*/
 if( ErrorCode != grOk )      /* Error occured during init  */
   {
    printf(" Graphics System Error: %s\n", grapherrormsg( ErrorCode ) );
    exit( 1 );
   }
/* settextstyle( SMALL_FONT, HORIZ_DIR, 0 ); */
}

/*****  gprintf  ************************************/
/*                                                  */
/*  Used like PRINTF except the output is sent to   */
/*  the screen in graphics mode at the specified    */
/*  co-ordinate. From Borland International.        */
/*                                                  */
/*  The return value from gprintf is not used.      */
/*                                                  */
/****************************************************/

int gprintf( int *xloc, int *yloc, char *fmt, ... )
{
 va_list  argptr;  /* Argument list pointer          */
 char str[80];     /* Buffer to build string into    */
 int count;        /* Result of vsprintf for return  */

 va_start( argptr, fmt );               /* Initialize va_functions      */
 count = vsprintf( str, fmt, argptr );  /* prints string to buffer      */
 outtextxy( *xloc, *yloc, str );        /* Send string in graphics mode */
 va_end( argptr );                      /* Close va_ functions          */
 return( count );                       /* Return the conversion count  */

}


/*****  Setscreen  *******************************************************

   Initializes graphics screen for the sort.

   called by: driver

   parameters:

    int *array         the array to sort

    int elements       how many elements

    int random         random = 1 or worst case = 0

*************************************************************************/

void Setscreen( int *array, int elements, int random )
{
int j;

cleardevice();

if ( random )
  {
   randomize();
   for ( j = 0; j < elements; j++ )
     {
      *( array + j) = random( elements );
      putpixel( 3*j, *(array+j), 10);
     }
  }
else /* initialize worst case */
  {
   for ( j = 0; j < elements; j++ )
     {
      *(array + j) = elements - j;
      putpixel( 3*j, *(array+j), 10);
     }

   }
}

/*****  Showdata  ***********************************/
/*                                                  */
/*  Displays the values in the first 20 elements    */
/*  of the array.                                   */
/*                                                  */
/****************************************************/


void Showdata( int *array )
{
int i, j, x, y;
j = 0;
i = 20;
x = 570;
y = 0;

while ( j < i )
 {
  gprintf( &x, &y, "%2d: %d ", j+1, array[j] );
  y += textheight( "H" ) + 1; /*  Advance to next line   */
  j++;
 }
}


/*****  Swap_Pixels  ********************************/
/*                                                  */
/*  Swaps the data in two array elements and        */
/*  changes their respective pixels accordingly.    */
/*  The turning off and on of pixels is what gives  */
/*  the illusion of movement.                       */
/*                                                  */
/****************************************************/

int Swap_Pixels( int *array, int i, int j, int delay_factor )
{
int h;
h = *(array + i);
putpixel( 3 * i, *(array + i), 0);
putpixel( 3 * j, *(array + i), 10 );
*(array + i) = *(array + j);
putpixel( 3 * j, *( array + j), 0 );
putpixel( 3 * i, *(array + j), 10 );
*(array + j) = h;

delay( delay_factor );
return( h );
}

/*****  Bubble  *************************************/
/*                                                  */
/****************************************************/

void Bubble( int *array, int elements, int delay_factor )
{
int i,j;

for ( i = 0; i < elements - 1 ; i++ )
 for ( j = i + 1; j < elements; j++ )
   {
    if ((*(array+i)) > (*(array+j)))
      {
       Swap_Pixels( array, i, j, delay_factor );
      }
   }
}

/*****  Delayed  ************************************/
/*                                                  */
/****************************************************/

void Delayed( int *array, int elements, int delay_factor )
{
int p, h, k, i, j;

for ( p = 0; p < elements-1; p++ )
 {
  h = p;
  for ( k = p + 1; k < elements ; k++ )
    if (*(array+k) < *(array+h))
      h = k;
  if ( p != h )
   {
    i = h;
    j = p;
    Swap_Pixels( array, i, j, delay_factor );
   }
 }
}

/*****  Shell  **************************************/
/*                                                  */
/****************************************************/

void Shell( int *array, int elements, int delay_factor )
{
 int p, f, i, j, m;


p = elements;
while ( p > 1)
  {
   p /= 2;
   /* gprintf( &xaxis, &yaxis, "%d", p );
   y++;   */
   m = elements - p;
   do{
     f = 0;
     for ( j = 0; j < m; j++ )
       {
        i = j + p;
        if (*(array + j) > *(array + i))
          {
           Swap_Pixels( array, i, j, delay_factor );
           f = 1;
          }
       }
     } while( f );
  }
}

/*****  Shell-Metzner  ******************************/
/*                                                  */
/****************************************************/

void Shell_Metzner( int *array, int elements, int delay_factor )
{
int p, k, t, i, j;

p = elements;
p /= 2;
while ( p != 0 )
  {
  k = elements - p;
  for ( t = 0; t < k; t++ )
    {
    i = t;
    while ( i >= 0 )
      {
      j = i + p;
      if (*(array+j) < *(array + i))
        {
        Swap_Pixels( array, i, j, delay_factor );
        i = i - p;
        }
      else
        break;
      }
    }
  p /= 2;
  }
}

/*****  Quicksort  **********************************/
/*                                                  */
/****************************************************/

void Quicksort( int *array, int left, int right, int delay_factor )
{
 int i, j, t;

 if ( right > left )
 {
  i = left - 1; j = right;
  do {
      do i++;
        while ( array[i] < array[right] );
      do j--;
        while ( array[j] > array[right] && j > 0 );
      t = Swap_Pixels( array, i, j, delay_factor );
     } while ( j > i );

      putpixel( 3*j, *(array + j), 0);
      array[j] =array[i];
      putpixel( 3*j, *(array + j), 10 );
      putpixel( 3*i, *(array + i), 0 );
      /* putpixel( 3*right, *(array + right), 0); <-- putting this stmt
        here causes duplicate pixels...         */
      array[i] =array[right];
      putpixel( 3*i, *(array + i), 10 );
      /* on the other hand, this one works... why? maybe if
       array[i] ==array[right] there's a problem...   */
      putpixel( 3*right, *(array + right), 0 );
      array[right] = t;
      putpixel( 3*right, *(array + right), 10 );

      Quicksort( array, left, i - 1, delay_factor );
      Quicksort( array, i + 1, right, delay_factor );

  }
}


/*****  Insertion  **********************************/
/*                                                  */
/****************************************************/

void Insertion( int *array, int elements, int delay_factor )
{
 int p, j, t;


 for ( p = 0; p < elements - 1; p++ )
   {
    t = *(array + p + 1);
    for ( j = p; j >= 0; j-- )
      {
       if ( t <= *(array + j) )
         {
          *(array + j + 1) = *(array + j);
          putpixel( 3*(j + 1), *(array + j + 1), 10 );
          putpixel( 3*j, *(array + j + 1), 0 );
          delay( delay_factor );
         }
       else
         break;
      }
    *(array + j + 1) = t;
    putpixel( 3*(p + 1), t, 0 );
    putpixel( 3*(j + 1), t, 10 );
   }
}

/*****  end code for csort.c  ********************************************/