CSBB 202
DESIGN AND ANALYSIS OF ALGORITHMS
Lab File
Submitted By:
Name: PARIDHI GUPTA
Roll No: 241210085
Branch: CSE
Semester: 3RD Sem
Submitted To: DR. GUNJAN
Department of Computer Science and Engineering
NATIONAL INSTITUTE OF TECHNOLOGY DELHI 2025
INDEX
[Link] Name of Experiment Date of Page Remarks
Experiment No.
1. Searching algorithms, Insertion Sort and Quick Sort 05.08.2025
2. Merge Sort algorithm, Comparison of other sorting 18.08.2025
algorithms
EXPERIMENT-1
Problem Statement:
a) Comparison of linear search and binary search.
b) Implement insertion sort.
c) Sort a given set of elements using the quicksort method and determine the time required to sort the
elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted.
The elements can be read from a file or can be generated using the random number generator.
Codes and Outputs:
a)Linear and Binary Search algorithms:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Linear Search
int linearsearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) return i;
}
return -1;
}
// Binary Search
int binarysearch(int arr[], int n, int x)
{
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == x) return mid;
else if (arr[mid] < x) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main()
{
printf ("\n Paridhi Gupta");
printf ("\n CSE 2");
printf ("\n 241210085");
int n, x;
printf("\n Enter number of elements: ");
scanf("%d", &n);
int *arr = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) arr[i] = i + 1;
printf("Enter element to search: ");
scanf("%d", &x);
clock_t start, end;
double time_taken;
// Linear Search
start = clock();
int pos1 = linearsearch(arr, n, x);
end = clock();
time_taken = (double)(end - start) / CLOCKS_PER_SEC;
printf("\n--- Linear Search ---\n");
if (pos1 != -1) printf("Element found at index %d\n", pos1);
else printf("Element not found\n");
printf("Time taken: %.8lf sec\n", time_taken);
// Binary Search
start = clock();
int pos2 = binarysearch(arr, n, x);
end = clock();
time_taken = (double)(end - start) / CLOCKS_PER_SEC;
printf("\n--- Binary Search ---\n");
if (pos2 != -1) printf("Element found at index %d\n", pos2);
else printf("Element not found\n");
printf("Time taken: %.8lf sec\n", time_taken);
free(arr);
return 0;
}
Time Complexity Analysis:
Output:
b)Insertion Sort:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
printf ("\n Paridhi Gupta");
printf ("\n CSE 2");
printf ("\n 241210085");
int n;
printf("\n Enter number of elements: ");
scanf("%d", &n);
int *arr = malloc(n * sizeof(int));
// Random number generator
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 10000;
}
clock_t start = clock();
insertionSort(arr, n);
clock_t end = clock();
printf("\nSorted Array:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("\nTime taken: %.8lf sec\n", time_taken);
free(arr);
return 0;
}
Time Complexity Analysis:
Output:
c) Quick Sort:
#include <stdio.h>
#include <stdlib.h>
#include <time.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; 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);
}
}
int main() {
printf ("\n Paridhi Gupta");
printf ("\n CSE 2");
printf ("\n 241210085");
int n;
printf("\n Enter number of elements: ");
scanf("%d", &n);
int *arr = malloc(n * sizeof(int));
srand(time(NULL));
for (int i = 0; i < n; i++) arr[i] = rand() % 10000;
clock_t start = clock();
quickSort(arr, 0, n - 1);
clock_t end = clock();
printf("\nSorted Array:\n");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
double time_taken = (double)(end - start) / CLOCKS_PER_SEC;
printf("\nTime taken: %.8lf sec\n", time_taken);
free(arr);
return 0;
}
Time Complexity Analysis:
Output:
EXPERIMENT-2
Problem Statement:
Implement a merge sort algorithm to sort a given set of elements and determine the time required to sort the
elements. Repeat the experiment for different values of n, the number of elements in the list to be sorted.
The elements can be read from a file or can be generated using the random number generator.
Comparison of
(i) Counting sort,
(ii) (ii) Radix sort,
(iii) (iii) Bucket sort
Make a tabular comparison of time complexity for best, average, and worst case.
Codes and Outputs:
Merge Sort Algorithm:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
int main() {
printf ("\n Paridhi Gupta");
printf ("\n CSE 2");
printf ("\n 241210085");
int sizes[] = {1000, 5000, 10000, 50000, 100000};
int numSizes = sizeof(sizes) / sizeof(sizes[0]);
srand(time(0));
for (int s = 0; s < numSizes; s++) {
int n = sizes[s];
int *arr = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
arr[i] = rand() % 100000;
}
clock_t start = clock();
mergeSort(arr, 0, n - 1);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("N = %d -> Time: %f seconds\n", n, time_taken);
free(arr);
}
return 0;
}
Time Complexity Analysis:
Output:
Comparison between (i) Counting sort, (ii) Radix sort, (iii) Bucket sort