Experiment: Implementation of Linked Lists (Insertion, Deletion, Inversion)

Objective: To implement a Linked List data structure to understand the dynamic organization of data. The goal is to
perform fundamental operations such as insertion, deletion, searching, and reversing the list.

Theory: A Linked List is a linear data structure where elements, known as nodes, are not stored at contiguous
memory locations. Each node consists of two parts: the data field, which stores the actual information, and the link (or
next) field, which holds the reference to the next node in the sequence. This structure allows for efficient insertion and
deletion of elements, as the list can grow or shrink dynamically without shifting existing elements. In this specific
experiment, we simulate this behavior using an "Array of Structures," where integer indices are used instead of
pointers to connect the nodes within a static memory block.

Algorithm:

1.​ Initialization:
1.​ Set head = -1 to indicate an empty list.
2.​ Set free_pos = 0 to track the first available index in the array.
2.​ Insert (General Logic):
1.​ Check if free_pos >= MAX (Overflow). If yes, stop.
2.​ Allocate a new index n from free_pos.
3.​ Read data into list[n].data.
4.​ Update indices:
■​ Begin: Set list[n].next = head, then update head = n.
■​ End: Traverse to the last node (where next == -1), link it to n, and set list[n].next
= -1.
Position: Traverse to the node before the target position, link n between them by
■​
adjusting indices.
3.​ Delete (General Logic):
1.​ If head == -1, print "Empty".
2.​ Begin: Update head to list[head].next.
3.​ End/Position: Traverse to the specific node using indices, then update the previous node's next
field to skip the current node (e.g., [Link] = [Link]).
4.​ Reverse:
1.​ Initialize prev = -1, curr = head.
2.​ Loop while curr != -1:
■​ Store the next node's index: next = list[curr].next.
■​ Reverse the link: list[curr].next = prev.
■​ Shift pointers: prev = curr, curr = next.
3.​ Update head = prev.

Code:

// Exp 4A: Implementation of Linked lists: inserting, deleting, and inverting a linked list

// Hriddhi Bhattacharyya. 10900324160. 2B-130

// 15-12-2025
#include <stdio.h>

#define MAX 50

struct node {

int data;

int next;

};

struct node list[MAX];

int head = -1;

int free_pos = 0;

int getnode() {

if (free_pos >= MAX) {

printf("Overflow\n");

return -1;

return free_pos++;

void insert_begin();

void insert_end();

void insert_pos();
void delete_begin();

void delete_end();

void delete_pos();

void search();

void display();

void reverse();

void insert_begin() {

int n = getnode();

if (n == -1) return;

printf("Data: ");

scanf("%d", &list[n].data);

list[n].next = head;

head = n;

void insert_end() {

int n = getnode();

if (n == -1) return;

printf("Data: ");

scanf("%d", &list[n].data);

list[n].next = -1;

if (head == -1) {

head = n;
 } else {

int temp = head;

while (list[temp].next != -1)

temp = list[temp].next;

list[temp].next = n;

void insert_pos() {

int pos, i = 1, temp, n;

printf("Pos: ");

scanf("%d", &pos);

if (pos == 1) {

insert_begin();

return;

temp = head;

while (temp != -1 && i < pos - 1) {

temp = list[temp].next;

i++;

if (temp == -1) {
 printf("Out of range\n");

} else {

n = getnode();

if (n == -1) return;

printf("Data: ");

scanf("%d", &list[n].data);

list[n].next = list[temp].next;

list[temp].next = n;

void delete_begin() {

if (head == -1) {

printf("Empty\n");

return;

head = list[head].next;

void delete_end() {

if (head == -1) {

printf("Empty\n");

return;

if (list[head].next == -1) {
 head = -1;

} else {

int temp = head, prev;

while (list[temp].next != -1) {

prev = temp;

temp = list[temp].next;

list[prev].next = -1;

void delete_pos() {

int pos, i = 1, temp, prev;

if (head == -1) return;

printf("Pos: ");

scanf("%d", &pos);

if (pos == 1) {

head = list[head].next;

return;

temp = head;

while (temp != -1 && i < pos) {

prev = temp;
 temp = list[temp].next;

i++;

if (temp == -1) printf("Not found\n");

else list[prev].next = list[temp].next;

void search() {

int key, pos = 1, temp = head;

printf("Key: ");

scanf("%d", &key);

while (temp != -1) {

if (list[temp].data == key) {

printf("Pos: %d\n", pos);

return;

temp = list[temp].next;

pos++;

printf("Not found\n");

void display() {

int temp = head;

 while (temp != -1) {

printf("%d -> ", list[temp].data);

temp = list[temp].next;

printf("NULL\n");

void reverse() {

int prev = -1, curr = head, next;

while (curr != -1) {

next = list[curr].next;

list[curr].next = prev;

prev = curr;

curr = next;

head = prev;

int main() {

int choice;

printf("Implementation of Linked List using Array of Structures\n");

while (1) {

printf("\[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]\n");

printf("Choice: ");

scanf("%d", &choice);
 switch (choice) {

case 1: insert_begin(); break;

case 2: insert_end(); break;

case 3: insert_pos(); break;

case 4: delete_begin(); break;

case 5: delete_end(); break;

case 6: delete_pos(); break;

case 7: search(); break;

case 8: display(); break;

case 9: reverse(); break;

case 10: return 0;

default: printf("Invalid\n");

Output:

Plaintext

Implementation of Linked List using Array of Structures

[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 1

Data: 10
[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 2

Data: 20

[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 2

Data: 30

[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 8

10 -> 20 -> 30 -> NULL

[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 9

[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 8

30 -> 20 -> 10 -> NULL

[Link] Begin [Link] [Link] [Link] Begin [Link] End [Link] Pos [Link] [Link] [Link] [Link]

Choice: 10

Conclusion: In this experiment, we successfully studied the Linked List data structure. It was observed that unlike
arrays, linked lists allow for efficient memory utilization and flexible data management. The implementation using an
array of structures provided a practical understanding of how nodes are linked logically even if they are stored
physically in a static block.
Experiment: Implementation of Circular Queue using Linked List

Objective: To implement the Circular Queue data structure using a Linked List to demonstrate the First-In-First-Out
(FIFO) principle with dynamic memory allocation.

Theory: A Circular Queue implemented using a Linked List is a linear data structure where the last node is
connected back to the first node to form a circle. Unlike a linear linked list where the last node points to NULL, here
the next pointer of the rear node always points to the front node.

Unlike the Array implementation, this method does not require the modulo (%) operator to wrap around. It overcomes
the size limitation of static arrays as memory is allocated dynamically using malloc.

●​ Enqueue: Insert at rear. Update rear to the new node and make rear->next point to front.
●​ Dequeue: Delete from front. Update front to front->next and ensure rear->next points to the new
front.

Algorithm:

1.​ Enqueue (Insertion):

1.​ Start.
2.​ Allocate memory for newNode. If NULL, print "FULL".
3.​ Read data into newNode.
4.​ If front is NULL (Empty Queue):
■​ Set front = rear = newNode.
■​ Set rear->next = front.
5.​ Else:
■​ Set rear->next = newNode.
■​ Set rear = newNode.
■​ Set rear->next = front (Establish circular link).
6.​ Stop.
2.​ Dequeue (Deletion):
1.​ Start.
2.​ If front is NULL, print "EMPTY".
3.​ If front == rear (Only one node):
■​ Free front.
■​ Set front = rear = NULL.
4.​ Else:
■​ Set temp = front.
■​ Move front to front->next.
■​ Update rear->next = front.
■​ Free temp.
5.​ Stop.
3.​ Display:
1.​ Start.
2.​ If front is NULL, print "EMPTY".
3.​ Set temp = front.
4.​ Print temp->data.
5.​ Move temp = temp->next.
 6.​ Repeat steps 4-5 while temp != front.
7.​ Stop.

Code:

C
// Circular Queue (using linked list) and its operations using switch case
// Hriddhi Bhattacharyya_10900324160_ECE-2B-130
// DATE: 06.01.2026

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
};

struct Node *front = NULL;

struct Node *rear = NULL;

void enqueue()
{
int x;
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
{
printf("FULL\n");
}
else
{
printf("ENTER ELEMENT: ");
scanf("%d", &x);
newNode->data = x;
if (front == NULL)
{
front = rear = newNode;
rear->next = front;
}
else
{
rear->next = newNode;
rear = newNode;
rear->next = front;
}
printf("INSERTED %d\n", x);
}
}

void dequeue()
{
struct Node *temp;
if (front == NULL)
{
 printf("EMPTY\n");
}
else if (front == rear)
{
printf("DELETED %d\n", front->data);
free(front);
front = rear = NULL;
}
else
{
temp = front;
printf("DELETED %d\n", front->data);
front = front->next;
rear->next = front;
free(temp);
}
}

void display()
{
struct Node *temp;
if (front == NULL)
{
printf("EMPTY\n");
}
else
{
printf("QUEUE ");
temp = front;
do
{
printf("%d ", temp->data);
temp = temp->next;
} while (temp != front);
printf("\n");
}
}

int main()
{
int choice;
do
{
printf("\nMENU\n1 INSERT\t2 DELETE\t3 DISPLAY\t4 EXIT\n");
printf("CHOICE: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
 case 3:
display();
break;
case 4:
printf("EXITTED\n");
break;
default:
printf("INVALID\n");
break;
}
} while (choice != 4);
return 0;
}

Output:

Plaintext
MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 1
ENTER ELEMENT: 23
INSERTED 23

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 1
ENTER ELEMENT: 34
INSERTED 34

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 2
DELETED 23

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 3
QUEUE 34

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 4
EXITTED

Conclusion: The Circular Queue using Linked List efficiently utilizes memory by allocating nodes dynamically during
runtime. It eliminates the problem of fixed size encountered in the Array implementation. The circular nature is
maintained by pointing the rear node's next pointer to the front node, allowing continuous operations without
resetting pointers.

​
​
​

Experiment: Implementation of Linear Queue using Linked List

Objective: To implement the Linear Queue data structure using a Linked List to demonstrate the First-In-First-Out
(FIFO) principle with dynamic memory allocation.

Theory: A Linear Queue implemented using a Linked List is a linear data structure where elements are arranged
sequentially. It follows the FIFO (First In First Out) principle, where insertion takes place at the rear end and deletion
happens at the front end.

Unlike the Array implementation, the Linked List implementation allows the queue to grow dynamically according to
memory availability, eliminating the "Queue Full" problem (overflow) unless the system memory is exhausted.

●​ Front Pointer: Points to the first node (element to be deleted).

●​ Rear Pointer: Points to the last node (element just inserted).
●​ Next Pointer: The last node's next pointer is always NULL.

Algorithm:

1.​ Enqueue (Insertion):

1.​ Start.
2.​ Allocate memory for newNode. If NULL, print "FULL".
3.​ Read data into newNode. Set newNode->next = NULL.
4.​ If front is NULL (Empty Queue):
■​ Set front = rear = newNode.
5.​ Else:
■​ Set rear->next = newNode.
■​ Update rear = newNode.
6.​ Print "INSERTED".
7.​ Stop.
2.​ Dequeue (Deletion):
1.​ Start.
2.​ If front is NULL, print "EMPTY".
3.​ Set temp = front.
4.​ Print front->data as deleted element.
5.​ If front == rear (Only one node):
■​ Set front = rear = NULL.
6.​ Else:
■​ Move front to front->next.
7.​ Free temp.
8.​ Stop.
3.​ Display:
1.​ Start.
2.​ If front is NULL, print "EMPTY".
3.​ Set temp = front.
4.​ While temp is not NULL:
 ■​ Print temp->data.
■​ Move temp to temp->next.
5.​ Stop.

Code:

C
// Linear Queue ( using linked list) and its operations
// Hriddhi Bhattacharyya_10900324160_ECE-2B-130
// DATE: 06.01.2026

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
};

struct Node *front = NULL;

struct Node *rear = NULL;

void enqueue() {
int x;
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
if(newNode == NULL) {
printf("FULL\n");
} else {
printf("ENTER ELEMENT: ");
scanf("%d", &x);
newNode->data = x;
newNode->next = NULL;
if(front == NULL && rear == NULL) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
printf("INSERTED %d\n", x);
}
}

void dequeue() {
struct Node *temp;
if(front == NULL) {
printf("EMPTY\n");
} else {
temp = front;
printf("DELETED %d\n", front->data);
if(front == rear) {
front = rear = NULL;
} else {
front = front->next;
}
 free(temp);
}
}

void display() {
struct Node *temp;
if(front == NULL) {
printf("EMPTY\n");
} else {
temp = front;
printf("QUEUE ");
while(temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}

int main() {
int choice;
do {
printf("\nMENU\n1 INSERT\t2 DELETE\t3 DISPLAY\t4 EXIT\n");
printf("CHOICE: ");
scanf("%d", &choice);
switch (choice) {
case 1: {
enqueue();
break;
}
case 2: {
dequeue();
break;
}
case 3: {
display();
break;
}
case 4: {
printf("EXITTED\n");
break;
}
default: {
printf("INVALID\n");
break;
}
}
} while (choice != 4);
return 0;
}

Output:
Plaintext
MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 1
ENTER ELEMENT: 23
INSERTED 23

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 1
ENTER ELEMENT: 34
INSERTED 34

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 1
ENTER ELEMENT: 45
INSERTED 45

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 2
DELETED 23

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 3
QUEUE 34 45

MENU
1 INSERT 2 DELETE 3 DISPLAY 4 EXIT
CHOICE: 4
EXITTED

Conclusion: The Linear Queue using Linked List efficiently manages data in a FIFO manner. It overcomes the
fixed-size limitation of array-based queues by using dynamic memory allocation. However, unlike the Circular Queue,
the Linear Queue (in array implementation) suffers from memory wastage, but here in Linked List implementation,
memory is allocated and deallocated as needed, making it highly efficient.

—----------------------------------------------------------------------------------------------------------------------------

Experiment: Implementation of Stack using Linked List

Objective:

To implement the Stack data structure using a Linked List to demonstrate the Last-In-First-Out (LIFO) principle with
dynamic memory allocation.

Theory:
A Stack implemented using a Linked List is a linear data structure that follows the LIFO (Last In First Out) principle.
Unlike an array-based stack which has a fixed size, a linked list-based stack can grow and shrink dynamically during
runtime.

In this implementation, the top pointer represents the head of the linked list. All insertions (push) and deletions (pop)
happen at the top end to maintain $O(1)$ time complexity for these operations.

●​ Push: A new node is added before the current head, and top is updated to point to this new node.
●​ Pop: The node pointed to by top is removed, and top is moved to the next node.

Algorithm:

1.​ Push (Insertion):

1.​ Start.
2.​ Allocate memory for newNode. If NULL, print "Stack Overflow".
3.​ Read n (data).
4.​ Set newNode->data = n.
5.​ Set newNode->next = top (Link new node to previous top).
6.​ Set top = newNode (Update top).
7.​ Print "pushed onto stack".
8.​ Stop.
2.​ Pop (Deletion):
1.​ Start.
2.​ If top is NULL, print "Stack Underflow".
3.​ Else:
■​ Set temp = top.
■​ Print top->data as popped element.
■​ Set top = top->next (Move top pointer down).
■​ Free temp (Release memory).
4.​ Stop.
3.​ Peak (Peek/Top):
1.​ Start.
2.​ If top is NULL, print "Stack is empty".
3.​ Else, print top->data.
4.​ Stop.
4.​ Display:
1.​ Start.
2.​ If top is NULL, print "Stack is empty".
3.​ Set temp = top.
4.​ While temp is not NULL:
■​ Print temp->data.
■​ Move temp to temp->next.
5.​ Stop.

Code:

C
// Stack Implementation using Linked List
// Hriddhi Bhattacharyya. 10900324160. 2B-130
// DATE : 06.01.2026

#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};

struct Node *top = NULL;

void push(int n)
{
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL)
printf("Stack Overflow\n");
else {
newNode->data = n;
newNode->next = top;
top = newNode;
printf("%d pushed onto stack\n", n);
}
}

void pop()
{
if (top == NULL)
printf("Stack Underflow\n");
else {
struct Node *temp = top;
printf("%d popped from stack\n", top->data);
top = top->next;
free(temp);
}
}

void peak()
{
if (top == NULL)
printf("Stack is empty\n");
else
printf("Top element is %d\n", top->data);
}

void display()
{
if (top == NULL)
printf("Stack is empty\n");
else {
struct Node *temp = top;
printf("Stack elements ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
}
int main()
{
int choice, n;
printf("Stack Implementation using Linked List\n");
do
{
printf("1 Push 2 Pop 3 Peak 4 Display 5 Exit\n");
printf("Enter your choice ");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter number to push ");
scanf("%d", &n);
push(n);
break;
case 2:
pop();
break;
case 3:
peak();
break;
case 4:
display();
break;
case 5:
printf("Exitted.\n");
break;
default:
printf("Invalid\n");
}
} while (choice != 5);
return 0;
}

Output:

Plaintext
Stack Implementation using Linked List
1 Push 2 Pop 3 Peak 4 Display 5 Exit
Enter your choice 1
Enter number to push 10
10 pushed onto stack

1 Push 2 Pop 3 Peak 4 Display 5 Exit

Enter your choice 1
Enter number to push 20
20 pushed onto stack

1 Push 2 Pop 3 Peak 4 Display 5 Exit

Enter your choice 2
20 popped from stack
1 Push 2 Pop 3 Peak 4 Display 5 Exit
Enter your choice 3
Top element is 10

1 Push 2 Pop 3 Peak 4 Display 5 Exit

Enter your choice 1
Enter number to push 30
30 pushed onto stack

1 Push 2 Pop 3 Peak 4 Display 5 Exit

Enter your choice 4
Stack elements 30 10

1 Push 2 Pop 3 Peak 4 Display 5 Exit

Enter your choice 5
Exitted.

Conclusion:

The Stack data structure was successfully implemented using a Linked List. This approach solves the overflow
problem inherent in fixed-size array stacks (limited only by system memory). The operations push and pop are
efficient with $O(1)$ complexity as they are performed at the head of the list.

—----------------------------------------------------------------------------------------------------------------------------

Experiment: Implementation of Quick Sort

Objective:

To implement the Quick Sort algorithm to arrange a given set of integers in ascending order. The goal is to
understand the Divide and Conquer strategy and the partitioning mechanism.

Theory:

Quick Sort is a highly efficient sorting algorithm and is based on the Divide and Conquer algorithm. It picks an
element as a pivot and partitions the given array around the picked pivot.

●​ Partitioning: The key process in Quick Sort is partition(). The target of partitions is, given an array and an
element x of array as a pivot, put x at its correct position in a sorted array and put all smaller elements
(smaller than x) before x, and put all greater elements (greater than x) after x.
●​ In this implementation, the last element is chosen as the pivot.

Algorithm:

1.​ Partition Function (arr, low, high):

1.​ Set pivot = arr[high].
2.​ Set i = (low - 1) (Index of smaller element).
3.​ Loop j from low to high - 1:
■​ If arr[j] < pivot:
■​ Increment i.
■​ Swap arr[i] and arr[j].
4.​ Swap arr[i + 1] and arr[high] (Place pivot in correct position).
5.​ Return (i + 1).
2.​ Quick Sort Function (arr, low, high):
1.​ If low < high:
 ■​ Find partition index pi = partition(arr, low, high).
■​ Recursively call quickSort(arr, low, pi - 1) (Sort Left side).
■​ Recursively call quickSort(arr, pi + 1, high) (Sort Right side).

Code:

// Quick Sort

// Hriddhi Bhattacharyya_10900324160_ECE-2B-130

// DATE: 18.11.2025

#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);

int main()

int n, i;

printf("ENTER NUMBER OF ELEMENTS: ");

scanf("%d", &n);

int arr[n];

printf("ENTER %d INTEGERS:\n", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

quickSort(arr, 0, n - 1);
 printf("SORTED ARRAY USING QUICK SORT:\n");

for (i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

Output:

Plaintext

ENTER NUMBER OF ELEMENTS: 5

ENTER 5 INTEGERS:

56

34

12

SORTED ARRAY USING QUICK SORT:

6 8 12 34 56

Conclusion:

Quick Sort was successfully implemented. It is observed that Quick Sort is faster in practice than other $O(n \log n)$
algorithms like Merge Sort for smaller datasets because of its efficient cache usage and in-place sorting nature
(requiring only stack space for recursion).

Experiment: Implementation of Insertion Sort

Objective:
To implement the Insertion Sort algorithm to arrange a given set of integers in ascending order. The goal is to
understand how to build a sorted array one item at a time.

Theory:

Insertion Sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The
array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the
correct position in the sorted part.

●​ It is an In-Place sorting algorithm.

●​ It is Stable (does not change the relative order of elements with equal keys).
●​ It is efficient for small data sets or data sets that are already substantially sorted.

Algorithm:

1.​ Start from the second element (index 1) to the last element (index n-1). Let this be i.
2.​ Store the current element: key = arr[i].
3.​ Set j = i - 1.
4.​ While j >= 0 AND arr[j] > key:
○​ Shift element to the right: arr[j + 1] = arr[j].
○​ Decrement j.
5.​ Insert the key at the correct position: arr[j + 1] = key.
6.​ Repeat until the array is sorted.

Code:

// Insertion Sort

// Hriddhi Bhattacharyya_10900324160_ECE-2B-130

// DATE: 18.11.2025

#include <stdio.h>

void insertionSort(int arr[], int n)

int i, key, j;

for (i = 1; i < n; i++)

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key)

 {

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

int main()

int n, i;

printf("ENTER NUMBER OF ELEMENTS: ");

scanf("%d", &n);

int arr[n];

printf("ENTER %d INTEGERS:\n", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

insertionSort(arr, n);

printf("SORTED ARRAY USING INSERTION SORT:\n");

for (i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;
}

Output:

Plaintext

ENTER NUMBER OF ELEMENTS: 5

ENTER 5 INTEGERS:

12

23

34

SORTED ARRAY USING INSERTION SORT:

1 6 12 23 34

Conclusion:

Insertion Sort was successfully implemented. It was observed that while this algorithm has a time complexity of
34$O(n^2)$, making it inefficient for large lists, it performs very well for small lis5ts or lists that are nearly6 sorted, due
to its low overhead.

—----------------------------------------------------------------------------------------------------------------------------

Aha! Asol khela toh ekhon shuru! (The real game starts now!) You want the main course after the starters? Besh,
besh! (Good, good!)

Here are the reports for Merge Sort, Heap Sort, and Selection Sort, formatted exactly as you like. Copy them
quickly, don't keep the file waiting!

Experiment: Implementation of Merge Sort

Objective:

To implement the Merge Sort algorithm to arrange a given set of integers in ascending order. The goal is to
understand the recursive application of the Divide and Conquer strategy.

Theory:
Merge Sort is a stable, divide-and-conquer sorting algorithm. It works by recursively dividing the input array into two
halves until each sub-array contains a single element (which is inherently sorted). Then, it merges these sorted
sub-arrays back together to produce the final sorted array.

●​ Divide: Split the array into two halves.

●​ Conquer: Recursively sort the two halves.
●​ Combine: Merge the two sorted halves into a single sorted array.
●​ Time Complexity: $O(n \log n)$ in all cases.

Algorithm:

1.​ Merge Function (arr, l, m, r):

1.​ Create temporary arrays L and R.
2.​ Copy data to L (left subarray) and R (right subarray).
3.​ Initialize indices i = 0, j = 0, k = l.
4.​ Compare elements of L and R:
■​ If L[i] <= R[j], place L[i] in arr[k], increment i.
■​ Else, place R[j] in arr[k], increment j.
5.​ Copy remaining elements of L or R into arr.
2.​ Merge Sort Function (arr, l, r):
1.​ If l < r:
■​ Calculate middle index m = l + (r - l) / 2.
■​ Call mergeSort(arr, l, m).
■​ Call mergeSort(arr, m + 1, r).
■​ Call merge(arr, l, m, r).

Code:

// Merge Sort

// Hriddhi Bhattacharyya_10900324160_ECE-2B-130

// DATE: 18.11.2025

#include <stdio.h>

void merge(int arr[], int l, int m, int r)

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++)

 L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1 + j];

i = 0;

j = 0;

k = l;

while (i < n1 && j < n2)

if (L[i] <= R[j])

arr[k] = L[i];

i++;

else

arr[k] = R[j];

j++;

k++;

while (i < n1)

arr[k] = L[i];

i++;

k++;

while (j < n2)

 {

arr[k] = R[j];

j++;

k++;

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()

int n, i;

printf("ENTER NUMBER OF ELEMENTS: ");

scanf("%d", &n);

int arr[n];

printf("ENTER %d INTEGERS:\n", n);

for (i = 0; i < n; i++)

{
 scanf("%d", &arr[i]);

mergeSort(arr, 0, n - 1);

printf("SORTED ARRAY USING MERGE SORT:\n");

for (i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

Output:

Plaintext

ENTER NUMBER OF ELEMENTS: 5

ENTER 5 INTEGERS:

78

12

34

90

122

SORTED ARRAY USING MERGE SORT:

12 34 78 90 122

Conclusion:

Merge Sort was implemented successfully. It is highly predictable with a guaranteed time complexity of $O(n \log n)$.
However, unlike Quick Sort, it requires $O(n)$ auxiliary space for the temporary arrays, which can be a drawback for
memory-constrained systems.
Experiment: Implementation of Heap Sort
Objective:

To implement the Heap Sort algorithm to arrange a given set of integers. The goal is to understand the construction
and manipulation of the Binary Heap data structure.

Theory:

Heap Sort is a comparison-based sorting technique based on the Binary Heap data structure. It involves building a
Max-Heap from the input data (where the largest element is at the root) and then repeatedly extracting the maximum
element from the heap and placing it at the end of the sorted array.

●​ Heapify: The process of creating a heap data structure from a binary tree.
●​ It is an In-Place algorithm but is Not Stable.

Algorithm:

1.​ Heapify Function (arr, n, i):

1.​ Initialize largest = i.
2.​ Set left = 2*i + 1 and right = 2*i + 2.
3.​ If left < n and arr[left] > arr[largest], update largest = left.
4.​ If right < n and arr[right] > arr[largest], update largest = right.
5.​ If largest != i:
■​ Swap arr[i] and arr[largest].
■​ Recursively call heapify(arr, n, largest).
2.​ Heap Sort Function (arr, n):
1.​ Build Max Heap: Loop i from n/2 - 1 down to 0, call heapify.
2.​ Extract elements: Loop i from n-1 down to 0.
■​ Swap arr[0] (max) with arr[i].
■​ Call heapify(arr, i, 0) on the reduced heap.

Code:

// Heap Sort

// Hriddhi Bhattacharyya_10900324160_ECE-2B-130

// DATE: 29.11.2025

#include <stdio.h>

void swap(int *a, int *b)

int t = *a;

*a = *b;
 *b = t;

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);
 }

int main()

int n, i;

printf("ENTER NUMBER OF ELEMENTS: ");

scanf("%d", &n);

int arr[n];

printf("ENTER %d INTEGERS:\n", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

heapSort(arr, n);

printf("SORTED ARRAY USING HEAP SORT:\n");

for (i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

Output:

Plaintext

ENTER NUMBER OF ELEMENTS: 4

ENTER 4 INTEGERS:

35

99

23

SORTED ARRAY USING HEAP SORT:

1 23 35 99

Conclusion:

Heap Sort was successfully implemented. It combines the time efficiency of Merge Sort ($O(n \log n)$) with the space
efficiency of Quick Sort ($O(1)$ extra space). It is particularly useful when memory is tight and worst-case
performance guarantees are needed.

Experiment: Implementation of Selection Sort

Objective:

To implement the Selection Sort algorithm to arrange a set of integers. The goal is to understand the concept of
repeatedly finding the minimum element from the unsorted part and putting it at the beginning.

Theory:

Selection Sort is a simple comparison-based sorting algorithm. The list is divided into two parts: the sorted part at the
left end and the unsorted part at the right end.

●​ In every iteration, the minimum element (considering ascending order) from the unsorted subarray is
picked and moved to the sorted subarray.
●​ It performs well on small files but is inefficient for large lists.

Algorithm:

1.​ Loop i from 0 to n-2:

1.​ Assume min_idx = i.
2.​ Loop j from i + 1 to n-1:
■​ If arr[j] < arr[min_idx], update min_idx = j.
3.​ If min_idx != i:
■​ Swap arr[min_idx] and arr[i].
2.​ Stop.

Code:

// Selection Sort
// Hriddhi Bhattacharyya_10900324160_ECE-2B-130

// DATE: 29.11.2025

#include <stdio.h>

void selectionSort(int arr[], int n)

int i, j, min_idx, temp;

for (i = 0; i < n - 1; i++)

min_idx = i;

for (j = i + 1; j < n; j++)

if (arr[j] < arr[min_idx])

min_idx = j;

if (min_idx != i)

temp = arr[min_idx];

arr[min_idx] = arr[i];

arr[i] = temp;

int main()

int n, i;

printf("ENTER NUMBER OF ELEMENTS: ");

scanf("%d", &n);
 int arr[n];

printf("ENTER %d INTEGERS:\n", n);

for (i = 0; i < n; i++)

scanf("%d", &arr[i]);

selectionSort(arr, n);

printf("SORTED ARRAY USING SELECTION SORT:\n");

for (i = 0; i < n; i++)

printf("%d ", arr[i]);

printf("\n");

return 0;

Output:

Plaintext

ENTER NUMBER OF ELEMENTS: 5

ENTER 5 INTEGERS:

88

23

90

12

102

SORTED ARRAY USING SELECTION SORT:

12 23 88 90 102
Conclusion:

Selection Sort was successfully implemented. While it has a high time complexity of $O(n^2)$, it has the property of
making the minimum number of swaps (at most $n-1$), which can be advantageous when the cost of writing to
memory is high.