Skip to main content

Posts

Showing posts with the label Algorithm

Binary Search in C using Recursion

#include<stdio.h> void bins ( int lb , int ub , int item , int a []); void main () { int i , n , item , a [ 20 ]; printf ( "Enter the size of an array: " ); scanf ( "%d" , & n ); printf ( "Enter the elements of the array: " ); for ( i = 0 ; i < n ; i ++ ) { scanf ( "%d" , & a [ i ]); } printf ( "Enter the number to be search: " ); scanf ( "%d" , & item ); bins ( 0 , n - 1 , item , a ); } void bins ( int lb , int ub , int item , int a []) { int mid , flag = 0 ; if ( lb <= ub ) { mid = ( lb + ub ) / 2 ; if ( item == a [ mid ]) { flag = flag + 1 ; } else if ( item < a [ mid ]) { return bins ( lb , mid - 1 , item , a ); } else return bins ( mid + 1 , ub , item , a ); } if (

Solve All-Pairs Shortest Path Problem using Floyd–Warshall Algorithm

Program: #include<stdio.h> #include<conio.h> #define inf 999 void main () { int i , j , k , n , w [ 20 ][ 20 ]; clrscr (); printf ( " \n Enter the no. of vertices : " ); scanf ( "%d" , & n ); printf ( " \n Enter the weights : " ); for ( i = 1 ; i <= n ; i ++ ) for ( j = 1 ; j <= n ; j ++ ) { printf ( "w[%d][%d]= " , i , j ); scanf ( "%d" , & w [ i ][ j ]); if ( i != j && ( w [ i ][ j ] == 0 )) w [ i ][ j ] = inf ; } for ( i = 1 ; i <= n ; i ++ ) { printf ( " \n " ); for ( j = 1 ; j <= n ; j ++ ) printf ( "%d \t " , w [ i ][ j ]); } for ( k = 1 ; k <= n ; k ++ ) { for ( i = 1 ; i <= n ; i ++ ) { for ( j = 1 ; j <= n ; j ++ ) { if ( w [ i ][ k ] + w [ k ][ j ] < w [ i ][ j ]) w [ i ][ j ] = w [ i ][ k ] + w [ k ][ j ]; } } } printf ( " \

Insertion Sort

Write a C program to implement Insertion Sort Algorithm Algorithm:  for (c = 1 to  n - 1)   {     d <= c;     while ( d > 0 AND array[d] < array[d-1])     {       t          <= array[d];       array[d]   <= array[d-1];       array[d-1] <= t;       d <= d-1;     }   } Program: #include <stdio.h> void main() {   int n, array[20], c, d, t;   printf("Enter the number of Elements:");   scanf("%d", &n);   printf("Enter %d integers:\n", n);   for (c = 0; c < n; c++)   {     scanf("%d", &array[c]);   }   for (c = 1 ; c <= n - 1; c++)   {     d = c;     while ( d > 0 && array[d] < array[d-1])     {       t          = array[d];       array[d]   = array[d-1];       array[d-1] = t;       d--;     }   }   printf("Sorted list in ascending order:\n");   for (c = 0; c <= n - 1; c++)   {     printf("%d  ", array[c]);   } } Output: Enter the number of Elements:5 Enter 5 integers: Enter t

Prim's Algorithm

Write a C Program to Implement Prim’s Algorithm and find the Minimum Spanning Tree (MST) for the following Graph. Algorithm: visit[1] <- 1; while( p < n )      {      min=999;      for( i<- 1 to n )         {         for( j <- 1 to n )            {             if(cost[i][j] < min)               {               if( visit[i]!= 0 )                 {                 Min <- cost[i][j];                 a <- u <- i;                 b <- v <- j;                 }               }            }         }       if( visit[u] = 0 OR visit[v] = 0 )         {          Print Edge of MST;          mincost <- mincost+min;          visit[b] <- 1;         }      cost[a][b] <- cost[b][a] <- inf;      }     Print Total Minimum Cost; Program: #include<stdio.h> #include<conio.h> #define inf 999 int cost [ 10 ][ 10 ], visit [ 10 ] = { 0 }; int n , p = 1 , i , u , v , j , min , a , b , mincost ; void main () { clrscr (); printf ( "Ente

C Program to Implement Heap Sort

Algorithm: hs( a[], n)  {   heap(a,n);   for (i = n to 1)    {     temp<-a[1];     a[1]<-a[i];     a[i]<-temp;     downheap(a,1,i-1);    }  } heap(a[],n)  {   index <- n/2;   for(i= index to 1)     downheap(a,i,n);  } downheap(heap[], root, leaf)  {   lc<-2*root;   rc<-lc+1;   if(lc<=leaf)    {     max<-heap[lc];     index<-lc;     if(rc<=leaf)     {      if(heap[rc]>max)      {       max<-heap[rc];       index<-rc;      }     }     if(heap[root] < heap[index])      {       temp <- heap[root];       heap[root] <- heap[index];       heap[index] <- temp;       downheap(heap,index,leaf);      }    } } Program #include<stdio.h> #include<conio.h> void heap ( int * , int ); void downheap ( int * , int , int ); void hs ( int * , int ); void main () { int a [ 20 ], i , n ; clrscr (); printf ( "Enter the number of Elements:" ); scanf ( "%d" , & n ); printf ( "Enter the elements: \n &qu

Write a C Program to find the number of data in a linked list

#include <stdio.h> #define newnode (struct node*)malloc(sizeof(struct node)) typedef struct node { int data ; struct node * next ; } node ; node * create_list (); void main () { node * f ; int len ; f = NULL ; f = create_list (); len = find_len ( f ); printf ( " \n length = %d" , len ); } // main node * create_list () { node * f , * c , * p ; int tdata ; f = NULL ; printf ( " \n Enter data ( use 0 to exit ) : " ); scanf ( "%d" , & tdata ); while ( tdata != 0 ) { c = newnode ; if ( c == NULL ) { printf ( " \n Insuf. mem. " ); exit ( 0 ); } c -> data = tdata ; c -> next = NULL ; if ( f == NULL ) f = c ; else p -> next = c ; p = c ; printf ( " \n Enter data ( use 0 to exit ) : " ); scanf ( "%d" , & tdata ); } //while return ( f ); } // create list int find_len ( node * f ) { int len = 0 ; node * t

Write a C Program to sort a set of number using Selection Sort

Algorithm: ssort(array[],n)       {                   for ( i = 0 to n-1 )               {                position <- i;                for ( j = i + 1 to n )                    {                      if ( array[position] > array[j] )                          position <- j;                    }                if ( position !=  i )                   {                    temp <- array[i];                    array[i] <- array[position];                    array[position] <- temp;                   }                }       } Program: /* Using User Defined Method */  #include <stdio.h> void  printar(int array[], int n)     {     int i;     for ( i = 0 ; i < n ; i++ )       printf("%d ", array[i]);     printf("\n\n");     } void ssort(int array[], int n)       {           int i,j,position,temp;           for ( i = 0 ; i < ( n - 1 ) ; i++ )               {                position = i;                for ( j = i + 1 ; j < n ; j++ )          

Write a C Program for Binary Search

#include<stdio.h> void main() {  int arr[10],i,max,min,mid,val,index;  printf("Please enter 10 values in ascending order:\n");  for(i=0;i<10;i++)   scanf("%d",&arr[i]);  printf("\nEnter a value to be searched: ");  scanf("%d",&val);  max=9;  min=0;  index=-1;  while(min<=max)  {   mid=(max+min)/2;   if(val==arr[mid])   {    index=mid;    break;   }   if(arr[mid]>val)    max=mid-1;   else    min=mid+1;  }  if(index>=0)   printf("Value found in Array at %d location",index+1);  else   printf("Value not found in Array"); }

Write a C Program to Implement Dijkstra's algorithm

Algorithm: dj(int n,int v,int cost[][],int dist[]) {  for( i <- 1 to n )    flag[i]<-0;    dist[i]<-cost[v][i];  count<-2;  while(count<=n)   {    min<-99;    for( w <- 1 to n )     if(dist[w]<min && !a[w])       min <- dist[w];       u<-w;    a[u] <- 1;    count <- count+1;    for( w <- 1 to n )     if((dist[u]+cost[u][w])<dist[w] && !a[w])       dist[w] <- dist[u]+cost[u][w];   } } Program: #include<stdio.h> #include<conio.h> #define inf 999 void dj ( int n , int v , int cost [ 10 ][ 10 ], int dist []) { int i , u , count , w , a [ 10 ], min ; for ( i = 1 ; i <= n ; i ++ ) a [ i ] = 0 , dist [ i ] = cost [ v ][ i ]; count = 2 ; while ( count <= n ) { min = 99 ; for ( w = 1 ; w <= n ; w ++ ) if ( dist [ w ] < min && ! a [ w ]) min = dist [ w ], u = w ; a [ u ] = 1 ; count ++ ; for ( w = 1 ; w <= n ; w ++ ) if (( dist [ u ] + cost [ u ][ w ]) <