Chirayu Baliyan

Program-1 2000301540017
Pg = 1

1. Write a program in C language for Linear

Search and Recursive Binary Search.

1.1) Linear Search

#include<stdio.h>

int main()
{

int a[20],i,x,n;

printf("How many elements?");

scanf("%d",&n);

printf("Enter array elements:n");

for(i=0;i<n;++i)
scanf("%d",&a[i]);

printf("nEnter element to search:");

scanf("%d",&x);

for(i=0;i<n;++i)
if(a[i]==x)
break;

if(i<n)
printf("Element found at index %d",i);
else
printf("Element not found");
return 0;
}
 Chirayu Baliyan
1.2) Recursive Binary Search 2000301540017
Pg = 2
#include <stdio.h>

int binarySearch(int arr[], int lo, int hi, int item)

{
int mid;
if (lo > hi)
return -1;
mid = (lo + hi) / 2;
If (arr[mid] == item)
return mid;
else if (arr[mid] > item)
binarySearch(arr, lo, mid - 1, item);
else if (arr[mid] < item)
binarySearch(arr, mid + 1, hi, item);
}
int main()
{
int arr[] = { 10, 21, 17, 45, 88 };
int index = 0;
int item = 0;
printf("Enter item to search: ");
scanf("%d", &item);
index = binarySearch(arr, 0, 5, item);
if (index == -1)
printf("Item not found in array\n");
else
printf("Item found at index %d\n", index);
return 0;
}
 Program-2 Chirayu Baliyan
2000301540017
2. Write a program in C language for Pg = 3
performing Heap Sort.
#include <stdio.h>
void heapify(int a[], int n, int i)
{
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left child
int right = 2 * i + 2; // right child
if (left < n && a[left] > a[largest])
largest = left;
if (right < n && a[right] > a[largest])
largest = right;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, n, largest);
}
}
void heapSort(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
for (int i = n - 1; i >= 0; i--) {
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
}
}
void printArr(int arr[], int n)
{
for (int i = 0; i < n; ++i)
printf("%d", arr[i]);
}
int main()
{
int a[] = {48, 10, 23, 43, 28, 26, 1};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
heapSort(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
 Chirayu Baliyan
Program-3 2000301540017
Pg = 4
Write a program in C language for
Insertion Sort.
#include <math.h>
#include <stdio.h>
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}

// Driver code
int main()
{
int arr[] = {11,14,33,5,6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}
 Program-4 Chirayu Baliyan
2000301540017
Pg 5
Write a program in C language for
Selection Sort .
#include <stdio.h>

int main() {
int arr[10]={6,12,0,18,11,99,55,45,34,2};
int n=10;
int i, j, position, swap;

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

position = i;
for (j = i + 1; j < n; j++) {
if (arr[position] > arr[j])
position = j;
}

if (position != i) {
swap = arr[i];
arr[i] = arr[position];
arr[position] = swap;
}
}

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

printf("%d\t", arr[i]);
return 0;
}
 Chirayu Baliyan
Program-5 2000301540017
Pg 6
Write a program in C language for
Quick Sort.

#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
}
int main() {
int data[] = {18, 7, 82, 61, 0, 99, 6};
int n = sizeof(data) / sizeof(data[0]);
printArray(data, n);
quickSort(data, 0, n - 1);
printArray(data, n);
return 0;
}
 Program-6 Chirayu Baliyan
2000301540017
Write a program in C language for Pg 7

Merge Sort.
#include <stdio.h>
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];

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

L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

int i, j, k;
i = 0;
j = 0;
k = p;

while (i < n1 && j < n2) {

if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
}
else
{
arr[k] = M[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = L[i];
i++;
k++;
}

while (j < n2) {

arr[k] = M[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) { Chirayu Baliyan
2000301540017
Pg 8
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
}
int main() {
int arr[] = {26, 5, 12, 10, 19, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printArray(arr, size);
}
 Program - 7 Chirayu Baliyan
2000301540017
Pg 9
Write a program in C language for Bubble Sort

#include <stdio.h>
void swap(int* xp, int* yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
}
int main()
{
int arr[] = {5,26,19,1,10,12};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
 Program - 8 Chirayu Baliyan
2000301540017
Write a C program to implement fractional Knapsack Pg 10
using Greedy Method
#include <stdio.h>
void main()
{
int capacity, no_items, cur_weight, item;
int used[10];
float total_profit;
int i;
int weight[10];
int value[10];
printf("Enter the capacity of knapsack:\n");
scanf("%d", &capacity);
printf("Enter the number of items:\n");
scanf("%d", &no_items);
printf("Enter the weight and value of %d item:\n", no_items);
for (i = 0; i < no_items; i++){
printf("Weight[%d]:\t", i);
scanf("%d", &weight[i]);
printf("Value[%d]:\t", i);
scanf("%d", &value[i]);
}
for (i = 0; i < no_items; ++i)
used[i] = 0;
cur_weight = capacity;
while (cur_weight > 0){
item = -1;
for (i = 0; i < no_items; ++i)
if ((used[i] == 0) &&
((item == -1) || ((float) value[i] / weight[i] > (float) value[item] / weight[item])))
item = i;
used[item] = 1;
cur_weight -= weight[item];
total_profit += value[item];
if (cur_weight >= 0)
printf("Added object %d (%d Rs., %dKg) completely in
the bag. Space left: %d.\n", item + 1, value[item], weight[item], cur_weight);
else{
int item_percent = (int) ((1 + (float) cur_weight / weight[item]) * 100);
printf("Added %d%% (%d Rs., %dKg) of object %d in the
bag.\n", item_percent, value[item], weight[item], item + 1);
total_profit -= value[item];
total_profit += (1 + (float)cur_weight / weight[item]) * value[item];
}
}

printf("Filled the bag with objects worth %.2f Rs.\n", total_profit);}

Chirayu Baliyan
2000301540017
Pg 10