Category : C Source Code
Archive   : SORTDEMO.ZIP
Filename : SORTDEMO.C

 
Output of file : SORTDEMO.C contained in archive : SORTDEMO.ZIP

/* sortdemo.c
*
* By Jeff Schmitt
* Towson State University
*/

#include
#define NUM 200 /*number of values to be sorted*/
#define True 1
#define False 0

/* Define the sorting methods to be used */
#define Bubble 0
#define Insertion 1
#define Selection 2
#define Heap 3
#define Quick 4
#define Shell 5
#define Tree 6

/* Define the data file input orderings */
#define Ordered 0
#define Random 1
#define Inverse 2

int a[NUM],dataordered[NUM],datarandom[NUM],datainverse[NUM];

int comparecount=0, movecount=0;
struct resultrec {
char name[10];
int moves[3];
int compares[3];
};
struct resultrec results[7]={0};
struct treerec{
int data;
struct treerec *left;
struct treerec *right;
};

#define nil (struct treerec *)0
struct treerec *root=nil;

int temp=0,p=0;
int choice=0;
int sort=0;
int data=0;
/*******************************************/
/* End Variables */
/*******************************************/

void readoriginal()
{
int i;
for (i=0;i<=NUM;i++){
dataordered[i]=i;
}
for (i=0;i<=NUM;i++){
datarandom[i]=abs(rand() % NUM);
}
for (i=0;i<=NUM;i++){
datainverse[i]=dataordered[NUM-i];
}
}

void printresults()
{
int i,j;
for (i=Bubble;i<=Tree;i++){
for (j=Ordered;j<=Inverse;j++){
printf("%d %d",results[i].compares[j],results[i].moves[j]);
}
}
}

void totemp(lrg)
int lrg;
{
temp=a[lrg];
movecount++;
}

void fromtemp(sml)
int sml;
{
a[sml]=temp;
movecount++;
}

void move(lrg,sml)
int lrg,sml;
{
a[lrg]=a[sml];
movecount++;
}

void exchange(lrg,sml)
int lrg,sml;
{
totemp(lrg);
move(lrg,sml);
fromtemp(sml);
}

int keyless(a,b)
int a,b;
{
comparecount++;
return a }

void bubblesort()
{
int i,j,flag; /*flag used as boolean*/
i=1;
flag=True;
while (flag && (i flag=False;
for (j=1;j<=NUM;j++){
if (keyless(a[j+1],a[j])){
flag=True;
exchange(j,j+1);
}
}
i++;
}
}

/*insertionsort compiles but does not work properly*/
void insertionsort()
{
int i,j,done; /*done is boolean*/
for (i=2;i<=NUM;i++){
if (keyless(a[i],a[i-1])){
totemp(i);
done=False;
j=i-1;
while((!done) && (j>=1)){
if (keyless(temp,a[j])){
move(j,j+1);
j--;
} else {
done=True;/*stop the while loop*/
}
}
fromtemp(j+1);
}
}
}

void selectionsort()
{
int i,j,k;
for (i=1;i<=(NUM-1);i++){
k=i;
for (j=(i+1);j<=NUM;j++){
if (keyless(a[j],a[k])){
k=j;
}
}
exchange(i,k);
}
}

void qsort(L,r)
int L,r;
{
int i,j,h1,h2;
i=L;
j=r;
totemp(L);
while(i while((keyless(temp,a[j]))&&(i j--;
}
if (j!=i){
move(j,i);
i++;
}
while((keyless(a[i],temp))&&(i i++;
}
if (j!=i){
move(i,j);
}
}
fromtemp(j);
if (L h1=L;h2=(j-1);
qsort(h1,h2);
}
if (r>i){
h1=i+1;h2=r;
qsort(h1,h2);
}
}

void quicksort()
{
qsort(1,NUM);
}

void shellsort()
{
int i,j,k;
i=NUM/2;
while(i>0){
j=i;
do{
j++;
k=j-i;
while (k>0){
if (keyless(a[k+i],a[k])){
exchange(k,k+i);
k=k-i;
} else {
k=0;
}
}
}while (j!=NUM);
i=i/2;
}
}

void walkdown(i,n)
int i,n;
{
int k;
k=2*i;
do{
if (k if (keyless(a[k],a[k+1])){
k++;
}
}
if (keyless(a[i],a[k])){
exchange(k,i);
i=k;
k=2*i;
}
else{
i=k;
k=2*i;
}
} while (k }

void heapsort()
{
int y;
y=NUM/2+1;
while (y>2){
y--;
walkdown(y,NUM);
}
y=NUM+1;
while (y>2){
y--;
walkdown(1,y);
exchange(1,y);
}
}

/*the tree routines compile but addressing error occurs*/
void buildtree(t)
struct treerec **t;
{
if (*t == nil){
*t=(struct treerec *) alloca(sizeof(struct treerec));
(*t)->data=temp;
(*t)->left=nil;
(*t)->right=nil;
} else {
if (keyless(temp,(*t)->data)){
buildtree(&(*t)->left);
}else{
buildtree(&(*t)->right);
}
}
}

void inorder(t)
struct treerec *t;
{
if (t!=nil){
inorder(t->left);
p++;
temp=t->data;
fromtemp(p);
inorder(t->right);
}
}

void treesort()
{
struct treerec *root;
root=nil;
for (p=1;p<=NUM;p++){
totemp(p);
buildtree(&root);
}
p=0;
inorder(root);
}

void initialize()
{
}

main()
{
initialize();
readoriginal();
for (data=Ordered;data<=Inverse;data++){
for (sort=Insertion;sort<=Tree;sort++){
switch (data){
case Ordered:
for (p=1;p<=NUM;p++){
a[p]=dataordered[p];
}
break;
case Random:
for (p=1;p<=NUM;p++){
a[p]=datarandom[p];
}
break;
case Inverse:
for (p=1;p<=NUM;p++){
a[p]=datainverse[p];
}
break;
}
movecount=0;
comparecount=0;
switch (sort){
case Bubble:
bubblesort();
break;
case Insertion:
insertionsort();
break;
case Selection:
selectionsort();
break;
case Heap:
heapsort();
break;
case Quick:
quicksort();
break;
case Shell:
shellsort();
break;
case Tree:
treesort();
break;
}
results[sort].moves[data]=movecount;
results[sort].compares[data]=comparecount;
}
printresults();
}
for (data=Ordered;data<=Inverse;data++){
movecount=0;
comparecount=0;
switch (data){
case Ordered:
for (p=0;p<=NUM;p++){
a[p]=dataordered[p];
}
break;
case Random:
for (p=0;p<=NUM;p++){
a[p]=datarandom[p];
}
break;
case Inverse:
for (p=0;p<=NUM;p++){
a[p]=datainverse[p];
}
break;
}
bubblesort();
results[Bubble].moves[data]=movecount;
results[Bubble].compares[data]=comparecount;
}
printresults();
}