Search This Blog

Sunday 7 August 2016

Counting Sort

#include <stdio.h>
#include <stdlib.h>
void count(int A[],int k,int n)
{
    int i,j;
    int B[10],C[15];
    for(i=0;i<=k;i++)
    {
        C[i]=0;
    }
    for(j=1;j<=n;j++)
    {
        C[A[j]]= C[A[j]] +1;
    }

    for(i=1;i<=k;i++)
        C[i]= C[i]+C[i-1];

    for(j=n;j>=1;j--)
    {
        B[C[A[j]]] = A[j];
        C[A[j]] = C[A[j]] -1;
    }

    printf("Sorted array is:\n");
    for(i=1;i<=n;i++)
    {
        printf("%d ",B[i]);
    }

}

int main()
{
    int n,A[15],k=0,i;
    printf("Enter n\n");
    scanf("%d",&n);
    printf("\nEnter ele:");
    for(i=1;i<=n;i++)
    {
        scanf("%d",&A[i]);
        if(A[i]>k)
            k=A[i];
    }
    count(A,k,n);

    return 0;
}

Friday 5 August 2016

Merge Sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

long int n=100000,a[100000];

void merge(long int begin,long int mid, long int end,long int a[])
{
long int i=begin,j=mid+1,temp[end],cnt=0;
while(cnt<(end-begin+1))
{
if(i==mid+1)
{
temp[cnt++]=a[j];
j++;
}
else if(j==end+1)
{
temp[cnt++]=a[i];
i++;
}
else
{
if(a[i]<a[j])
{
temp[cnt++]=a[i];
i++;
}
else
{
temp[cnt++]=a[j];
j++;
}
}
}
for(i=begin;i<=end;i++)
a[i]=temp[i-begin];
}

void divide(long int a,long int b,long int y[])
{
long int mid=(b-a)/2+a;
if((b-a)>1)
{
divide(a,mid,y);
divide(mid+1,b,y);
}
merge(a,mid,b,y);
}

int main()
{
struct timeval  tv1, tv2;
 
long int mid;
for(long int i=0;i<n;i++)
a[i]=rand();

gettimeofday(&tv1, NULL);

mid=(n-1)/2;
divide(0,mid,a);
divide(mid+1,n-1,a);
merge(0,mid,n-1,a);

gettimeofday(&tv2, NULL);
printf("Time taken in execution = %f micro-seconds\n",
    (double) (tv2.tv_usec - tv1.tv_usec));
    return 0;
}

Insertion Sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

int main()
{
long timedif;
struct timeval tpstart;
struct timeval tpend;
struct timeval now;
int rc;

now.tv_sec=000000000;
now.tv_usec=000000;

rc=settimeofday(&now, NULL);

if(rc==0)
{
printf("settimeofday() failed.\n");
}
else
{
printf("\nsettimeofday() Succesful\n");
printf("\nTime Set sec=%ld Msec=%ld\n",now.tv_sec,now.tv_usec);
}

gettimeofday(&tpstart, NULL);

long int n=100000;
long int a[n];

for(long int i=0;i<n;i++)
{
long int temp=random(),flag=1;
for(long int j=0;j<i;j++)
{
if(temp<a[j])
{
for(long int k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=temp;
flag=0;
break;
}
}
if(flag==1)
a[i]=temp;
}

gettimeofday(&tpend, NULL);
timedif = 1000000 * (tpend.tv_sec - tpstart.tv_sec) + tpend.tv_usec - tpstart.tv_usec;

printf("\nTime difference is:%ld\n",timedif);
}


Selection sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

long int n=100000,a[100000];

int main()
{
struct timeval  tv1, tv2;
   
for(long int i=0;i<n;i++)
a[i]=rand();

gettimeofday(&tv1, NULL);

for(long int i=0;i<n;i++)
{
long long int min=a[i],ind=i;
for(long int j=i+1;j<n;j++)
{
if(min>a[j])
{
min=a[j];
ind=j;
}
}
a[ind]=a[i];
a[i]=min;
//cout << a[i] << endl;
}

gettimeofday(&tv2,NULL);
printf("Time taken in execution = %f micro-seconds\n",
    (double) (tv2.tv_usec - tv1.tv_usec));
    return 0;
}


Bubble Sort

#include<stdio.h>
#include<math.h>
#include<sys/time.h>
#include<stdlib.h>
#include<iostream>

using namespace std;

long int n=100000,a[100000];

int main()
{
     struct timeval tv1, tv2;

     for(long int i=0;i<n;i++)
     a[i]=rand();

     gettimeofday(&tv1, NULL);

     for(long int i=0;i<n;i++)
     {
           for(long int j=i;j<n;j++)
           {
                 if(a[i]>a[j])
                 {
                        long int temp;
                        temp=a[i];
                        a[i]=a[j];
                        a[j]=temp;
                  }
           }
     }

     gettimeofday(&tv2, NULL);
     printf("Time taken in execution = %f micro-seconds\n",(double) (tv2.tv_usec - tv1.tv_usec));
     return 0;
}