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. 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;
}
No comments:
Post a Comment