Posts Tagged BUBBLE SORT

Program for bubble sort in C++.

Posted by admin in C++ Examples on July 2nd, 2009 

#include<iostream>
using namespace std;
#include<stdio.h>
#include<time.h>
#include<stdlib.h>

void bubblesort(long int*);

void main()
{
long int i=0,c;
long int a[30000];
FILE *fp;
fp=fopen("input3.txt","r");
while(fscanf(fp,"%ld",&c)!=EOF)
{
a[i]=c;
//    cout<<a[i];
i++;
}
fclose(fp);

bubblesort(a);

fp=fopen("output3.txt","w");
for(i=0;i<30000;i++)
{
fprintf(fp,"%ld ",a[i]);
}
fclose(fp);
}

void bubblesort(long int*h)
{
clock_t start, finish;
double  duration;

long int temp;
start = clock();

for(int i=30000;i>1;i--)
{
for(int j=0;j<i-1;j++)
{
if(h[j]>h[j+1])
{
temp=h[j];
h[j]=h[j+1];
h[j+1]=temp;
}
}
}
finish = clock();
duration = (float)(finish - start) / CLOCKS_PER_SEC;
printf( "%2.3f seconds\n", duration );

}

,

7 Comments

Program for all types of Sortings in C.

Posted by admin in C Examples on July 1st, 2009 

#include <stdio.h>
#include<math.h>
int SIZE=10;
int ncomps[7],nswaps[7],time[7];
int fl=0;
FILE *fpp,*fp;
void insertion();
void exchange();
void shell1();
void shell2();
void fileopen();
void shell3();
void bubble();
void heap();
int sh2();
int sh3();
float value();
main()
{
int i;
fpp=fopen("as.txt","w");
insertion();
exchange();
shell1();
shell2();
shell3();
bubble();
heap();
fclose(fpp);
for (i=0;i<7;i++)
{
printf ("no %d----%d----%d-----%d\n",i+1,ncomps[i],nswaps[i],time[i]);
}
}

void insertion()
{
int aj1=0,aj2=0;
int i,j,k,a[SIZE];
fileopen();
for (i=0;i<SIZE;i++){
fscanf(fp,"%d",&a[i]);
}

printf("1-insertion sort\n");
for (i=1;i<SIZE;i++)
{
j=a[i];
for (k=i-1;k>=0&&a[k]>j;k--)
{a[k+1]=a[k];aj1++;}
a[k+1]=j;
aj2++;
}

ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj1;
fl++;
for (i=0;i<SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
fclose(fp);
return;
}

void exchange()
{
fileopen();
int aj1=0,aj2=0,aj3=0;
int i,t,mid,j,a[SIZE];
for (i=0;i<SIZE;i++){
fscanf(fp,"%d",&a[i]);
}

printf("2- exchange sort\n");
for (i=0;i<SIZE-1;i++)
{
t=i;
for(j=i+1;j<SIZE;j++)
{aj3++;
if(a[t]>a[j])
{t=j;aj1++;}}
mid=a[t];
a[t]=a[i];
a[i]=mid;
aj2++;
}
ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj3;
fl++;
for (i=0;i<SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
fclose(fp);
return;
}

void shell1()
{
int aj1=0,aj2=0,aj3=0;
int q,v,i,j,a[SIZE],mid,qe;
fileopen();
for (i=0;i<SIZE;i++){
fscanf(fp,"%d",&a[i]);
}
printf("3- shell sort\n");
for (i=(SIZE/2);i>0;(i/=2))
for (j=i;j<SIZE;j++)
{
mid=a[j];
for (q = j; q >= i && mid < a[q- i];q = q - i)
{a[q] = a[q-i];aj1++;}
a[q] = mid;aj2++;
}
ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj1;
fl++;
for (i=0;i<SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
fclose(fp);
return;
}

void shell2()
{
printf("4- shell sort hibbard's increament \n");
int i,v,q,j,mid,k,a[SIZE];
fileopen();
for (i=0;i<SIZE;i++){
fscanf(fp,"%d",&a[i]);
}
int aj1=0,aj2=0,aj3=0;

for(k=sh2(),i=(pow(2,k)-1);k!=0;k--,i=pow(2,k)-1)
for (j=i;j<SIZE;j++)
{
mid=a[j];
for (q = j; q >= i && mid < a[q- i];q = q - i)
{a[q] = a[q-i];aj1++;}
a[q] = mid;aj2++;
}

ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj1;
fl++;

for (i=0;i<SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
fclose(fp);
return;
}

void shell3()
{
printf("5- shell sort sedgewick increament\n");
int i,j,q,k,a[SIZE],mid;
float r;
fileopen();
for (i=0;i<SIZE;i++)
{
fscanf(fp,"%d",&a[i]);
}

int aj1=0,aj2=0,aj3=0;

for(k=sh3(),i=(int)(((9*pow(4,k))-(9*pow(2,k))+1));k>=0;k--,i=(int)(((9*pow(4,k))-(9*pow(2,k))+1)))
for (j=i;j<SIZE;j++)
{
mid=a[j];

for (q = j; q >= i && mid < a[q- i];q = q - i)
{a[q] = a[q-i];aj1++;}
a[q] = mid;aj2++;
}

for (i=0;i<SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
fclose(fp);

ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj1;
fl++;
return;
}
void bubble()
{
printf("6- bubble sort\n");
int i,j,mid,a[SIZE];
int aj1=0,aj2=0,aj3=0;
fileopen();
for (i=0;i<SIZE;i++){
fscanf(fp,"%d",&a[i]);
}

for(i=SIZE-1;i>0;i--)
for(j=0;j<i;j++)
{if(a[j]>a[j+1])
{
mid=a[j];a[j]=a[j+1];a[j+1]=mid;aj2++;
}aj1++;
}
ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj1;
fl++;
for (i=0;i<SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
fclose(fp);
return;
}

int sh2()
{
return (int)(log(SIZE)/log(2));
}

int sh3()
{
float x;
int y1,z1,q1,y2,z2,q2;
x=sqrt(9-(4*(1-SIZE)));

y1=(int)((9+3*x)/2);
z1=(int)((9-3*x)/2);
if(y1>0)
q1=(int)((log(y1))/(log(2)));
else if(z1>0)
q1= (int)((log(z1))/(log(2)));
else q1= 1;
return(q1);
}

void heap()
{
printf("7- heap sort\n");
int k,q,i,j,mid,temp,a[SIZE+1];
fileopen();
a[0]=-1;
int aj1=0,aj2=0,aj3=0;
for (j=1;j<=SIZE;j++)
{
i=j;
fscanf(fp,"%d",&temp);
q=(i/2);
for(a[j]=temp;a[i]>a[q]&&q!=0;i/=2,q/=2)
{aj3++;
mid =a[i];a[i]=a[q];a[q]=mid;
}
}

for (j=SIZE;j!=1;j--)
{
temp=a[j];a[j]=a[1];a[1]=temp;
for (k=1,q=2;(q<j)||(q+1<j);)
{aj1++;aj3++;
if(q+1<j)
{
if(a[q]<a[q+1])
{
mid=a[k];a[k]=a[q+1];a[q+1]=mid;aj2++;
k=k*2+1;
}
else
{
mid=a[k];a[k]=a[q];a[q]=mid;
k*=2;aj2++;
}
}
else if(q<j+1)
{
mid=a[k];a[k]=a[q];a[q]=mid;
k=k*2;aj2++;
}
else break;
q=2*k;
}
}

ncomps[fl]=aj1;nswaps[fl]=aj2;time[fl]=aj3;

for (i=1;i<=SIZE;i++)
fprintf(fpp,"%d\t",a[i]);
fprintf(fpp,"\n");
return;
}

void fileopen()
{
fp=fopen("x.txt","r");
if(fp==NULL)
{
printf("ERROR IN OPEANING THE FILE\n");
exit(1);
}
}

, , , , , ,

No Comments

PROGRAM TO ANALYSE VARIOUS SORTING TECHNIQUES.

Posted by admin in C++ Examples on June 18th, 2009 

#include<iostream.h>         //HEADER FILES
#include<time.h>
#include<fstream.h>
#include<math.h>

fstream file;
int record[30000],copy[30000];            //TO STORE DATA
long comp=0,avgcomp;
long swp,avgswp;
long avgtime;

void bubblesort(int x[],int n)           //BUBBLE SORT
{
int hold,j,i;
int swapped=1;
comp=swp=0;
for(i=0;i<n-1&&swapped==1;i++)
{
swapped=0;
for(j=0;j<n-i;j++)
{
comp++;
if(x[j]>x[j+1])
{
swapped=1;
swp++;
hold=x[j];
x[j]=x[j+1];
x[j+1]=hold;
}
}
}
}

void insertsort(int x[],int n)               //INSERTION SORT
{
int i,j,temp;
comp=swp=0;
for(i=0;i<n;i++)
{
temp=x[i];
for(j=i-1;j>=0&&temp<x[j];j--)
{
comp++;
swp++;
x[j+1]=x[j];
}
x[j+1]=temp;
swp++;
}
}

void selectsort(int x[],int n)          //EXCHANGE SORT
{
int i,j,index,min;
comp=swp=0;
for(i=0;i<n-1;i++)
{
min=x[i];
index=i;
for(j=1+i;j<n;j++)
{
comp++;
if(x[j]<min)
{
min=x[j];
index=j;
}
}
if(index!=i)
{
x[index]=x[i];
x[i]=min;
swp++;
}
}
}

void shellsort(int x[], int n)         //SHELL SORT - SHELL'S INCREMENTS
{
int i, j,k, increment, temp;
swp=comp=0;
increment = n/2;
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
comp++;
swp++;
x[k+increment]=x[k];
}
x[k+increment]=temp;
swp++;
}
}
comp++;
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}

void hibbardsort(int x[], int n)       //SHELL SORT - HIBBARD'S INCREMENTS
{
int i, j,k, increment, temp;
swp=comp=0;
int val;
val=log(n+1)/log(2);
increment =pow(2,val)-1;
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
comp++;
swp++;
x[k+increment]=x[k];
}
x[k+increment]=temp;
swp++;
}
}
comp++;
val--;
if(increment!=1)
increment=pow(2,val)-1;
else
increment = 0;
}
}

void sedgewicksort(int x[], int n)     //SHELL SORT - SEDGEWICK'S INCREMENTS
{
int i, j,k, increment, temp;
swp=comp=0;
int val,incrmnt[]={16001,8929,3905,2161,929,505,209,109,41,19,5,1};
val=0;
increment =incrmnt[val];
while (increment > 0)
{
for (i=0;i<increment;i++)
{
for(j=0;j<n;j+=increment)
{
temp=x[j];
for(k=j-increment;k>=0&&temp<x[k];k-=increment)
{
comp++;
swp++;
x[k+increment]=x[k];
}
x[k+increment]=temp;
swp++;
}
}
comp++;
val++;
if(incrmnt[val-1]!=1)
increment=incrmnt[val];
else
increment = 0;
}
}

void main()                  //EXECUTION STARTS HERE
{
int i,j,k,l,valid;
file.open("records.txt",ios::in);
for(i=0;i<30000;i++)          //READ RECORDS
file>>record[i];
file.close();

long p,q,r;
cout<<"\n\n WAIT..........................";

file.open("bubble.txt",ios::out);         //BUBBLE SORT
for(k=1;k<=300;k++)
{
valid=100*k;
r=0.0;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
bubblesort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("select.txt",ios::out);       //EXCHANGE SORT
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
selectsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("insert.txt",ios::out);         //INSERTION SORT
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
insertsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("shell.txt",ios::out);    //SHELL SORT - SHELL'S INCREMENTS
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
shellsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("hibbard.txt",ios::out); //SHELL SORT - HIBBARD'S INCREMENTS
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
hibbardsort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();

file.open("sedgewick.txt",ios::out);   //SHELL SORT - SEDGEWICK'S INCREMENTS
for(k=1;k<=300;k++)
{
valid=100*k;
for(j=0;j<valid;j++)
copy[j]=record[j];
p=clock();
sedgewicksort(copy,valid);
q=clock();
avgtime=(q-p)*1000/CLOCKS_PER_SEC;
avgcomp=comp;
avgswp=swp;
file<<avgtime<<"\t"<<avgcomp<<"\t"<<avgswp<<"\n";
}
file.close();
}

, , , , , ,

No Comments