11.
Develop a C program to implement and demonstrate the following searching
algorithms: a) Linear Search b) Binary Search
a) Linear Search
#include <stdio.h>
// Function prototype
int lsearch(int n, int a[], int item);
int main()
int a[10], loc = -1, i, item, n;
printf("Enter size of array (max 10):\n");
scanf("%d", &n);
printf("Enter elements of the array:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter the item to search:\n");
scanf("%d", &item);
loc = lsearch(n, a, item);
if (loc == -1)
printf("Search unsuccessful\n");
else
printf("Item found at position %d\n", loc + 1);
return 0;
// Linear search function
int lsearch(int n, int a[], int item)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == item)
return i;
return -1;
Linear Search Recursive
#include <stdio.h>
// Function prototype
int lsearch(int n, int a[], int item);
int main()
int a[10], loc = -1, i, item, n;
printf("Enter size of array (max 10):\n");
scanf("%d", &n);
printf("Enter elements of the array:\n");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter the item to search:\n");
scanf("%d", &item);
loc = lsearch(n, a, item);
if (loc == -1)
printf("Search unsuccessful\n");
else
printf("Item found at position %d\n", loc + 1);
return 0;
// Linear search function
int lsearch(int n, int a[], int item)
if(n<0)
return -1; // base case: item not found
if(a[n-1]==item)
return(n-1); // base case: item found
else
return lsearch(n-1,a,item); // recursive call
b) Binary Search
#include <stdio.h>
// Function prototype
int binsearch(int a[], int n, int item);
int main() {
int a[10], i, item, n, pos;
printf("Enter number of elements:\n");
scanf("%d", &n);
printf("Enter elements in sorted order:\n");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("Enter item to search:\n");
scanf("%d", &item);
pos = binsearch(a, n, item);
if (pos != -1)
printf("Item %d found at position %d \n", item, pos+1);
else
printf("Item %d is not found\n", item);
return 0;
// Binary search function
int binsearch(int a[], int n, int item) {
int beg = 0, end = n - 1, mid;
while (beg <= end) {
mid = (beg + end) / 2;
if (item == a[mid])
return mid;
else if (item > a[mid])
beg = mid + 1;
else
end = mid - 1;
return -1;
Binary Search Recursive
#include <stdio.h>
// Function prototype
int binsearch(int a[], int beg, int end, int item);
int main() {
int a[10], i, item, n, loc;
printf("Enter number of elements:\n");
scanf("%d", &n);
printf("Enter elements in sorted order:\n");
for(i = 0; i < n; i++) // 0-based indexing
scanf("%d", &a[i]);
printf("Enter item to search:\n");
scanf("%d", &item);
loc = binsearch(a, 0, n - 1, item);
if (loc == -1)
printf("Item %d is not found\n", item);
else
printf("Item %d found at position %d \n", item, loc + 1); // position = index + 1
return 0;
// Recursive binary search function
int binsearch(int a[], int beg, int end, int item) {
int mid;
if (beg > end)
return -1;
mid = (beg + end) / 2;
if (item == a[mid])
return mid;
else if (item > a[mid])
return binsearch(a, mid + 1, end, item);
else
return binsearch(a, beg, mid - 1, item);
12.Develop a C program to implement and demonstrate the following searching
algorithms: a) Bubble sort b) Selection sort.
a) Selection sort
#include <stdio.h>
void SelectionSort(int arr[], int n)
int i, j, small;
for (i = 0; i < n-1; i++) // One by one move boundary of unsorted subarray
small = i; //minimum element in unsorted array
for (j = i+1; j < n; j++)
if (arr[j] < arr[small])
small = j;
// Swap the minimum element with the first element
if(small!=i)
{
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
printf("Sorted Array: ");
for(i = 0; i < n; i++)
printf("%d ", arr[i]);
int main()
int arr[100], i, n, step, temp;
// ask user for number of elements to be sorted
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
}
// call the function SelectionSort
SelectionSort(arr, n);
return 0;
b) Bubble sort.
#include <stdio.h>
void bubbleSort(int arr[], int n)
int i, j, temp;
for(i = 0; i < n-1; i++)
for(j = 0; j < n-1-i; j++)
if( arr[j] > arr[j+1])
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
// print the sorted array
printf("Sorted Array: ");
for(i = 0; i < n; i++)
printf("%d ", arr[i]);
int main()
int arr[100], i, n, step, temp;
// ask user for number of elements to be sorted
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
// call the function bubbleSort
bubbleSort(arr, n);
return 0;
}
Write a C program to implement insertion sort
#include <stdio.h>
int main() {
int a[5] = {4, 3, 5, 1, 2};
int i, j, key;
for (i = 1; i < 5; i++) {
key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
a[j + 1] = key;
// Print the sorted array
for (i = 0; i < 5; i++) {
printf("%d ", a[i]);
return 0;
