2023 students

 

C program for insertion sort

#include <math.h>

#include <stdio.h>

 

/* Function to sort an array

   using insertion sort*/

void insertionSort(int arr[], int n)

{

    int i, key, j;

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

    {

        key = arr[i];

        j = i - 1;

 

        /* Move elements of arr[0..i-1],

           that are greater than key,

           to one position ahead of

           their current position */

        while (j >= 0 && arr[j] > key)

        {

            arr[j + 1] = arr[j];

            j = j - 1;

        }

        arr[j + 1] = key;

    }

}

 

// A utility function to print

// an array of size n

void printArray(int arr[], int n)

{

    int i;

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

        printf("%d ", arr[i]);

    printf("\n");

}

 

// Driver code

int main()

{

    int arr[] = {12, 11, 13, 5, 6};

    int n = sizeof(arr) / sizeof(arr[0]);

 

    insertionSort(arr, n);

    printArray(arr, n);

 

    return 0;

}

Merge Sort

 #include <stdio.h>

#define max 10

int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };

int b[10];

void merging(int low, int mid, int high) {

   int l1, l2, i;

   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {

      if(a[l1] <= a[l2])

         b[i] = a[l1++];

      else

         b[i] = a[l2++];

   }

   

   while(l1 <= mid)    

      b[i++] = a[l1++];

   while(l2 <= high)   

      b[i++] = a[l2++];

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

      a[i] = b[i];

}

void sort(int low, int high) {

   int mid;

   

   if(low < high) {

      mid = (low + high) / 2;

      sort(low, mid);

      sort(mid+1, high);

      merging(low, mid, high);

   } else { 

      return;

   }   

}

int main() { 

   int i;

   printf("List before sorting\n");

   

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

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

   sort(0, max);

   printf("\nList after sorting\n");

   

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

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

}

NON RECURSIVE MERGE SORT

 #include <stdio.h>

#define MAX 30

int main()

{

int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;

printf("Enter the number of elements : ");

scanf("%d",&n);

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

{

printf("Enter element %d : ",i+1);

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

}

printf("Unsorted list is : ");

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

printf("%d ", arr[i]);

/*l1 lower bound of first pair and so on*/

for(size=1; size < n; size=size*2 )

{

l1=0;

k=0;  /*Index for temp array*/

while( l1+size < n)

{

h1=l1+size-1;

l2=h1+1;

h2=l2+size-1;

/* h2 exceeds the limlt of arr */

if( h2>=n ) 

h2=n-1;

/*Merge the two pairs with lower limits l1 and l2*/

i=l1;

j=l2;

while(i<=h1 && j<=h2 )

{

if( arr[i] <= arr[j] )

temp[k++]=arr[i++];

else

temp[k++]=arr[j++];

}

while(i<=h1)

temp[k++]=arr[i++];

while(j<=h2)

temp[k++]=arr[j++];

/**Merging completed**/

/*Take the next two pairs for merging */

l1=h2+1; 

}/*End of while*/

/*any pair left */

for(i=l1; k<n; i++) 

temp[k++]=arr[i];

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

arr[i]=temp[i];

printf("\nSize=%d \nElements are : ",size);

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

printf("%d ", arr[i]);

}/*End of for loop */

printf("Sorted list is :\n");

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

printf("%d ", arr[i]);

printf("\n");

return 0;

}/*End of main()*/

Heap Sort

 // C++ program for implementation of Heap Sort

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

int largest = i; // Initialize largest as root Since we are using 0 based indexing

int l = 2 * i + 1; // left = 2*i + 1

int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])

largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])

largest = r;

// If largest is not root

if (largest != i) {

swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);

}

}

// main function to do heap sort

void heapSort(int arr[], int n)

{

// Build heap (rearrange array)

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

heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--) {

// Move current root to end

swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);

}

}

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

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

cout << arr[i] << " ";

cout << "\n";

}

// Driver program

int main()

{

int arr[] = { 60 ,20 ,40 ,70, 30, 10};

int n = sizeof(arr) / sizeof(arr[0]);

//heapify algorithm

// the loop must go reverse you will get after analyzing manually

// (i=n/2 -1) because other nodes/ ele's are leaf nodes

// (i=n/2 -1) for 0 based indexing

// (i=n/2) for 1 based indexing

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

heapify(arr,n,i);

}

cout << "After heapifying array is \n";

printArray(arr, n);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);

return 0;

}

//code by Prajwal Chougale

Randomized Quick sort

 #include<iostream>

#include<cstdlib>

using namespace std;

void swap(int *a, int *b) {

   int temp;

   temp = *a;

   *a = *b;

   *b = temp;

}

int Partition(int a[], int l, int h) {

   int pivot, index, i;

   index = l;

   pivot = h;

   for(i = l; i < h; i++) {

      if(a[i] < a[pivot]) {

         swap(&a[i], &a[index]);

         index++;

      }

   }

   swap(&a[pivot], &a[index]);

   return index;

}

int RandomPivotPartition(int a[], int l, int h) {

   int pvt, n, temp;

   n = rand();

   pvt = l + n%(h-l+1);

   swap(&a[h], &a[pvt]);

   return Partition(a, l, h);

}

int QuickSort(int a[], int l, int h) {

   int pindex;

   if(l < h) {

      pindex = RandomPivotPartition(a, l, h);

      QuickSort(a, l, pindex-1);

      QuickSort(a, pindex+1, h);

   }

   return 0;

}

int main() {

   int n, i;

   cout<<"\nEnter the number of data element to be sorted: ";

   cin>>n;

   int arr[n];

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

      cout<<"Enter element "<<i+1<<": ";

      cin>>arr[i];

   }

   QuickSort(arr, 0, n-1);

   cout<<"\nSorted Data ";

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

      cout<<"->"<<arr[i];

   return 0;

}

RADIX SORT

#include<stdio.h>

int get_max (int a[], int n){

   int max = a[0];

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

      if (a[i] > max)

         max = a[i];

   return max;

}

void radix_sort (int a[], int n){

   int bucket[10][10], bucket_cnt[10];

   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;

   lar = get_max (a, n);

   while (lar > 0){

      NOP++;

      lar /= 10;

   }

   for (pass = 0; pass < NOP; pass++){

      for (i = 0; i < 10; i++){

         bucket_cnt[i] = 0;

      }

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

         r = (a[i] / divisor) % 10;

         bucket[r][bucket_cnt[r]] = a[i];

         bucket_cnt[r] += 1;

      }

      i = 0;

      for (k = 0; k < 10; k++){

         for (j = 0; j < bucket_cnt[k]; j++){

            a[i] = bucket[k][j];

            i++;

         }

      }

      divisor *= 10;

      printf ("After pass %d : ", pass + 1);

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

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

     // printf ("");

   }

}

int main (){

   int i, n, a[10];

   printf ("Enter the number of items to be sorted: ");

   scanf ("%d", &n);

   printf ("Enter items: ");

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

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

   }

   radix_sort (a, n);

   printf ("Sorted items : ");

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

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

  // printf ("");

   return 0;

}

DYNAMIC LCS

 #include<iostream>

using namespace std;

int lcs(string pattern_1, string pattern_2) {

  int m = pattern_1.size();

  int n = pattern_2.size();

  // dp will store solutions as the iteration goes on

  int dp[n + 1][m + 1];

  for (int i = 0; i < n + 1; i++) {

    for (int j = 0; j < m + 1; j++) {

      if (i == 0 || j == 0) {

        dp[i][j] = 0;

      } else if (pattern_2[i - 1] == pattern_1[j - 1]) {

        dp[i][j] = dp[i - 1][j - 1] + 1;

      } else {

        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

      }

    }

  }

  return dp[n][m];

}

int main() {

  string pattern_1 = "RGBGARGA";

  string pattern_2 = "BGRARG";

  cout<<"Length of LCS: "<<lcs(pattern_1, pattern_2)<<endl;

}

DFS IN C++

 #include<iostream>

using namespace std;

#include<conio.h>

#include<stdlib.h>

int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

int main()

{

    int m;

    cout <<"Enter no of vertices:";

    cin >> n;

    cout <<"Enter no of edges:";

    cin >> m;

    cout <<"\nEDGES \n";

    for(k=1; k<=m; k++)

    {

        cin >>i>>j;

        cost[i][j]=1;

    }

    cout <<"Enter initial vertex to traverse from:";

    cin >>v;

    cout <<"DFS ORDER OF VISITED VERTICES:";

    cout << v <<" ";

    visited[v]=1;

    k=1;

    while(k<n)

    {

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

            if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)

            {

                visit[j]=1;

                stk[top]=j;

                top++;

            }

        v=stk[--top];

        cout<<v << " ";

        k++;

        visit[v]=0;

        visited[v]=1;

    }

    return 0;

}

BFS IN C

 #include <stdio.h>

 

int n, i, j, visited[10], queue[10], front = -1, rear = -1;

int adj[10][10];

 

void bfs(int v)

{

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

        if (adj[v][i] && !visited[i])

            queue[++rear] = i;

    if (front <= rear)

    {

        visited[queue[front]] = 1;

        bfs(queue[front++]);

    }

}

 

void main()

{

    int v;

    printf("Enter the number of vertices: ");

    scanf("%d", &n);

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

    {

        queue[i] = 0;

        visited[i] = 0;

    }

    printf("Enter graph data in matrix form:    \n");

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

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

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

    printf("Enter the starting vertex: ");

    scanf("%d", &v);

    bfs(v);

    printf("The node which are reachable are:    \n");

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

        if (visited[i])

            printf("%d\t", i);

        else

            printf("BFS is not possible. Not all nodes are reachable");

    

}