Category : C Source Code
Archive : SORTDEMO.ZIP
Filename : SORTDEMO.C
Output of file : SORTDEMO.C contained in archive : SORTDEMO.ZIP
*
* 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
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
}
if (j!=i){
move(j,i);
i++;
}
while((keyless(a[i],temp))&&(i
}
if (j!=i){
move(i,j);
}
}
fromtemp(j);
if (L
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
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();
}
Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!
This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.
But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/