Write user defined functions for the following sorting methods and compare their performance by time measurement with random data and Sorted data.


SELECTION SORT:

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<time.h>
#define n 10000

void selection_sort(int[]);
unsigned long int count=0;
void main()
{
            int a[n];
            int choice,i;
            clrscr();
            printf("1.Sorted Data  2.Random Data \n");
            scanf("%d",&choice);
            switch(choice)
            {
                        case 1:
                                    for(i=0;i<n;i++)
                                    {
                                                a[i]=i+1;
                                    }
                                    selection_sort(a);
                                    break;
                        case 2:
                                    for(i=0;i<n;i++)
                                    {
                                                a[i]=n-i;
                                    }
                                    selection_sort(a);
                                    break;
                       
                               default:
                                    printf("Choice is not appropiate");
                                    getch();
                                    break;
            }
            getch();
}

void selection_sort(int a[])
{
            int min,i,j,temp;
            double total_time;
            clock_t start,end;
            srand(time(NULL));
            start = clock();
            for(i=0;i<size;i++)
            {
                        min=i;
                        for(j=i+1;j<size;j++)
                        {
                                    if(a[j]<a[min])
                                    {
                                                min=j;
                                    }
                        }
                        if(min!=i)
                        {
                                    temp=a[min];
                                    a[min]=a[i];
                                    a[i]=temp;
                        }
            }
end =  clock();
total_time = ((double)(end - start)) / CLK_TCK;
 printf(“time : %f”,total_time);         
}

BUBBLE SORT:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<time.h>
#define size 10000

void bubble_sort(int[]);
unsigned long int count=0;
void main()
{
            int a[size];
            int choice,i;
            clrscr();
            printf("1.Sorted Data  2.Random Data \n");
            scanf("%d",&choice);
            switch(choice)
            {
                        case 1:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=i+1;
                                    }
                                    bubble_sort(a);
                                    break;
                        case 2:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=size-i;
                                    }
                                    bubble_sort(a);
                                    break;
                        default:
                                    printf("Choice is not appropiate");
                                    getch();
                                    break;
            }
            getch();
}

void bubble_sort(int a[])
{
            int flag,i,j,temp;
            for(i=0;i<size-1;i++)
            {
                        flag=0;
                        for(j=0;j<size-i-1;j++)
                        {
                                    if(a[j]>a[j+1])
                                    {
                                                temp=a[j];
                                                a[j]=a[j+1];
                                                a[j+1]=temp;
                                                flag=1;
                                    }
                        }
                        if(flag==0)
                        {
                        return;
                        }
            }
}

INSERTION SORT:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<time.h>
#define size 10000

void insertion_sort(int[]);
unsigned long int count=0;
void main()
{
            int a[size];
            int choice,i;
            clrscr();
            printf("1.Sorted Data  2.Random Data \n");
            scanf("%d",&choice);
            switch(choice)
            {
                        case 1:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=i+1;
                                    }
                                    insertion_sort(a);
                                    break;
                        case 2:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=size-i;
                                    }
                                    insertion_sort(a);
                                    break;
                        default:
                                    printf("Choice is not appropiate");
                                    getch();
                                    break;
}
            getch();
}

void insertion_sort(int a[])
{
            int key,i,j;
           
for(j=1;j<=size;j++)
            {
                        key=a[j];
                        i=j-1;
            while(i>=0 && a[i]>key)
                        {
                                    a[i+1] = a[i];
                                    i= i-1;
                        }
                        a[i+1] =key;
            }
}

MERGE SORT:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define size 10000
void merge_sort(int[],int,int);
void merge(int[],int,int,int);
unsigned long int count=0;
void main()
{
            int a[size];
            int choice,i;
            clrscr();
            printf("1.Sorted Data  2.Random Data \n");
             scanf("%d",&choice);
            switch(choice)
            {
                        case 1:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=i+1;
                                    }
                                    merge_sort(a,0,size-1);
                                    break;
                        case 2:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=size-i;
                                    }
                                    merge_sort(a,0,size-1);
                                    break;
                        default:
                                    printf("Choice is not appropiate");
                                    getch();
                                    break;
            }
            getch();
}

void merge_sort(int a[],int start,int finish)
{
            int middle,s;
            s=(finish-start)+1;
            if(s<=1)
            {
                        return;
            }
            middle = start+(s/2)-1;
            merge_sort(a,start,middle);
            merge_sort(a,middle+1,finish);
            merge(a,start,middle+1,finish);
}

void merge(int a[],int first,int second,int third)
{
            int i=first,j=second,l=-1,temp[size];
            while(i<second && j<=third)
            {
                        if(a[i]<=a[j])
                        {
                                    l++;
                                     temp[l]=a[i];
                                    i++;
                        }
                        else
                        {
                                    l++;
                                    temp[l]=a[j];
                                    j++;
                        }
            }
           
            if(i>=second)
            {
                        while(j<=third)
                        {
                                    l++;
                                    temp[l]=a[j];
                                    j++;
                        }
            }
            else
            {
                        while(i<second)
                        {
                                    l++;
                                    temp[l]=a[i];
                                    i++;
                        }
            }
            for(i=0;i<=l;i++)
            {
                        a[first+i]=temp[i];
            }
}

QUICK SORT:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<time.h>
#define size 10000

void quick_sort(int [],int,int);
unsigned long int count=0;
void main()
{
            int a[size];
            int choice,i;
            clrscr();
            printf("1.Sorted Data  2.Random Data \n");
            scanf("%d",&choice);
            switch(choice)
            {
                        case 1:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=i+1;
                                    }
                                    quick_sort(a,0,size-2);
                                    break;
                        case 2:
                                    for(i=0;i<size;i++)
                                    {
                                                a[i]=size-i;
                                    }
                                    quick_sort(a,0,size-2);
                                    break;
                        default:
                                    printf("Choice is not appropiate");
                                    getch();
                                    break;
            }
            getch();
}

void quick_sort(int a[],int lb,int ub)
{
            int flag=1,i,j,temp,key;
             double total_time;
            clock_t start,end;
            srand(time(NULL));
            start = clock();

            if(lb<ub)
            {
                        i=lb;
                        j=ub+1;
                        key=a[lb];
                        while(flag)
                        {
                                    i++;
                                    while(a[i]<key && i<ub)
                                    {
                                                i++;
                                    }
                                    j--;
                                    while(a[j]>key)
                                    {
                                                j--;
                                    }
                                    if(i<j)
                                    {
                                                temp=a[i];
                                                a[i]=a[j];
                                                a[j]=temp;
                                    }
                                    else
                                    {
                                                flag=0;
                                    }
                                    temp=a[lb];
                                    a[lb]=a[j];
                                    a[j]=temp;
                                    quick_sort(a,lb,j);;
                                    quick_sort(a,j+1,ub);
                        }
            }
end = clock();
total_time  =  ((double)(end - start)) / CLK_TCK;
printf(“Time : %f”,total_time);
}


Location: Mehsana, Gujarat, India

Comments

Post a Comment

Popular posts from this blog

Implement functions to print nth Fibonacci number using iteration and recursive method.

Image
Implement functions to print nth Fibonacci number using iteration and recursive method. Compare the performance of two methods by counting number of steps executed on various inputs. Also draw a comparative chart. (Fibonacci series 1, 1, 2, 3, 5, 8…..  Here 8 is the 6th Fibonacci number) #include<stdio.h> #include<conio.h> int iteration(int); int recursive(int); int count=0; void main() { int n,choice,ans; clrscr(); printf("\nenter nth number : "); scanf("%d",&n); printf(“\n==iteration==”); ans=iteration(n); printf(“\nans=%d\ncount=%d”,ans,count); printf(“\n\n==recursive==”); ans=recursive(n); printf("\nans=%d\ncount=%d",ans,count); getch(); } int iteration(int n) { int f=1,s=1,t,i; count++;   count++; for(i=3;i<=n;i++) { t=f+s; count++; f=s; count++; s=t; count++; } count++; return t; } int recursive(int n) { count++; if(n==0 || n==1) { cou...
Read more

Implement program for randomized version of quick sort and compare its performance with normal version of quick sort using steps count on various number of inputs.

RANDOMIZED QUICK SORT: #include<stdio.h> #include<conio.h> #define size 10 unsigned long count=0; void randomized_quick(int a[],int low,int high) {       int pivot;       count++;       count++;       if(low<high)       {                   count++;                   pivot=randomized_part(a,low,high);                   count++;                   randomized_quick(a,low,pivot-1);                   cou...
Read more