CSE 161 of PAU

Algorithm assignments .......marge sort, quick sort, insertion sort , counting sort, pattern matching.(in c programming language)

Algorithm assignment....

Q. no. 1 : Quick sort in c programming language.

#include<stdio.h>
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}
int partition (int arr[], int low, int high)
{
    int pivot = arr[high];
    int i = (low - 1);
        int j;
    for (j = low; j <= high- 1; j++)
    {

        if (arr[j] <= pivot)
        {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
}
int main()
{
    int arr[] = {7,10,15,6,4};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

Q. no. 3 : coin change problem.

#include<stdio.h>

int count( int S[], int m, int n )

{

    int i, j, x, y;

    int table[n+1][m];

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

        table[0][i] = 1;

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

    {

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

        {

            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

            y = (j >= 1)? table[i][j-1]: 0;

            table[i][j] = x + y;

        }

    }

    return table[n][m-1];

}

int main()

{

    int arr[] = {7,5,1};

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

    int n = 10;

    printf(" %d ", count(arr, m, n));

    return 0;

}

Q. no. 4 : counting sort with c programming language

#include<stdio.h>

void counting_sort(int a[],int n,int max)

{

     int count[50]={0},i,j;

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

      count[a[i]]=count[a[i]]+1;

     printf("\nSorted elements are:");

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

      for(j=1;j<=count[i];++j)

       printf("%d ",i);

}

int main()

{

    int a[50],n,i,max=0;

    printf("Enter number of elements:");

    scanf("%d",&n);

    printf("\nEnter elements:");

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

    {

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

     if(a[i]>max)

      max=a[i];

    }

    counting_sort(a,n,max);

    return 0;

}

Q. no. 5 : Simple pattern matching algorithm 

#include <stdio.h>

#include <string.h>

int match(char [], char []);

int main() {

  char a[100]={"acdefgm"}, b[100]={"def"};

  int position;

  position = match(a, b);

  if(position != -1) {

    printf("Found at location %d\n", position + 1);

  }

  else {

    printf("Not found.\n");

  }

  return 0;

}

int match(char text[], char pattern[]) {

  int c, d, e, text_length, pattern_length, position = -1;

  text_length    = strlen(text);

  pattern_length = strlen(pattern);

  if (pattern_length > text_length) {

    return -1;

  }

  for (c = 0; c <= text_length - pattern_length; c++) {

    position = e = c;

    for (d = 0; d < pattern_length; d++) {

      if (pattern[d] == text[e]) {

        e++;

      }

      else {

        break;

      }

    }

    if (d == pattern_length) {

      return position;

    }

  }

  return -1;

}

Q. no. 6 : Insertion sort 

#include <stdio.h>

int main()

{

  int array[1000] = {4 , 8 , 2 , 5 , 3}, n=5, c, d, t;

  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\n");

  for (c = 0; c <= n - 1; c++) {

    printf("%d\n", array[c]);

  }

  return 0;

}