"Bubble Sort", "Delayed Exchange Sort", "Shell Sort" & more..

[aruljothi]

#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 = 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 = 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 );
    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, "c:\tc\bgi" );
ErrorCode = graphresult();   /* Read result of initialization*/
if( ErrorCode != grOk )      /* Error occured during init  */
   {
    printf(" Graphics System Error: %s
", 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 < array

);
      do j--;
        while ( array[j] > array

&& j > 0 );
      t = Swap_Pixels( array, i, j, delay_factor );
     } while ( j > i );

      putpixel( 3*j, *(array + j), 0);
      array[j] =array;
      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 =array

;
      putpixel( 3*i, *(array + i), 10 );

/*
On the other hand, this one works... why? maybe if array ==array

there's a problem...   
*/

      putpixel( 3*right, *(array + right), 0 );
      array

= 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 ********************************************/