|
Displaying Source Code(s)
|
|
"Bubble Sort", "Delayed Exchange Sort", "Shell Sort" & more..
--------------------------------------------------------------------------------
Description : All sorting method using C Graphics ....
#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<BR>, 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
********************************************/
|
|
|
123
Eng