#include //iostream.h
#include //fstream.h
#include //graphics.h
#include //stdlib.h
#include //conio.h
#include //string.h
#include //stdio.h
#include //dos.h
#include //time.h
#include //math.h
struct name
{
char s[20];
}data;
int x = 200,y = 50;
void printheap(char p[][20],int n,int s,int z,int d)
{
cleardevice();
outtextxy(300,10,"HEAP SORT");
char *t = "";
strcpy(t,"");
sprintf(t,"%d",d);
outtextxy(550,240,"Count:");
outtextxy(550,260,t);
setbkcolor(9);
for(int i =0;i {
if(i==s)
setcolor(BLUE);
else if(i==z)
setcolor(14);
else
setcolor(RED);
outtextxy(x,y+i*50,p[i]);
setcolor(14);
rectangle(x-20,y+i*50 -20,x+300,y+i*50+30);
}
delay(2000);
getch();
}
int d = 0;
void max_heapify(char p[][20],int x,int s,int n)
{
char t[20] = "";
while(x)
{
top:
if((x*2+1)<=s)
{
if (strcmp(p[x],p[x*2+1])<0)
{
//swap;
strcpy(t,p[x]);
strcpy(p[x],p[x*2+1]);
strcpy(p[x*2+1],t);
x=x*2+1;
d++;
printheap(p,n,s,x,d);
goto top;
}
}
if (2*x<=s)
{
if (strcmp(p[x],p[x*2])<0)
{
//swap;
strcpy(t,p[x]);
strcpy(p[x],p[x*2]);
strcpy(p[x*2],t);
x=x*2;
d++;
printheap(p,n,s,x,d);
goto top;
}
}
x--;
}
}
void printins(char p[][20],int n,int j,int k)
{
outtextxy(300,10,"INSERTION SORT");
for(int i =0;i {
if(i==j)
setcolor(BLUE);
else
setcolor(RED);
outtextxy(x,y+i*50,p[i]);
if(i==k)
{
setcolor(14);
rectangle(x-18,y+i*50-18,x+298,y+i*50+28);
}
else
setcolor(BLUE);
rectangle(x-20,y+i*50 -20,x+300,y+i*50+30);
setcolor(RED);
}
// delay(2000);
}
void printbub(char p[][20],int n,int k, int j,int t)
{
x = 200;
y = 50;
outtextxy(300,10,"BUBLE SORT");
for(int i = 0;i {
setcolor(YELLOW);
line(0,y+t*50-20,640,y+t*50-20);
if(i==k)
setcolor(BLUE);
else if(i==j)
{
setcolor(14);
rectangle(x-20,y+i*50 -20,x+300,y+i*50+30);
rectangle(x-18,y+i*50-18,x+298,y+i*50+28);
setcolor(GREEN);
}
else
{
setcolor(RED);
}
rectangle(x-20,y+i*50 -20,x+300,y+i*50+30);
outtextxy(x,y+i*50,p[i]);
}
// delay(2000);
}
void printsel(char p[][20],int n,int index,int t)
{
x = 200;
y = 50;
outtextxy(300,10,"SELECTION SORT");
for(int i = 0;i {
setcolor(YELLOW);
line(0,y+t*50-20,640,y+t*50-20);
if(i==index)
{
setcolor(14);
rectangle(x-20,y+i*50 -20,x+300,y+i*50+30);
rectangle(x-18,y+i*50-18,x+298,y+i*50+28);
setcolor(GREEN);
}
else
{
setcolor(RED);
}
rectangle(x-20,y+i*50 -20,x+300,y+i*50+30);
outtextxy(x,y+i*50,p[i]);
}
// delay(2000);
}
void main()
{
clrscr();
int gd=DETECT,gm;
initgraph(&gd,&gm,"x:\\bgi\\");
int ch;
do
{
cleardevice();
cout<<"\nMenu:";
cout<<"\n\n1.Add new name:";
cout<<"\n2.Insertion sort:";
cout<<"\n3.Bubble sort:";
cout<<"\n4.Selection Sort:";
cout<<"\n5.Heap Sort:";
cout<<"\n6.Compare time:";
cout<<"\n7.Exit:";
cout<<"\n\nEnter your choice:";
cin>>ch;
char * temp;
char p[20][20] = {0};
ifstream in;
char t[20] = "";
switch(ch)
{
case 1:
cout<<"\nEnter the first name:";
cin>>temp;
strcpy(data.s,"");
strcat(data.s,temp);
strcat(data.s," ");
cout<<"\nEnter the last name:";
cin>>temp;
strcat(data.s,temp);
ofstream out("x:\\files\\sem_3\\names.dat",ios::app);
out.write((char*)&data,sizeof(data));
out.close();
break;
case 2:
clock_t start1,end1;
start1 = clock();
in.open("x:\\files\\sem_3\\names.dat");
int n=0;
do
{
in.read((char*)&data,sizeof(data));
n++;
}
while(!in.eof());
in.close();
n--;
in.open("x:\\files\\sem_3\\names.dat");
in.read((char*)&data,sizeof(data));
strcpy(p[0],data.s);
char key[20] = "";
int i;
for(i = 1;i {
in.read((char*)&data,sizeof(data));
strcpy(p[i],data.s);
}
// getch();
for(int j = 1;j< n;j++)
{
strcpy(key,p[j]);
cleardevice();
setbkcolor(9);
setcolor(RED);
i = j - 1;
while(i>=0 && strcmp(p[i],key)>0)
{
cleardevice();
flushall();
outtextxy(x-100,y+j*50,"KEY:");
setcolor(GREEN);
outtextxy(x-150,y+j*50+20,key);
setcolor(RED);
printins(p,n,i,j);
strcpy(p[i+1],p[i]);
i = i - 1;
}
strcpy(p[i+1],key);
cleardevice();
outtextxy(x-100,y+j*50,"KEY:");
setcolor(GREEN);
flushall();
outtextxy(x-150,y+j*50+20,key);
setcolor(RED);
printins(p,n,j,j);
}
in.close();
// getch();
end1 = clock();
break;
case 3:
clock_t start2,end2;
flushall();
start2 = clock();
in.open("x:\\files\\sem_3\\names.dat");
n=0;
do
{
in.read((char*)&data,sizeof(data));
strcpy(p[n++],data.s);
}while(!in.eof());
in.close();
n--;
for(i=0;i {
for(int j=n-2;j>=i;j--)
{
cleardevice();
printbub(p,n,j,j+1,i);
if(strcmp(p[j],p[j+1])>0)
{
cleardevice();
setbkcolor(9);
setcolor(RED);
printbub(p,n,j,j+1,i);
strcpy(t,p[j+1]);
strcpy(p[j+1],p[j]);
strcpy(p[j],t);
}
}
}
end2 = clock();
break;
case 4:
flushall();
clock_t start3,end3;
cleardevice();
setbkcolor(9);
start3 = clock();
in.open("x:\\files\\sem_3\\names.dat");
n=0;
do
{
in.read((char*)&data,sizeof(data));
strcpy(p[n++],data.s);
}while(!in.eof());
in.close();
n--;
char min[20] = "";
int index=0;
for(i = 0;i {
cleardevice();
strcpy(min,p[i]);
index = i;
for(int j=i;j {
if(strcmp(min,p[j])>=0)
{
strcpy(min,p[j]);
index = j;
}
}
printsel(p,n,index,i);
strcpy(t,p[index]);
strcpy(p[index],p[i]);
strcpy(p[i],t);
}
cleardevice();
printsel(p,n,index,i);
end3 = clock();
break;
case 5: flushall();
clock_t start4,end4;
cleardevice();
setbkcolor(9);
start4 = clock();
in.open("x:\\files\\sem_3\\names.dat");
n=0;
do
{
in.read((char*)&data,sizeof(data));
strcpy(p[n++],data.s);
}while(!in.eof());
in.close();
n--;
int s = n-1,x;
while (s-1)
{
x=floor(s/2);
max_heapify(p,x,s,n);
d++;
printheap(p,n,s,x,d);
getch();
strcpy(t,p[0]);
strcpy(p[0],p[s]);
strcpy(p[s],t);
s--;
}
end4 = clock();
break;
case 6:
cout<<"\nInsertion: "<<(end1-start1)/CLK_TCK;
cout<<"\nBubble: "<<(end2-start2)/CLK_TCK;
cout<<"\nSelection: "<<(end3-start3)/CLK_TCK;
cout<<"\nHeap: "<<(end4-start4)/CLK_TCK;
getch();
break;
}
}while(ch!=7);
getch();
closegraph();
}
|