230493131036 Analysis and Design of Algorithms
PRACTICAL:1
Aim: Implementation and Time analysis of sorting algorithms. Bubblesort,
Selection sort, Insertion sort, Merge sort and Quicksort.
BUBBLE SORT
#include <stdio.h>
void bubbleSort(int array[], int size) {
for (int step = 0; step < size - 1; ++step) {
for (int i = 0; i < size - step - 1; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
printf("\n");
int main() {
int data[] = {90, 20, 70, 10, 80};
int size = sizeof(data) / sizeof(data[0]);
bubbleSort(data, size);
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 1
230493131036 Analysis and Design of Algorithms
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
OUTPUT:
Fig: Bubble Sort
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 2
230493131036 Analysis and Design of Algorithms
SELECTION SORT
#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[] = { 90, 18, 50, 34, 12};
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 3
230493131036 Analysis and Design of Algorithms
printArr(a, n);
selection(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
OUTPUT:
Fig: Selection Sort
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 4
230493131036 Analysis and Design of Algorithms
INSERTION SORT
#include <stdio.h>
void insert(int a[], int n) /* function to sort an aay with insertion sort*/
int i, j, temp;
for (i = 1; i < n; i++) {
temp = a[i];
j = i - 1;
while(j>=0 && temp <= a[j]) /* Move the elements greater than temp to one position
ahead from their current position*/
a[j+1]=a[j];
j = j-1;
a[j+1] = temp;
}
void printArr(int a[], int n) /* function to print the array */
{
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])
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 5
230493131036 Analysis and Design of Algorithms
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:
Fig: Insertion Sort
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 6
230493131036 Analysis and Design of Algorithms
MERGE SORT
#include <stdio.h>
/* Function to merge the subarrays of a[] */
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]; //temporary arrays
/* copy data to temp arrays */
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; /* initial index of first sub-array */
j = 0; /* initial index of second sub-array */
k = beg; /* initial index of merged sub-array */
while (i < n1 && j < n2){
if(Left Array[i] <= Right Array[j])
{
a[k] = Left Array[i];
i++;
}
else
{
a[k] = Right Array[j];
j++;
}
k++;
}
while (i<n1){
a[k] = Left Array[i];
i++;
k++;
}
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 7
230493131036 Analysis and Design of Algorithms
while (j<n2){
a[k] = Right Array[j];
j++;
k++;
}
}
void merge Sort(int a[], int beg, int end)
{
if (beg < end)
{
int mid = (beg + end) / 2;
merge Sort(a, beg, mid);
merge Sort(a, mid + 1, end);
merge(a, beg, mid, end);
}
}
/* Function to print the array */
void print Array(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 = size of(a) / size of(a[0]);
printf("Before sorting array elements are - \n");
print Array(a, n);
merge Sort(a, 0, n - 1);
printf("After sorting array elements are - \n");
print Array(a, n);
return 0;
}
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 8
230493131036 Analysis and Design of Algorithms
OUTPUT:
Fig: Merge Sort
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 9
230493131036 Analysis and Design of Algorithms
QUICK SORT
#include <stdio.h>
/* function that consider last element as pivot,place the
pivot at its exact position, and place smaller elements to
left of pivot and greater elements to right of pivot. */
int partition (int a[], int start, int end)
{
int pivot = a[end]; // pivot element
int i = (start - 1);
for (int j = start; j <= end - 1; j++)
{
// If current element is smaller than the pivot
if (a[j] < pivot)
{
i++; // increment index of smaller element
int=a[i];
a[i]=a[j];
a[j] = t;
}
}
int t = a[i+1];
a[i+1] = a[end];
a[end] = t;
return (i + 1);
}
/* function to implement quick sort */
void quick(int a[], int start, int end) /* a[] = array to be sorted, start =Starting index,
end = Ending index */
{
if (start < end)
{
int p = partition(a, start, end); //p is the partitioning indexquick(a, start,
p - 1);
quick(a, p + 1, end);
}
}
/* function to print an array */
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 10
230493131036 Analysis and Design of Algorithms
void printArr(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", a[i]);
}
int main()
{
int a[] = { 24, 9, 29, 14, 19, 27 };
int n = sizeof(a) / sizeof(a[0]);
printf("Before sorting array elements are - \n");
printArr(a, n);
quick(a, 0, n - 1);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
return 0;
}
OUTPUT:
Fig: Quick Sort
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 11
230493131036 Analysis and Design of Algorithms
PRACTICAL:2
Aim: Implementation and Time analysis of linear and binary search algorithm.
1. Linear Search: -
Input :-
#include<stdio.h>
int main() {
int arr[20], size, key, i, index;
int countKey = 0; //initializing count of key element as 0
printf("Number of elements in the list: ");
scanf("%d", &size);
printf("Enter elements of the list:
");for (i = 0; i < size; i++)
scanf("%d", &arr[i]);
printf("Enter the element to search ie. key element:");
scanf("%d", &key);
for (index = 0; index < size; index++) {
if (arr[index] == key) {
printf("Key element found at index %d\n", index);
countKey++;
}
}
if (countKey == 0)
printf("Key element not found");
else
printf("Key element is present %d times in the array.\n", countKey);
return 0;
}
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 12
230493131036 Analysis and Design of Algorithms
Output : -
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 13
230493131036 Analysis and Design of Algorithms
2. Binary Search :-
Input : -
#include <stdio.h>
int binarySearch(int a[], int beg, int end, int val)
{
int mid;
if(end >= beg)
{ mid = (beg + end)/2;
if(a[mid] == val)
{
return mid+1;
}
else if(a[mid] < val)
{
return binarySearch(a, mid+1, end, val);
}
else
{
return binarySearch(a, beg, mid-1, val);
}
}
return -1;
}
int main() {
int a[] = {11, 14, 25, 30, 40, 41, 52, 57, 70};
int val = 40;
int n = sizeof(a) / sizeof(a[0]);
int res = binarySearch(a, 0, n-1, val);
printf("The elements of the array are");
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 14
230493131036 Analysis and Design of Algorithms
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
printf("\n Element to be searched is - %d",val);
if (res == -1)
printf("\n Element is not present in the array");
else
printf("\n Element is present at %d position of array", res);
return 0;
}
Output :-
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 15
230493131036 Analysis and Design of Algorithms
PRACTICAL: 3
AIM: Implementation of max-heap sort algorithm.
INPUT:
#include <stdio.h>
/* function to heapify a subtree. Here 'i' is the
index of root node in array a[], and 'n' is the size of heap. */
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 child is larger than root
if (left < n && a[left] > a[largest])
largest = left;
// If right child is larger than root
if (right < n && a[right] > a[largest])
largest = right;
// If root is not largest
if (largest != i) {
// swap a[i] with a[largest]
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 16
230493131036 Analysis and Design of Algorithms
heapify(a, n, largest);
}
}
/*Function to implement the heap sort*/
void heapSort(int a[], int n)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(a, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
/* Move current root element to end*/
// swap a[0] with a[i]
int temp = a[0];
a[0] = a[i];
a[i] = temp;
heapify(a, i, 0);
/* function to print the array elements */
void printArr(int arr[], int n)
for (int i = 0; i < n; ++i)
printf("%d", arr[i]);
printf(" ");
}
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 17
230493131036 Analysis and Design of Algorithms
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;
OUTPUT:
Fig: Max-Heap
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 18
230493131036 Analysis and Design of Algorithms
PRACTICAL: 4
AIM: Implementation and Time analysis of factorial program using iterative and recursive
method.
INPUT:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int fact(int x)
{
double f = x;
if (x != 1)
f *= fact(x - 1);
else
return 1; return
f;
}
void main()
{
int i, n;
double a, fa = 1;
clock_t end, start;
double cpu;
printf("\nEnter a number to find factorial ");
scanf("%d", &n);
start = clock();
for (i = n; i > 0; i--)
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 19
230493131036 Analysis and Design of Algorithms
fa *= i;
}
end = clock();
cpu = ((double)(end - start) / CLOCKS_PER_SEC);
printf("\nTime for iterative is %lf", cpu); printf("\nFactorial
of %d is %lf\n", n, fa);
start = clock();
a = fact(n); end
= clock();
cpu = ((double)(end - start) / CLOCKS_PER_SEC);
printf("\nTime for recursive is %lf", cpu);
printf("\nFactorial of %d is %lf", n, a); printf("\n");
}
OUTPUT:
Fig: Factorial
SNPITRC/CSE/2023-24/SEM-5/3150703 Page | 20
