T 20 Match 5 original

1. BFS

#include<stdio.h>

#include<time.h>

void bfs(int a[10][10],int n,int source)

{

      int s[10],q[10],f=0,r=-1,t,v;

       for(v=0;v<n;v++)

      {

                  s[v]=0;

      }

      q[++r]= source;

      s[source]=1;

      while(f<=r)

      {

                  t=q[f++];

                  for(v=0; v<n; v++)

                  if(a[t][v]==1 && s[v]==0)

                  {

                              q[++r]=v;

                                    printf("The BFS traversal is:\n %d %d", t, v);

                              s[v]=1;

                  }

      }

  }

 

 

void main()

{

      int a[10][10],n,i,j,s;

      double clk;

      clock_t starttime,endtime;

      printf("\n Enter the number of cities\n");

      scanf("%d",&n);

      printf("\nEnter the matrix represention:");

      for(i=0;i<n;i++)

      for(j=0;j<n;j++)

      scanf("%d",&a[i][j]);

      printf("\nEnter the source city");

      scanf("%d",&s);

      starttime=clock();

      bfs(a,n,s);

      endtime=clock();

      clk=((double)(endtime-starttime)/CLOCKS_PER_SEC)*1000;

      printf("\nThe run time is %f ms\n",clk);

 

}

2. DFS

#include<stdio.h>

#include<time.h>

void bfs(int a[10][10],int n,int source)

{

      int s[10],q[10],f=0,r=-1,t,v;

       for(v=0;v<n;v++)

      {

                  s[v]=0;

      }

      q[++r]= source;

      s[source]=1;

      while(f<=r)

      {

                  t=q[f++];

                  for(v=0; v<n; v++)

                  if(a[t][v]==1 && s[v]==0)

                  {

                              q[++r]=v;

                                    printf("The BFS traversal is:\n %d %d", t, v);

                              s[v]=1;

                  }

      }

  }

 

 

void main()

{

      int a[10][10],n,i,j,s;

      double clk;

      clock_t starttime,endtime;

      printf("\n Enter the number of cities\n");

      scanf("%d",&n);

      printf("\nEnter the matrix represention:");

      for(i=0;i<n;i++)

      for(j=0;j<n;j++)

      scanf("%d",&a[i][j]);

      printf("\nEnter the source city");

      scanf("%d",&s);

      starttime=clock();

      bfs(a,n,s);

      endtime=clock();

      clk=((double)(endtime-starttime)/CLOCKS_PER_SEC)*1000;

      printf("\nThe run time is %f ms\n",clk);

 

}

3. BINARY SORT 

PROGRAM

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

int main()

{

int i,n,a[1000],key,bottom,top,mid,j,temp;

double clk;

clock_t starttime,endtime;

printf("Enter the number of Products\n");

scanf("%d",&n);

printf("The Product ID are: \n");

for(i=0;i<n;i++)

{

a[i]=rand()%100;

printf("%d\t",a[i]);

}

for(i=0;i<n-1;i++)

{

for(j=0;j<n-i-1;j++)

{

if(a[j]>a[j+1])

{

temp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

}

}

}

printf("\n Sorted Product ID List is : \n");

for(i=0;i<n;i++)

{

printf("\t%d",a[i]);

}

printf("\nEnter the Product ID to be searched: \n");

scanf("%d",&key);

starttime=clock();

bottom = 1;

top = n;

do

{

mid = (bottom + top) / 2;

if (key < a[mid])

top = mid- 1;

else if (key > a[mid])

bottom = mid + 1;

} while (key != a[mid] && bottom <= top);

if (key == a[mid])

{

printf("Product found!!\n");

printf("\n Product %d found in position: %d\n", key, mid + 1);

}

else

{

printf("\nSearch failed\n %d not found\n", key);

}

endtime=clock();

clk=(double)(endtime-starttime)/CLOCKS_PER_SEC;

printf(" Time taken to search is %f sec\n",clk);

}

4. Insertion Sort

#include<stdio.h>

#include<stdlib.h>

#include<time.h>

void insertion_sort(long a[], int n)

{

    int i,j;

    long v=0;

    for(i=1;i<n;i++)

    {

        v=a[i];

        j=i-1;

        while(j>=0 && a[j]>v)

        {

            a[j+1]=a[j];

            j=j-1;

        }

        a[j+1]=v;

    }

    printf("sorted numbers are:\n");

    for(i=0;i<n;i++)

        printf("%ld\n",a[i]);

}

int main()

{

    clock_t starttime,endtime;

    starttime=clock();

    double clk;

    int i,n;

    long a[10];

    printf("Enter the value of n: ");

    scanf("%d",&n);

    for(i=0;i<n;i++)

        a[i]=9000000000+(rand()%99999999)+1;

    printf("\nphone numbers are:\n");

    for(i=0;i<n;i++)

        printf("%ld\n",a[i]);

    insertion_sort(a,n);

    endtime=clock();

    clk=(double)(endtime-starttime)/CLOCKS_PER_SEC;

    printf("\nTHE RUN TIME IS :%f\n",clk);

}

5.  MERGE SORT

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

 

int a[500000];

 

void merge(int,int,int);

 

void merge_sort(int low,int high)

{

    int mid;

    if(low<high)

    {

        mid=(low+high)/2;

        merge_sort(low,mid);

        merge_sort(mid+1,high);

        merge(low,mid,high);

    }

}

 

void merge(int low,int mid,int high)

{

    int i,j,k;

    int b[500000], c[500000];

 

    // Copy left subarray into b

    for(i=low; i<=mid; i++)

        b[i] = a[i];

 

    // Copy right subarray into c

    for(j=mid+1; j<=high; j++)

        c[j] = a[j];

 

    i = low;        // pointer for b (left)

    j = mid + 1;    // pointer for c (right)

    k = low;        // pointer for a (merged)

 

    // Merge b and c into a

    while(i<=mid && j<=high)

    {

        if(b[i] <= c[j])

        {

            a[k] = b[i];

            i++;

        }

        else

        {

            a[k] = c[j];

            j++;

        }

        k++;

    }

 

    // Copy remaining elements of b

    while(i<=mid)

    {

        a[k] = b[i];

        i++;

        k++;

    }

 

    // Copy remaining elements of c

    while(j<=high)

    {

        a[k] = c[j];

        j++;

        k++;

    }

}

 

int main()

{

    int n,i;

    double clk;

    clock_t starttime,endtime;

 

    printf("MERGE SORT\n");

    printf("Enter the number of employee records:\n");

    scanf("%d",&n);

 

    printf("The Employee IDs are:\n");

    for(i=0;i<n;i++)

    {

        a[i]=rand()%100;

        printf("%d\t",a[i]);

    }

 

    starttime=clock();

    merge_sort(0,n-1);

    endtime=clock();

 

    clk=(double)(endtime-starttime)/CLOCKS_PER_SEC;

 

    printf("\nEmployee IDs in sorted order:\n");

    for(i=0;i<n;i++)

    {

        printf("%d\t",a[i]);

    }

 

    printf("\nThe run time is %f seconds\n",clk);

    return 0;

}

6. QUICK SORT

#include<stdio.h>

#include<time.h>

#include<stdlib.h>

 

int partition(int a[], int low, int high)

{

    int i, j, temp, pivot;

    pivot = a[low];

    i = low + 1;

    j = high;

 

    while(1)

    {

        while(i <= high && a[i] <= pivot)

            i++;

 

        while(a[j] > pivot)

            j--;

 

        if(i < j)

        {

            temp = a[i];

            a[i] = a[j];

            a[j] = temp;

        }

        else

        {

            temp = a[j];

            a[j] = a[low];

            a[low] = temp;

            return j;

        }

    }

}

 

void quick_sort(int a[], int low, int high)

{

    int j;

    if(low < high)

    {

        j = partition(a, low, high);

        quick_sort(a, low, j - 1);

        quick_sort(a, j + 1, high);

    }

}

 

int main()

{

    int i, n, a[200000];

    double clk;

    clock_t starttime, endtime;

 

    printf("Enter the number of student records:\n");

    scanf("%d", &n);

 

    printf("The roll numbers are:\n");

    for(i = 0; i < n; i++)

    {

        a[i] = rand() % 100;

        printf("%d\t", a[i]);

    }

 

    starttime = clock();

    quick_sort(a, 0, n - 1);

    endtime = clock();

 

    clk = (double)(endtime - starttime) / CLOCKS_PER_SEC;

 

    printf("\nSorted roll numbers are:\n");

    for(i = 0; i < n; i++)

        printf("%d\t", a[i]);

 

    printf("\nThe run time is %f seconds\n", clk);

 

    return 0;

}

7. HEAP SORT 

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

 

#define MAX 20000

#define TRUE 1

#define FALSE 0

 

struct candidate

{

    char name[20];

    float percentage;   // Ranking (Average Percentage)

};

 

/* Bottom-Up Heap Construction */

void heapbottomup(struct candidate a[], int n)

{

    int i, j, k, heap;

    struct candidate v;

 

    for (i = n/2; i > 0; i--)

    {

        k = i;

        v = a[k];

        heap = FALSE;

 

        while (!heap && (2*k) <= n)

        {

            j = 2*k;

 

            if (j < n)

                if (a[j].percentage < a[j+1].percentage)

                    j = j + 1;

 

            if (v.percentage >= a[j].percentage)

                heap = TRUE;

            else

            {

                a[k] = a[j];

                k = j;

            }

        }

        a[k] = v;

    }

}

 

/* Heap Sort */

void heapsort(struct candidate a[], int n)

{

    int i;

    struct candidate temp;

 

    heapbottomup(a, n);

 

    for (i = n; i > 1; i--)

    {

        temp = a[1];

        a[1] = a[i];

        a[i] = temp;

 

        heapbottomup(a, i-1);

    }

}

 

int main()

{

    struct candidate a[MAX];

    int n, i;

    clock_t start, end;

    double time_taken;

 

    printf("Enter number of candidates: ");

    scanf("%d", &n);

 

    if (n <= 0 || n > MAX)

    {

        printf("Invalid input\n");

        return 0;

    }

 

    srand(time(NULL));

 

    /* Generate Random Resume Data */

    for (i = 1; i <= n; i++)

    {

        sprintf(a[i].name, "Cand_%d", i);

        a[i].percentage = 50 + (rand() % 500) / 10.0;   // 50.0 to 99.9

    }

 

    /* BEFORE SORTING */

    printf("\n--- BEFORE SORTING ---\n");

    printf("Name\t\tPercentage\n");

    for (i = 1; i <= n; i++)

    {

        printf("%s\t%.2f\n", a[i].name, a[i].percentage);

    }

 

    /* Time Measurement */

    start = clock();

    heapsort(a, n);

    end = clock();

 

    time_taken = (double)(end - start) / CLOCKS_PER_SEC;

 

    /* AFTER SORTING */

    printf("\n--- AFTER SORTING (Ascending Order) ---\n");

    printf("Name\t\tPercentage\n");

    for (i = 1; i <= n; i++)

    {

        printf("%s\t%.2f\n", a[i].name, a[i].percentage);

    }

 

    printf("\nTime taken to sort %d candidates = %f seconds\n", n, time_taken);

 

    return 0;

}