11.

Develop a C program to implement and demonstrate the following searching

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

// 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

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;

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

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

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;