Computer Science Canada

csort.cpp
Author:  alpesh [ Wed Jan 28, 2004 7:11 am ]
Post subject:  csort.cpp
// Turbo C


#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, "c:\\tc\\bgi" );
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 ********************************************/

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy