home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
High Voltage Shareware
/
high1.zip
/
high1
/
DIR41
/
CUJ0793.ZIP
/
SORTNET.C
< prev
next >
Wrap
C/C++ Source or Header
|
1993-02-04
|
2KB
|
83 lines
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int print_swaps;
long n_swaps;
void show( int a, int b)
{
if( print_swaps)
printf( "swap %d %d\n", a, b);
n_swaps++;
}
long merge_sort( int n_elems)
{
if( n_elems == 2)
return( 1L);
if( n_elems == 1)
return( 0L);
return( merge_sort( n_elems / 2) + merge_sort( n_elems - n_elems / 2)
+ (long)n_elems - 1L);
}
void bracket( int start1, int n_elem1, int start2, int n_elem2)
{
if( n_elem1 == 1 && n_elem2 == 1)
show( start1, start2);
else if( n_elem1 == 1 && n_elem2 == 2)
{
show( start1, start2 + 1);
show( start1, start2);
}
else if( n_elem1 == 2 && n_elem2 == 1)
{
show( start1, start2);
show( start1 + 1, start2);
}
else
{
int a = n_elem1 / 2, b = (n_elem1 & 1) ? n_elem2 / 2 : (n_elem2 + 1) / 2;
bracket( start1, a, start2, b);
bracket( start1 + a, n_elem1 - a, start2 + b, n_elem2 - b);
bracket( start1 + a, n_elem1 - a, start2, b);
}
}
void pstar( int start, int n_elem)
{
if( n_elem > 1)
{
int m = n_elem / 2;
pstar( start, m);
pstar( start + m, n_elem - m);
bracket( start, m, start + m, n_elem - m);
}
}
void main( int argc, char **argv)
{
double z = 0;
int i, n_elems = atoi( argv[1]);
if( argc < 2)
{
printf( "SORTNET expects a number of elements as a command line\n");
printf( "argument. Adding another argument will suppress printing\n");
printf( "the individual swaps and will give totals only.\n");
exit( 0);
}
print_swaps = (argc == 2);
pstar( 1, n_elems);
printf( "%ld swaps required\n", n_swaps);
for( i = 2; i <= n_elems; i++)
z += log( (double)i);
z = ceil( z / log( 2.));
printf( "Theoretical: %ld\n", (long)z);
printf( "Swaps for merge sort: %ld\n", merge_sort( n_elems));
}