Department of Electrical Engineering Autumn 2025
EEO 101: DATA STRUCTURES
Worksheet – 8
Name: Anuj Kumar Gupta
Enrollment: 24115026
Department: Department of Electrical Engineering
Year: 2nd
Batch: B
Q1. Write functions to implement following algorithms for sorting the given list of data
InsertionSort( )
SelectionSort( )
BubblesSort( )
QuickSort( )
MergeSort( )
HeapSort( )
Compare the above for a given set of reasonably large set of sample data w.r.t.
execution time and memory requirement.
CODE:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
// ---------------- Insertion Sort ----------------
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;
}
}
// ---------------- Selection Sort ----------------
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIdx])
minIdx = j;
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
// ---------------- Bubble Sort ----------------
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// ---------------- Quick Sort ----------------
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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
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);
}
}
// ---------------- Merge Sort ----------------
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int *L = (int*)malloc(n1 * sizeof(int));
int *R = (int*)malloc(n2 * sizeof(int));
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++];
free(L);
free(R);
}
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);
}
}
// ---------------- Heap Sort ----------------
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
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--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
// ---------------- Timing Helper ----------------
void measure(void (*sortFunc)(int[], int), int arr[], int n, const char *name) {
int *temp = (int*)malloc(n * sizeof(int));
memcpy(temp, arr, n * sizeof(int));
clock_t start = clock();
sortFunc(temp, n);
clock_t end = clock();
double time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("%-15s : %.5f sec\n", name, time_taken);
free(temp);
}
int main() {
int n = 10000; // you can increase this value for larger comparison
int *data = (int*)malloc(n * sizeof(int));
srand(time(0));
for (int i = 0; i < n; i++)
data[i] = rand();
printf("Execution Time Comparison for n = %d\n", n);
printf("--------------------------------------------------\n");
measure(insertionSort, data, n, "InsertionSort");
measure(selectionSort, data, n, "SelectionSort");
measure(bubbleSort, data, n, "BubbleSort");
// For QuickSort, MergeSort, HeapSort, we need wrapper calls
{
int *temp = (int*)malloc(n * sizeof(int));
memcpy(temp, data, n * sizeof(int));
clock_t start = clock();
quickSort(temp, 0, n - 1);
clock_t end = clock();
printf("%-15s : %.5f sec\n", "QuickSort", ((double)(end - start)) / CLOCKS_PER_SEC);
free(temp);
}
{
int *temp = (int*)malloc(n * sizeof(int));
memcpy(temp, data, n * sizeof(int));
clock_t start = clock();
mergeSort(temp, 0, n - 1);
clock_t end = clock();
printf("%-15s : %.5f sec\n", "MergeSort", ((double)(end - start)) / CLOCKS_PER_SEC);
free(temp);
}
measure(heapSort, data, n, "HeapSort");
printf("\nApproximate Memory Usage:\n");
printf("InsertionSort, SelectionSort, BubbleSort, HeapSort => O(1) extra\n");
printf("QuickSort => O(log n) (recursion stack)\n");
printf("MergeSort => O(n) (temporary arrays)\n");
free(data);
return 0;
}
Comments
//Implemented all given sorting algorithms and measured their time taken
OUTPUT
Q2. Write functions to implement
Sequential search
Binary search
Indexed sequential search
CODE
#include <stdio.h>
#include <stdlib.h>
int sequentialSearch(int arr[], int n, int key)
{
for (int i = 0; i < n; i++)
{
if (arr[i] == key)
return i;
}
return -1;
}
int binarySearch(int arr[], int n, int key)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int indexedSequentialSearch(int arr[], int n, int key, int blockSize)
{
int index[100], indexValue[100];
int numBlocks = 0;
// Build index table
for (int i = 0; i < n; i += blockSize)
{
index[numBlocks] = i;
indexValue[numBlocks] = arr[i];
numBlocks++;
}
// Find block where key might exist
int block = -1;
for (int i = 0; i < numBlocks; i++)
{
if (key < indexValue[i])
{
block = i - 1;
break;
}
}
if (block == -1)
block = numBlocks - 1;
if (block < 0)
return -1;
// Sequential search within block
int start = index[block];
int end = (start + blockSize < n) ? start + blockSize : n;
for (int i = start; i < end; i++)
{
if (arr[i] == key)
return i;
}
return -1;
}
int main()
{
int n, key, pos;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d sorted elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Enter element to search: ");
scanf("%d", &key);
// Sequential Search
pos = sequentialSearch(arr, n, key);
if (pos != -1)
printf("Sequential Search: Found at index %d\n", pos);
else
printf("Sequential Search: Not found\n");
// Binary Search
pos = binarySearch(arr, n, key);
if (pos != -1)
printf("Binary Search: Found at index %d\n", pos);
else
printf("Binary Search: Not found\n");
// Indexed Sequential Search
int blockSize = 3; // you can choose sqrt(n) for optimization
pos = indexedSequentialSearch(arr, n, key, blockSize);
if (pos != -1)
printf("Indexed Sequential Search: Found at index %d\n", pos);
else
printf("Indexed Sequential Search: Not found\n");
return 0;
}
Comments
// Implemented functions to conduct given searches
OUTPUT
[Link] function to implement
Ternary search & Interpolation search
CODE
#include <stdio.h>
int ternarySearch(int arr[], int left, int right, int key) {
while (left <= right) {
int mid1 = left + (right - left) / 3;
int mid2 = right - (right - left) / 3;
if (arr[mid1] == key)
return mid1;
if (arr[mid2] == key)
return mid2;
if (key < arr[mid1])
right = mid1 - 1;
else if (key > arr[mid2])
left = mid2 + 1;
else {
left = mid1 + 1;
right = mid2 - 1;
}
}
return -1;
}
int interpolationSearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high && key >= arr[low] && key <= arr[high]) {
if (low == high) {
if (arr[low] == key)
return low;
return -1;
}
int pos = low + (((double)(high - low) / (arr[high] - arr[low])) * (key - arr[low]));
if (arr[pos] == key)
return pos;
else if (arr[pos] < key)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
int main() {
int n, key, pos;
printf("Enter number of elements: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d sorted elements: ", n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
printf("Enter element to search: ");
scanf("%d", &key);
pos = ternarySearch(arr, 0, n - 1, key);
if (pos != -1)
printf("Ternary Search: Found at index %d\n", pos);
else
printf("Ternary Search: Not found\n");
pos = interpolationSearch(arr, n, key);
if (pos != -1)
printf("Interpolation Search: Found at index %d\n", pos);
else
printf("Interpolation Search: Not found\n");
return 0;
}
Comments
// Created given functions
OUTPUT
Q4. Compare efficiency of Binary, Ternary and Interpolation search for a reasonably
larger size of data.
CODE
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// Binary Search
int binarySearch(int arr[], int n, int key)
{
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
// Ternary Search
int ternarySearch(int arr[], int l, int r, int key)
{
while (r >= l)
{
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
if (arr[mid1] == key)
return mid1;
if (arr[mid2] == key)
return mid2;
if (key < arr[mid1])
r = mid1 - 1;
else if (key > arr[mid2])
l = mid2 + 1;
else
{
l = mid1 + 1;
r = mid2 - 1;
}
}
return -1;
}
// Interpolation Search
int interpolationSearch(int arr[], int n, int key)
{
int low = 0, high = n - 1;
while (low <= high && key >= arr[low] && key <= arr[high])
{
if (low == high)
{
if (arr[low] == key)
return low;
return -1;
}
int pos = low + ((double)(key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
if (arr[pos] == key)
return pos;
if (arr[pos] < key)
low = pos + 1;
else
high = pos - 1;
}
return -1;
}
// ---------- MAIN ----------
int main()
{
int n = 1000000; // 1 million elements
int *arr = (int *)malloc(n * sizeof(int));
// Generate sorted data
for (int i = 0; i < n; i++)
arr[i] = i * 2; // uniform distribution
int key = arr[n - 10]; // pick key near end
clock_t start, end;
double timeBinary, timeTernary, timeInterpolation;
int repetitions = 100000; // repeat to get measurable time
int found;
// Binary Search
start = clock();
for (int i = 0; i < repetitions; i++)
found = binarySearch(arr, n, key);
end = clock();
timeBinary = ((double)(end - start)) / CLOCKS_PER_SEC / repetitions;
// Ternary Search
start = clock();
for (int i = 0; i < repetitions; i++)
found = ternarySearch(arr, 0, n - 1, key);
end = clock();
timeTernary = ((double)(end - start)) / CLOCKS_PER_SEC / repetitions;
// Interpolation Search
start = clock();
for (int i = 0; i < repetitions; i++)
found = interpolationSearch(arr, n, key);
end = clock();
timeInterpolation = ((double)(end - start)) / CLOCKS_PER_SEC / repetitions;
// Display results
printf("Results for n = %d elements:\n", n);
printf("Binary Search Time: %.20f seconds\n", timeBinary);
printf("Ternary Search Time: %.20f seconds\n", timeTernary);
printf("Interpolation Search Time: %.20f seconds\n", timeInterpolation);
free(arr);
return 0;
}
Comments
// Implemented given searches and measured their time for efficiency
OUTPUT