N-Queen Problem

   Implement N Queen’s problem using Back Tracking


#include<stdio.h>
#include<stdlib.h>
int place(int);

int X[10];

void main()
{
   int i,j,n,k,count=0;
   printf("\n\n*************N-QUEEN PROBLEM***************\n\n");
   printf("Enter the number of elements:");
   scanf("%d",&n);
   if(n==0||n==2||n==3)
    {
        printf("\n\n No solution\n");
        printf("\n\n********** ************ **********\n\n");
        exit(0);
    }
   k=1;
   X[k]=0;
   while(k)
   {
       X[k]=X[k]+1;
       while(X[k]<=n&&!place(k))
             X[k]=X[k]+1;
       if(X[k]<=n)
         {
             if(k==n)
              {
                 printf("\nSolution %d\n\n",++count);
                 for(i=1;i<=n;i++)
                    {
                       for(j=1;j<X[i];j++)
                            printf("*\t");
                       printf("Q\t");
                       for(j=X[i]+1;j<=n;j++)
                              printf("*\t");
                            printf("\n");
                    }
              }
              else
              {
                   k=k+1;
                   X[k]=0;
              }
         }
         else
                 k=k-1;
     }
     printf("\n\n******** ********* *********\n\n");
} 
int place(int p)
{
    int i;
    for(i=1;i<=p-1;i++)
     {
       if(X[i]==X[p]||abs(i-p)==abs(X[i]-X[p]))
         return 0;
     }
     return 1;
}







OUTPUT:

Enter the number of elements:4

Solution 1
*    Q    *    *
*    *    *    Q
Q    *    *    *
*    *    Q    *

Solution 2
*    *    Q    *
Q    *    *    *
*    *    *    Q
*    Q    *    *

******* ******** ***********

Read More

Floyd's Parallelized Algorithm

11. Implement All-Pairs Shortest Paths Problem using Floyd’s algorithm. Parallelize this algorithm, implement it using OpenMP and determine the speed-up achieved.

#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<time.h>
void floyd();
int min(int,int);
int i,j,n,k,a[8][8];
clock_t start,end;
void main()
{
  printf("\n\n*********FLOYD'S PARALLELIZED ALGORITHM*********\n\n");
  printf("Enter the number of vertices:");
  scanf("%d",&n);
  printf("\n\nEnter the adjacency matrix\n");
  for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
          scanf("%d",&a[i][j]);
  printf("\n\nEntered adjacency matrix is:\n");
  for(i=1;i<=n;i++)
  {
      for(j=1;j<=n;j++)
      {
          printf("%d\t",a[i][j]);
      }
      printf("\n");
  }
  start=clock();
  floyd(a,n);
  end=clock();
  printf("\nAll pair shortest path matrix:\n");
  for(i=1;i<=n;i++)
  {
    for(j=1;j<=n;j++)
          printf("%2d",a[i][j]);
    printf("\n");
  }
  printf("\n\nTime taken to execute is %f\n",(double)(end-start)/CLOCKS_PER_SEC);
  printf("\n*****************************************************************");
}
void floyd()
{
 //omp_set_num_threads(4);
  #pragma omp parallel for private(i,j,k)
      for(k=1;k<=n;k++)
       {
        for(i=1;i<=n;i++)
          for(j=1;j<=n;j++)
               a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
       }
 }
 int min(int a, int b)
{
  if(a>b)
       return b;
   else
       return a;
}



OUTPUT:
Enter the number of vertices:4

Enter the adjacency matrix
0  1  8  5  1  0  2  999  8  2  0  3  5  999  3  0

Entered adjacency matrix is:
0      1        8      5
1      0        2      999
8      2        0      3
5      999    3     0

All pair shortest path matrix :
0    1    3    5
1    0    2    5
3    2    0    3
5    5    3    0

Time taken to execute is 0.000104

*********** ************ **************

Read More

Prims Algorithm

10. Find Minimum Cost Spanning Tree of a given undirected graph using Prim’s algorithm.

#include<stdio.h>

void prims();

int nearV[10],cost[10][10],t[10][2],i,j,n,k,min,u,mincost=0;

void main()
{
  printf("\n\n**********PRIMS ALGORITHM***********\n\n");
  printf("Enter the number of nodes\n");
  scanf("%d",&n);
  printf("\n\nEnter the cost matrix\n");
  for(i=1;i<=n;i++)
    {
       for(j=1;j<=n;j++)
         {
             scanf("%d",&cost[i][j]);
         }
    }
  printf("\n\n The entered cost matrix is\n");
  for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
          {
            printf("%d\t",cost[i][j]);
          }
          printf("\n");
    }
printf("\n\nMinimum spanning tree edges and their cost are\n");
prims();
printf("\n\nThe minimum spanning tree cost is %d",mincost);
printf("\n\n********* *********** ***********");
}

void prims()
{
  for(i=2;i<=n;i++)
        nearV[i]=1;
  nearV[1]=0;
  for(i=1;i<n;i++)
   {
     min=999;
     for(j=1;j<=n;j++)
      {
          if(nearV[j]!=0&&cost[j][nearV[j]]<min)
           {
             min=cost[j][nearV[j]];
             u=j;
       }
      }
      t[i][1]=u;
      t[i][2]=nearV[u];
      mincost+=min;
      nearV[u]=0;
      for(k=1;k<=n;k++)
       {
         if(nearV[k]!=0&&cost[k][nearV[k]]>cost[k][u])
             nearV[k]=u;
       }
       printf("%d)edge(%d,%d),cost%d\n",i,t[i][1],t[i][2],min);
   }
}


OUTPUT:

Enter the number of nodes
3

Enter the cost matrix
0  2  3  2  0  1  3  1  0

Read More

TSP Dynamic Programming

9. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.

#include<stdio.h>
#include<stdlib.h>

int tspdp(int c[10][10], int tour[10], int start, int n);

void main()
{
  int i,j,n,cost,c[10][10], tour[10];
  printf("\n\n*************TSP DYNAMIC PROGRAMMING************\n\n");
  printf("\n\n Enter the number of cities:");
  scanf("%d",&n);
  if(n==1)
  {
        printf("\n Path is not possible\n\n");
        exit(0);
  }
  printf("\n\n Enter the cost matrix\n");
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
        scanf("%d",&c[i][j]);
  printf("\n\n The entered cost matrix is\n");
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
      printf("%d\t",c[i][j]);
    }
    printf("\n");
  }
  for(i=1;i<=n;i++)
       tour[i]=i;
  cost=tspdp(c,tour,1,n);
  printf("\n\n The accurate path is \n");
  for(i=1;i<=n;i++)
      printf("%d->",tour[i]);
  printf("1");
  printf("\n\nThe accurate mincost is %d",cost);
  printf("\n\n************ **************** ********** ");
}

int tspdp(int c[10][10], int tour[10], int start, int n)
 {
   int mintour[10],temp[10],mincost=999,ccost,i,j,k;
   if(start==n-1)
    {
      return(c[tour[n-1]][tour[n]]+c[tour[n]][1]);
    }
   for(i=start+1;i<=n;i++)
    {
      for(j=1;j<=n;j++)
               temp[j]=tour[j];
      temp[start+1]=tour[i];
      temp[i]=tour[start+1];
      if((c[tour[start]][tour[i]]+(ccost=tspdp(c,temp,start+1,n)))<mincost)
       {
          mincost=c[tour[start]][tour[i]]+ccost;
          for(k=1;k<=n;k++)
             mintour[k]=temp[k];
       }
 }
for(i=1;i<=n;i++)
   tour[i]=mintour[i];
return mincost;
}



OUTPUT:

Enter the number of cities:4

Enter the cost matrix
0  1  3  6  1  0  2  3  3  2  0  1  6  3  1  0
    

Read More

TSP Approximation Algorithm

9. Implement any scheme to find the optimal solution for the Traveling Salesperson problem and then solve the same problem instance using any approximation algorithm and determine the error in the approximation.

#include<stdio.h>

void tspapp(int v);

int visited[10],city,cost[10][10],count,mincost,i,j;

void main()
{
  printf("\n\n******TSP APPROXIMATION PROBLEM**\n\n");
  printf("Enter the number of cities:");
  scanf("%d",&city);
  printf("\n\nEnter the cost matrix\n\n");
  for(i=1;i<=city;i++)
   {
      for(j=1;j<=city;j++)
       {
          scanf("%d",&cost[i][j]);
       }
   }
  printf("\n\n The entered cost matrix is \n");
  for(i=1;i<=city;i++)
   {
      for(j=1;j<=city;j++)
       {
          printf("%d\t",cost[i][j]);
       }
       printf("\n");
   }
  printf("\n\n The approximate path is \n");
  tspapp(1);
  printf("\n\n************* **************** ************\n");
}

void tspapp(int v)
{
  int k,min;
  visited[v]=1;
  printf("%d->",v);
  if(count==city-1)
   {
     mincost=mincost+cost[v][1];
     printf("1");
     printf("\n\nApproximate Mincost is %d",mincost);
     return;
   }
  min=999;
  for(j=1;j<=city;j++)
   {
     if(cost[v][j]<min&&cost[v][j]!=0&&!visited[j])
      {
         min=cost[v][j];
         k=j;
      }
   }
  mincost=mincost+cost[v][k];
  count++;
  tspapp(k);
}



OUTPUT:

Enter the number of cities:4

Enter the cost matrix
0  1  3  6  1  0  2  3  3  2  0  1  6  3  1  0

Read More

Subset Problem

8. Find a subset of a given set S = {s1,s2,…..,sn} of n positive integers whose sum is equal to a given positive integer d. For example, if S= {1, 2, 5, 6, 8} and d = 9 there are two solutions {1,2,6} and {1,8}.A suitable message is to be displayed if the given problem instance doesn’t have a solution.

#include<stdio.h>
#include<stdlib.h>

void subset(int, int, int);

int w[10],n,d,i,cs,r,x[10],sum=0,k,c;

void main()
{
  printf("\n\n************SUBSET PROBLEM*********\n\n");
  printf("Enter the number of elements:");
  scanf("%d",&n);
  printf("\n\n Enter the elements in increasing order:");
  for(i=0;i<n;i++)
      scanf("%d",&w[i]);
  printf("\n\nEnter the value of d:");
  scanf("%d",&d);
  for(i=0;i<n;i++)
        sum=sum+w[i];
  printf("\n\nSUM=%d",sum);
  if(sum<d||w[0]>d)
  {
     printf("\n\n Subset is not posssible!");
     printf("\n\n*************** *********** **************\n\n");
     exit(0);
  }
  subset(0,0,sum);
  if(c==0)
      printf("\n\nSubset is not possible !");
  printf("\n\n********* ************ ************\n\n");
}
void subset(int cs, int k, int r)
 {
      x[k]=1;
      if(cs+w[k]==d)
       {
         printf("\n\n Solutiion %d is={",++c);
         for(i=0;i<=k;i++)
                if(x[i]==1)
                 {
                     printf("%d",w[i]);
                 }
                 printf("\b}");
       }
       else if((cs+w[k]+w[k+1])<=d)
              subset(cs+w[k],k+1,r-w[k]);
       if((cs+r-w[k])>=d&&(cs+w[k+1])<=d)
        {
           x[k]=0;
           subset(cs,k+1,r-w[k]);
        }
 }



OUTPUT:

Enter the number of elements:5

Enter the elements in increasing order:  1  2  3  6  8

Enter the value of d:9

Read More

DFS

7. Check whether a given graph is connected or not using DFS method.

#include<stdio.h>
void dfs(int);
int visited[10],adj[10][10],n,count;
void main()
{
 int i,j;
 printf("\n\n********DFS METHOD***********\n\n");
 printf("Enter the mumber of nodes:");
 scanf("%d",&n);
 printf("\n\nEnter the adjacency matrix\n");
 for(i=1;i<=n;i++)
  {
      for(j=1;j<=n;j++)
        {
         printf("%d\t",adj[i][j]);
        }
      printf("\n");
  }
 for(i=1;i<=n;i++)
  {
    count=0;
    for(j=1;j<=n;j++)
            visited[j]=0;
    dfs(i);
    if(count==n)
     {
       printf("\nGraph is connected");
       printf("\n\n******************");
       getch();
       exit(0);
     }
  }
 printf("\nGraph is not connected");
 printf("\n\n****************");
}
void dfs(int i)
{
  int w;
  count++;
  visited[i]=1;
  for(w=1;w<=n;w++)
   {
     if(adj[i][w]==1 && visited[w]==0)
           dfs(w);
   }
}



OUTPUT:

Enter the number of nodes:4

Enter the adjacency matrix
0  1  1  0  0  0  1  0  0  0  0  1  0  0  0  0




Enter the number of nodes:4

Enter the adjacency matrix
0  1  1  0  0  0  1  0  0  0  0  0  0  0  0  0

Read More

Kruskal's Agorithm

6. Find Minimum Cost Spanning Tree of a given undirected graph using Kruskal’s algorithm.

#include<stdio.h>

void kruskals();
int parent[10],cost[10][10],ne,i,j,n,min,a,b,u,v,mincost=0;

void main()
{
  printf("\n\n*********KRUSKALS ALGORITH*********\n\n");
  printf("Enter the number of nodes:");
  scanf("%d",&n);
  printf("\n\nEnter the cost matrix\n");
  for(i=1;i<=n;i++)
   {
     for(j=1;j<=n;j++)
      {
        scanf("%d",&cost[i][j]);
      }
   }
  printf("\n\nThe entered cost matrix is\n");
  for(i=1;i<=n;i++)
   {
     for(j=1;j<=n;j++)
      {
         printf("%d\t",cost[i][j]);
      }
      printf("\n");
   }
   kruskals();
   printf("\n\nThe minimum spanning tree cost is %d",mincost);
   printf("\n\n************ ************** *************");
}

void kruskals()
{
  ne=1;
  while(ne<n)
  {
    for(i=1,min=999;i<=n;i++)
      {
       for(j=1;j<=n;j++)
        {
          if(cost[i][j]<min)
           {
             min=cost[i][j];
             a=u=i;
             b=v=j;
           }
        }
      }
  while(parent[u])
      u=parent[u];
  while(parent[v])
      v=parent[v];
  if(u!=v)
   {
     printf("%d> minimum edge from %d to %d is %d\n\n",ne++,a,b,min);
     mincost+=min;
     parent[v]=u;
   }
   cost[a][b]=cost[b][a]=999;
  }
}



OUTPUT:

Enter the number of nodes:5

Enter the cost matrix
0  1  2  999  6  1  0  3  999  999  2  3  0   4  999  999  999  4  0  5  6  999  999  5  0

Read More

Dijkstra's Algorithm

5. From a given vertex in a weighted connected graph, find shortest paths to other vertices using Dijkstra’s algorithm.

#include<stdio.h>
void dij();
void printpath();

int sv,i,j,n,w,v=0,t,min,count,dist[10],visited[10],cost[10][10],path[10];
void main()
{
 printf("\n\n********DIJKSTRA'S ALGORITHM***********\n\n");
 printf("Enter the number of nodes:");
 scanf("%d",&n);
 printf("\n\nEnter the cost matrix\n");
 for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
         scanf("%d",&cost[i][j]);
 printf("\n\n The entered cost matrix is \n");
 for(i=1;i<=n;i++)
 {
     for(j=1;j<=n;j++)
      {
        printf("%d\t",cost[i][j]);
      }
      printf("\n");
 }
 printf("\n\nEnter the source vertex:");
 scanf("%d",&sv);
 dij();
 printpath();
 printf("\n\n**************************");
}

void dij()
 {
     count=2;
     for(i=1;i<=n;i++)
      {
         visited[i]=0;
         dist[i]=cost[sv][i];
         if(cost[sv][i]==999)
                 path[i]=0;
         else
                 path[i]=sv;
      }
     visited[sv]=1;
     while(count<=n)
      {
         min=999;
         for(w=1;w<=n;w++)
         if(dist[w]<min&&!visited[w])
          {
              min=dist[w];
               v=w;
          }
         visited[v]=1;
         count++;
         for(w=1;w<=n;w++)
           {
              if(dist[w]>dist[v]+cost[v][w])
               {
                  dist[w]=dist[v]+cost[v][w];
                  path[w]=v;
               }
           }
       }
 }
void printpath()
 {
    for(w=1;w<=n;w++)
     {
         if(visited[w]==1 && w!=sv)
          {
            printf("\n\nThe shortest distance between %d->%d=%d",sv,w,dist[w]);
            t=path[w];
            printf("\nThe path is:\n");
            printf("%d",w);
            while(t!=sv)
             {
               printf("<-->%d",t);
               t=path[t];
             }
            printf("<-->%d",sv);
          }
      }
 }



OUTPUT:

Enter the number of nodes:4

Enter the cost matrix
0  1  4  999  1  0  2  8  4  2  0  3  999  8  3  0

Read More

Knapsack Problem

4. Implement 0/1 Knapsack problem using Dynamic Programming.

#include<stdio.h>
#include<stdlib.h>

void displayinfo();
void knapsack();
void optimal();

int i,j,x[10],n,m,v[10][10],w[10],p[10],item=0;
void main()
{
 printf("\n\n********KNAPSACK PROBLEM *************\n\n");
 printf("\n\n Enter the total number of items:\n");
 scanf("%d",&n);
 printf("\n\n Enter the weight of each item:\n\n");
 for(i=1;i<=n;i++)
       scanf("%d",&w[i]);
 printf("\n\n Enter the profit of each ittem:\n\n");
 for(i=1;i<=n;i++)
       scanf("%d",&p[i]);
 printf("\n\nEnter the knapsack capacity:\n\n");
 scanf("%d",&m);
 displayinfo();
 knapsack();
 printf("\n\n The content of the knapsack table are \n");
 for(i=0;i<=n;i++)
   {
     for(j=0;j<=m;j++)
       {
          printf("%d\t",v[i][j]);
       }
     printf("\n");
   }
 optimal();
}
void displayinfo()
 {
  printf("\n\nEnterd information about knapsack problem are\n");
  printf("\nITEM\tWEIGHT\tPROFIT\n");
  for(i=1;i<=n;i++)
      printf("%d\t%d\t%d\n",i,w[i],p[i]);
  printf("capacity=%d\n\n",m);
 }
void knapsack()
 {
  for(i=0;i<=n;i++)
   {
    for(j=0;j<=m;j++)
     {
      if(i==0||j==0) 
              v[i][j]=0;
      else if(j<w[i])  
              v[i][j]=v[i-1][j];
      else   
              v[i][j]=max(v[i-1][j],(v[i-1][j-w[i]]+p[i]));
     }
   }
 }
void optimal()
 {
  int i=n,j=m;
  while(i!=0&&j!=0)
   {
    if(v[i][j]!=v[i-1][j])
         {
           x[i]=1;
           j=j-w[i];
         }
     i=i-1;
   }
   printf("\n\n Optimal solution is %d\n\n",v[n][m]);
   printf("selected items are:");
   for(i=1;i<=n;i++)
   if(x[i]==1)
    {
     printf("%d,",i);
     item=1;
    }
   printf("\b\b");
   if(item==0)
   printf("NIL\n\t sorry!No item can be placed in knapsack\n");
   printf("\n***************************************\n");
 }
int max(int a,int b)
 {
   if(a>b)
     return a;
   else
     return b;
 }



OUTPUT:

Enter the total number of items: 4
Enter the weight of each item: 2  3  1  2
Enter the profit of each item:12  10  15  20
Enter the knapsack capacity:5



Enter the total number of items: 2
Enter the weight of each item: 10  20
Enter the profit of each item:30  25
Enter the knapsack capacity:5  

Read More

Warshall Program

3. Compute the transitive closure of a given directed graph using Warshall’s algorithm.

#include<stdio.h>
void warshall(int a[10][10],int n);

void main()
{
 int a[10][10],i,j,n;
 printf("\n*********WARSHALL PROGRAM*******\n\n");
 printf("\n Enter the number of nodes in a graph\n");
 scanf("%d",&n);
 printf("\n\n Enter the adjacency matrix of directed graph\n");
 for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
 scanf("%d",&a[i][j]);
 printf("\n Entered adjacency matrix of ordered graph\n");
 for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
     printf("%d\t",a[i][j]);
    }
   printf("\n");
  }
 warshall(a,n);
 printf("\n\nTransitive closure matrix is \n");
 for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
     printf("%d\t",a[i][j]);
    }
   printf("\n");
  }
  printf("\n\n*********************************\n\n");
 }
 void warshall(int a[10][10],int n)
  {
   int i,j,k;
   for(k=1;k<=n;k++)
   {
    for(i=1;i<=n;i++)
     {
      for(j=1;j<=n;j++)
       {
      a[i][j]=a[i][j]||(a[i][k]&&a[k][j]);
       }
     }
   }
 }



OUTPUT:

Enter the number of nodes in a graph
3

Enter the adjacency matrix of directed graph
0  1  0  0  0  1  1  0  0

Read More

Topological Sorting

3. Obtain the Topological ordering of vertices in a given digraph.

#include<stdio.h>
void topo();
int ad[10][10],i,j,n,k;
void main()
{
 printf("\n\n********TOPOLOGICAL SORTING *********\n\n");
 printf("\n Enter the number of vertices\n");
 scanf("%d",&n);
 printf("\n Enter the adjecency matrix\n");
 for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
     scanf("%d",&ad[i][j]);
    }
  }
 printf("\n The entered adjecency matrix is \n");
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
    {
     printf("%d\t",ad[i][j]);
    }
   printf("\n");
  }
 topo();
}
void topo()
{
 int v[10],in=1,count=0,f=1,flag=0;
  while(f)
  {
   count++;
   for(i=1;i<=n;i++)
    {
     flag=0;
      for(j=1;j<=n;j++)
        {
         if(ad[j][i]!=0||v[j]==i)
          {
         flag=1;break;
          }
        }
    if(flag!=1)
      {
       v[in++]=i;for(k=1;k<=n;k++)
       ad[i][k]=0;
      }
   }
  if(count==n)f=0;
  }
  if(in<n)
  printf("\n\n Topological ordering is not possible\n");
  else
   {
    printf("\n\n Topological ordering is possible\n");
    printf("\n Ordering is:\n");
    for(i=1;i<=n;i++)
    printf("%d\t",v[i]);
   }
  printf("\n********\n");
}



OUTPUT:
Enter the number of vertices
5

Enter the adjacency matrix
0  1  0  0  0  0  0  0  0  0  1  1  0  0  0  0  0  1  0  0  0  0  1  0  0


Enter the number of vertices
3

Enter the adjacency matrix
0  0  1  1  0  0   0  1  0

Read More

Mergesort Parallel Program

2. Using OpenMP, implement a parallelized Merge Sort algorithm to sort a given set of elements and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<time.h>
void mergesort(int,int);
void merge(int,int,int);
int a[100000];
void main()
{
 int n,i;
 clock_t start,end;
 printf("\n\n....MERGESORT PARALLEL PROGRAM....\n\n");
 printf("\n\nEnter the element to be sorted\n\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
   a[i]=rand()%100;
 printf("\n Array element to be sorted \n");
 for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 start=clock();
 mergesort(0,n-1);
 end=clock();
 printf("\n\n The sorted elements are\n");
 for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 printf("\n\n The time taken is %f\n",(double)(end-start)/CLOCKS_PER_SEC);
 printf("\n\n****...........*******\n\n");
}
void mergesort(int low,int high)
{
 int mid;
 if(low<high)
  {
   mid=(low+high)/2;
   #pragma omp parallel section
    {
     #pragma omp section
     mergesort(low,mid);
     #pragma omp section
     mergesort(mid+1,high);
    }
   merge(low,mid,high);
  }
}
void merge(int low,int mid,int high)
 {
  int i,j,h,k,b[100000];
  h=low;
  i=low;
  j=mid+1;
  while((h<=mid)&&(j<=high))
   {
    if(a[h]<a[j])
     {
      b[i]=a[h];
      h=h+1;
     }
    else
     {
      b[i]=a[j];
      j=j+1;
     }
    i=i+1;
   }
 if(h>mid)
  {
   for(k=j;k<=high;k++)
     {
  b[i]=a[j];
  i=i+1;
     }
  }
else
 {
  for(k=h;k<=mid;k++)
  {
   b[i]=a[k];
   i=i+1;
  }
 }
 for(k=low;k<=high;k++)
   a[k]=b[k];
}



OUTPUT:

Enter the number of elements to be sorted
6

Array elements to be sorted are
83  86  77  15  93  35

Read More

Quick Sort Program

1. Sort a given set of elements using the Quicksort method and determine the time required to sort the elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted and plot a graph of the time taken versus n. The elements can be read from a file or can be generated using the random number generator.

 #include<stdio.h>
#include<time.h>

void quicksort(int,int);
int partition(int,int);
void interchange(int,int);

int a[10000000];

void main()
{
 int i,n;
 clock_t start,end;
 printf("\n\n********QUICK SORT PROGRAM*****\n\n");
 printf("Enter the number of elements to be sorted \n");
 scanf("%d",&n);
 for(i=0;i<n;i++) a[i]=rand()%100;
 printf("\n Array elements to be sorted are\n");
 for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 a[n]=999;
 start=clock();
 quicksort(0,n-1);
 end=clock();
 printf("\n\n The sorted elements are\n");for(i=0;i<n;i++)
 printf("%d\t",a[i]);
 printf("\n\n The time taken is %f \n",(double)(end-start)/CLOCKS_PER_SEC);
 printf("\n*********\n\n");
}
 void quicksort(int p,int q)
 {
  int j;
  if(p<q)
   {
    j=partition(p,q);
    quicksort(p,j-1);
    quicksort(j+1,q);
   }
 }
int partition(int p,int q)
{
 int v,i,j;
 v=a[p];
 i=p;
 j=q;
 while(i<=j)
 {
  while(a[i]<=v)i++;
  while(a[j]>v)j--;
  if(i<j)
  interchange(i,j);
 }
 a[p]=a[j];
 a[j]=v;
 return j;
}
void interchange(int i,int j)
{
 int p;
 p=a[i];
 a[i]=a[j];
 a[j]=p;
}



OUTPUT:

Enter the number of elements to be sorted
6

Array elements to be sorted are
83  86  77  15  93  35

Read More