Wednesday, September 19, 2012

Algorithm LAB _ WAP to implement INSERTION-SORT

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void sort(int *a,int n);

void sort(int *a,int n)
    {
    int i,j,c;
    for(j=1;j<n;j++)
        {
        c=a[j];
        i=j-1;
        while(i>=0 && a[i]>c)
            {
            a[i+1]=a[i];
            i=i-1;
            }
        a[i+1]=c;
        }
    }

int main()
    {
    FILE *f1,*f2,*f3;
    time_t start,end;
    double timetaken;
    srand(time(NULL));
    int *a,n,i,j;
    printf("enter the size of the array to be sorted\n");
    scanf("%d",&n);
    a=(int*)malloc(n*sizeof(int));
   
    f1=fopen("data1.txt","w+");
    for(i=0;i<n;i++)
        fprintf(f1,"%d\n",rand()%n);
    rewind(f1);
    i=0;
    while(fscanf(f1,"%d",&a[i])!=EOF)
        {
        i++;
        }
    fclose(f1);

    start=clock();
    sort(a,n);
    end=clock();
    timetaken=(double)(end-start)/(CLOCKS_PER_SEC);
    printf("the timetaken for average case is %lf",timetaken);

    f2=fopen("data2.txt","w+");
    for(i=0;i<n;i++)
        fprintf(f2,"%d\n",i);
    rewind(f2);
    i=0;
    while(fscanf(f2,"%d",&a[i])!=EOF)
        i++;
    fclose(f2);

    start=clock();
    sort(a,n);
    end=clock();
    timetaken =(double)(end-start)/(CLOCKS_PER_SEC);
    printf("\nthe time taken for the best case is %lf",timetaken);
   
    f3=fopen("data3.txt","w+");
    for(i=n;i>0;i--)
        fprintf(f3,"%d\n",i);
    rewind(f3);
    i=0;
    while(fscanf(f3,"%d",&a[i])!=EOF)
        i++;
    fclose(f3);

    start=clock();
    sort(a,n);
    end=clock();
    timetaken=(double)(end-start)/(CLOCKS_PER_SEC);
    printf("\n the time taken for the worst case is %lf",timetaken);

    return 0;
    }

No comments: