NGINEERING
F E D,MUZA & T
E O ROA FFA EC
EG TH RN HN
LL SA AG
OL
ON
AR
.C
OG
JA
S.D
Y
(2023-2024)
PRACTICLE FILE
Subject-DAA(KCS-553)
SUBMITTED TO: SUBMITTED BY:
Ms. KANAN JAIN Mr. ASMIT KUMAR VERMA
B. tech(COMPUTER SCIENCE)
Third year(5th semester)
INDEX
S. No. Practicle name Date Sign
01. Write a program in C
Recursive Linear Search
02. Write a program in C of
Recursive Binary Search
03. Write a program in C to
implement Quick Sort
04. Write a program in C for
Selection Sort.
05. Write a program in C of
Insertion Sort
06. Write a program in C
Merge Sort.
07. Write A program in C on
Heap Sort.
Program--01
Objective: Write a program in C Recursive Linear Search
Program :
#include <stdio.h>
int RecursiveLS(int arr[], int value, int index, int n)
{
int pos = 0;
if(index >= n)
{
return 0;
}
else if (arr[index] == value)
{
pos = index + 1;
return pos;
}
else
{
return RecursiveLS(arr, value, index+1, n);
}
return pos;
}
int main()
{
int n, value, pos, m = 0, arr[100];
printf("Enter the total elements in the array ");
scanf("%d", &n);
printf("Enter the array elements\n");
for (int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
}
printf("Enter the element to search ");
scanf("%d", &value);
pos = RecursiveLS(arr, value, 0, n);
if (pos != 0)
{
printf("Element found at pos %d ", pos);
}
else
{
printf("Element not found");
}
Return 0;
}
Output :
Enter the total elements int the array 6
Enter the array elements
• Enter the elements to search 6
• Elements found at pos- 2
Algorithm:
Step1: Start
Step2: initialize i=0 until i<n, repeat step 4
Step 3; set pos = linear[a,n,key]
Step4: if n>=0 the
If [an-1]= key
Return n; go to step 5
Else return S(a,n-1,key)
Step5: if pos!=0
Printf(“ elemets found”);
else
printf(“ elements not found”);
Step6: Exit
Program--02
Objective: Write a program in C of Recursive Binary Search
Program:
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x)
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x) {
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
return -1;
int main(void)
int arr[] = { 2, 3, 4, 10, 40 };
int size = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int index = binarySearch(arr, 0, size - 1, x);
if (index == -1) {
printf("Element is not present in array");
else {
printf("Element is present at index %d", index);
return 0;
Output:
10 is found at index 3
Algorithm:
Step 1: Binary Search[int [a],int first ,int last,int element]
Step2: if (last>= first){
Mid=(first+last)/2; otherwise go to step 6
Step3: if a[mid]= element
Return mid+1;
Step4: else if(a[mid]<element)
Return binarysearch(a,mid+1,last,element)
Step5: else : Return binarysearch(a,beg,mid-1,element)
Step6: return-1;
Step7: Stop.
Program--03
Objective : Write a program in C to implement Quick Sort
Program:
#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);
for (int 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]);
printf("\n");
}
int main() {
int arr[] = { 12, 17, 6, 25, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Sorted array: \n");
printArray(arr, n);
return 0; }
Output:
Sorted Array is
{1,5,6,12,17,25}
Algorithm:
Step1: Start
Step2: down= lb
Step3: up= ub
Step4: pivot= a[lb];
Step5: while(A[down]<=pivot && down,ub) and down++
Step6: while(a[up>pivot && up>lb and up)
Step7: if(down < up) interchange a[down] and a[up] and go to step5
Step8: Interchange a[up] and a[lb]
Step9: return up
Step10: stop
Program--04
Objective : Write a program in C for Selection Sort.
Program:
#include <stdio.h>
void selection(int arr[], int n)
{
int i, j, small;
for (i = 0; i < n-1; i++)
{
small = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[small])
small = j;
int temp = arr[small];
arr[small] = arr[i];
arr[i] = temp;
}
}
void printArr(int a[], int n){
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Output:
Sorted array is ={8,12,17,25,31,32}
Algorithm:
SELECTION SORT(arr, n)
Step 1: Repeat Steps 2 and 3 for i = 0 to n-1
Step 2: CALL SMALLEST(arr, i, n, pos)
Step 3: SWAP arr[i] with arr[pos]
[END OF LOOP]
Step 4: EXIT
SMALLEST (arr, i, n, pos)
Step 1: [INITIALIZE] SET SMALL = arr[i]
Step 2: [INITIALIZE] SET pos = i
Step 3: Repeat for j = i+1 to n
if (SMALL > arr[j])
SET SMALL = arr[j]
SET pos = j
[END OF if]
[END OF LOOP]
Step 4: RETURN pos
Program--05
Objective: Write a program in C of Insertion Sort.
Program:
#include <stdio.h>
void insert(int a[], int n) {
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) {
a[j+1] = a[j];
j = j-1;
}
a[j+1] = temp;
}
}
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
insert(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
Output:
Sorted array is :
{8,12,17,25,31,32}
Algorithm:
The simple steps of achieving the insertion sort are listed as follows -
Step 1 : If the element is the first element, assume that it is already sorted.
Return 1.
Step2 : Pick the next element, and store it separately in a key.
Step3 : Now, compare the key with all elements in the sorted array.
Step 4 : If the element in the sorted array is smaller than the current
element, then move to the next element. Else, shift greater elements in the
array towards the right.
Step 5 : Insert the value.
Step 6 : Repeat until the array is sorted.
Program--06
Objective: Write a program in C Merge Sort.
Program:
#include <stdio.h>
void merge(int a[], int beg, int mid, int end)
{
int i, j, k;
int n1 = mid - beg + 1;
int n2 = end - mid;
int LeftArray[n1], RightArray[n2];
for (int i = 0; i < n1; i++)
LeftArray[i] = a[beg + i];
for (int j = 0; j < n2; j++)
RightArray[j] = a[mid + 1 + j];
i = 0;
j = 0;
k = beg;
while (i < n1 && j < n2)
{
if(LeftArray[i] <= RightArray[j])
{
a[k] = LeftArray[i];
i++;
}
else
{
a[k] = RightArray[j];
j++;
}
k++;
}
while (i<n1)
{
a[k] = LeftArray[i];
i++;
k++;
}
while (j<n2)
{
a[k] = RightArray[j];
j++;
k++;
}
}
void mergeSort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
mergeSort(a, beg, mid);
mergeSort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
void printArray(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n");
}
int main()
{
int a[] = { 12, 31, 25, 8, 32, 17, 40, 42 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArray(a, n);
mergeSort(a, 0, n - 1);
printf("After sorting array elements are - \n");
printArray(a, n);
return 0;
}
Output:
Algorithm:
1. MERGE_SORT(arr, beg, end)
2. if beg < end
3. set mid = (beg + end)/2
4. MERGE_SORT(arr, beg, mid)
5. MERGE_SORT(arr, mid + 1, end)
6. MERGE (arr, beg, mid, end)
7. end of if
8. END MERGE_SORT
Program--07
Objective: Write A program in C on Heap Sort.
Program:
#include <
#include <stdio.h>
void swap(int* a, int* b)
int temp = *a;
*a = *b;
*b = temp;
void heapify(int arr[], int N, int i)
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < N && arr[left] > arr[largest])
largest = left;
if (right < N && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, N, largest);
}
void heapSort(int arr[], int N)
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
for (int i = N - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
void printArray(int arr[], int N)
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
printf("\n");
int main()
int arr[] = { 12, 11, 13, 5, 6, 7 };
int N = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, N);
printf("Sorted array is\n");
printArray(arr, N);
Output:
Sorted array is:
5 6 7 11 12 13
Algorithm:
First convert the array into heap data structure using heapify, then one by
one delete the root node of the Max-heap and replace it with the last node
in the heap and then heapify the root of the heap. Repeat this process until
size of heap is greater than 1.
• Build a heap from the given input array.
• Repeat the following steps until the heap contains only one element:
• Swap the root element of the heap (which is the largest element) with
the last element of the heap.
• Remove the last element of the heap (which is now in the correct
position).
• Heapify the remaining elements of the heap.
• The sorted array is obtained by reversing the order of the elements in
the input array
