1. Write a C++ program to implement the following using an array a) Stack ADT b) Queue ADT.
a)
#include <stdio.h>
#define MAX 100 // Maximum size of the stack
// Stack structure
typedef struct {
int data[MAX];
int top;
} Stack;
// Function to initialize the stack
void initializeStack(Stack *stack) {
stack->top = -1;
// Function to check if the stack is empty
int isEmpty(Stack *stack) {
return stack->top == -1;
// Function to check if the stack is full
int isFull(Stack *stack) {
return stack->top == MAX - 1;
// Function to push an element into the stack
void push(Stack *stack, int value) {
if (isFull(stack)) {
printf("Stack overflow!\n");
} else {
stack->data[++stack->top] = value;
printf("%d pushed into the stack.\n", value);
// Function to pop an element from the stack
int pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack underflow!\n");
return -1;
} else {
return stack->data[stack->top--];
}
// Function to display the stack elements
void display(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
} else {
printf("Stack elements: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
printf("\n");
int main() {
Stack stack;
initializeStack(&stack);
int choice, value;
while (1) {
printf("\nStack Operations:\n");
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter a value to push: ");
scanf("%d", &value);
push(&stack, value);
break;
case 2:
value = pop(&stack);
if (value != -1) {
printf("Popped value: %d\n", value);
break;
case 3:
display(&stack);
break;
case 4:
printf("Exiting...\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");
}
}
Output:
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter a value to push: 2
2 pushed into the stack.
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack elements: 2
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter a value to push: 4
4 pushed into the stack.
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack elements: 2 4
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
Popped value: 4
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack elements: 2
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 4
Exiting...
b)
#include <stdio.h>
#define MAX 100
// Define the Queue structure
typedef struct {
int data[MAX]; // Array to store queue elements
int front; // Index of the front element
int rear; // Index of the rear element
} Queue;
// Initialize the queue
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
// Check if the queue is empty
int isEmpty(Queue *q) {
return q->front == -1;
// Check if the queue is full
int isFull(Queue *q) {
return q->rear == MAX - 1;
// Enqueue operation: Add an element to the rear of the queue
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full! Cannot enqueue %d.\n", value);
return;
if (isEmpty(q)) {
q->front = 0; // Set front to 0 if the queue was empty
q->rear++;
q->data[q->rear] = value;
printf("Enqueued %d to the queue.\n", value);
}
// Dequeue operation: Remove an element from the front of the queue
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty! Cannot dequeue.\n");
return -1; // Return -1 to indicate an error
int value = q->data[q->front];
if (q->front == q->rear) {
// If there was only one element, reset the queue
q->front = -1;
q->rear = -1;
} else {
q->front++;
printf("Dequeued %d from the queue.\n", value);
return value;
// Display the elements of the queue
void display(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return;
printf("Queue elements: ");
for (int i = q->front; i <= q->rear; i++) {
printf("%d ", q->data[i]);
printf("\n");
int main() {
Queue q;
initQueue(&q);
int choice, value;
while (1) {
printf("\nQueue Operations:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter a value to enqueue: ");
scanf("%d", &value);
enqueue(&q, value);
break;
case 2:
dequeue(&q);
break;
case 3:
display(&q);
break;
case 4:
printf("Exiting...\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");
Output:
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 1
Enter a value to enqueue: 23
Enqueued 23 to the queue.
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue elements: 23
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 2
Dequeued 23 from the queue.
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue is empty!
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
Enter your choice: 3
Queue is empty!
Queue Operations:
1. Enqueue
2. Dequeue
3. Display
4. Exit
2. Write a C++ program to implement the following using a singly linked list a. Stack ADT b. Queue ADT.
a)
#include <stdio.h>
#include <stdlib.h>
// Define the Node structure
typedef struct Node {
int data;
struct Node *next;
} Node;
// Define the Stack structure
typedef struct {
Node *top;
} Stack;
// Initialize the stack
void initStack(Stack *s) {
s->top = NULL;
// Check if the stack is empty
int isEmpty(Stack *s) {
return s->top == NULL;
// Push operation: Add an element to the top of the stack
void push(Stack *s, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = s->top;
s->top = newNode;
printf("Pushed %d onto the stack.\n", value);
// Pop operation: Remove and return the top element of the stack
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty! Cannot pop.\n");
return -1; // Return -1 to indicate an error
Node *temp = s->top;
int value = temp->data;
s->top = s->top->next;
free(temp);
printf("Popped %d from the stack.\n", value);
return value;
// Display the elements of the stack
void display(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return;
printf("Stack elements: ");
Node *current = s->top;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
printf("\n");
int main() {
Stack s;
initStack(&s);
int choice, value;
while (1) {
printf("\nStack Operations:\n");
printf("1. Push\n");
printf("2. Pop\n");
printf("3. Display\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter a value to push: ");
scanf("%d", &value);
push(&s, value);
break;
case 2:
pop(&s);
break;
case 3:
display(&s);
break;
case 4:
printf("Exiting...\n");
return 0;
default:
printf("Invalid choice! Please try again.\n");
Output:
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter a value to push: 40
Pushed 40 onto the stack.
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack elements: 40
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
Popped 40 from the stack.
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack is empty!
Stack Operations:
1. Push
2. Pop
3. Display
4. Exit
b)
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
// Queue structure
struct Queue {
struct Node* front;
struct Node* rear;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
// Function to initialize a queue
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
// Enqueue operation
void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);
if (queue->rear == NULL) { // Queue is empty
queue->front = queue->rear = newNode;
printf("%d added to the queue.\n", data);
return;
queue->rear->next = newNode;
queue->rear = newNode;
printf("%d added to the queue.\n", data);
// Dequeue operation
int dequeue(struct Queue* queue) {
if (queue->front == NULL) { // Queue is empty
printf("Queue is empty. Nothing to dequeue.\n");
return -1;
struct Node* temp = queue->front;
int data = temp->data;
queue->front = queue->front->next;
// If the queue becomes empty
if (queue->front == NULL) {
queue->rear = NULL;
free(temp);
printf("%d removed from the queue.\n", data);
return data;
// Display the queue
void displayQueue(struct Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty.\n");
return;
struct Node* temp = queue->front;
printf("Queue: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
printf("\n");
// Main function
int main() {
struct Queue* queue = createQueue();
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
displayQueue(queue);
dequeue(queue);
dequeue(queue);
displayQueue(queue);
dequeue(queue);
dequeue(queue); // Trying to dequeue from an empty queue
return 0;
Output:
10 added to the queue.
20 added to the queue.
30 added to the queue.
Queue: 10 20 30
10 removed from the queue.
20 removed from the queue.
Queue: 30
30 removed from the queue.
Queue is empty. Nothing to dequeue.
3. Write C Program to implement the DEQUE (double ended queue) ADT using arrays.
#include <stdio.h>
#define MAX 10
typedef struct {
int data[MAX];
int front, rear;
} Deque;
// Initialize the deque
void initializeDeque(Deque *dq) {
dq->front = -1;
dq->rear = -1;
// Check if the deque is empty
int isEmpty(Deque *dq) {
return (dq->front == -1);
}
// Check if the deque is full
int isFull(Deque *dq) {
return ((dq->front == 0 && dq->rear == MAX - 1) || (dq->rear + 1 == dq->front));
// Insert at the front
void insertFront(Deque *dq, int value) {
if (isFull(dq)) {
printf("Deque is full. Cannot insert at the front.\n");
return;
if (isEmpty(dq)) {
dq->front = dq->rear = 0;
} else if (dq->front == 0) {
dq->front = MAX - 1;
} else {
dq->front--;
dq->data[dq->front] = value;
printf("Inserted %d at the front.\n", value);
// Insert at the rear
void insertRear(Deque *dq, int value) {
if (isFull(dq)) {
printf("Deque is full. Cannot insert at the rear.\n");
return;
if (isEmpty(dq)) {
dq->front = dq->rear = 0;
} else if (dq->rear == MAX - 1) {
dq->rear = 0;
} else {
dq->rear++;
dq->data[dq->rear] = value;
printf("Inserted %d at the rear.\n", value);
// Delete from the front
void deleteFront(Deque *dq) {
if (isEmpty(dq)) {
printf("Deque is empty. Cannot delete from the front.\n");
return;
}
printf("Deleted %d from the front.\n", dq->data[dq->front]);
if (dq->front == dq->rear) {
dq->front = dq->rear = -1;
} else if (dq->front == MAX - 1) {
dq->front = 0;
} else {
dq->front++;
// Delete from the rear
void deleteRear(Deque *dq) {
if (isEmpty(dq)) {
printf("Deque is empty. Cannot delete from the rear.\n");
return;
printf("Deleted %d from the rear.\n", dq->data[dq->rear]);
if (dq->front == dq->rear) {
dq->front = dq->rear = -1;
} else if (dq->rear == 0) {
dq->rear = MAX - 1;
} else {
dq->rear--;
// Display the deque
void displayDeque(Deque *dq) {
if (isEmpty(dq)) {
printf("Deque is empty.\n");
return;
printf("Deque elements: ");
int i = dq->front;
while (1) {
printf("%d ", dq->data[i]);
if (i == dq->rear) break;
i = (i + 1) % MAX;
printf("\n");
int main() {
Deque dq;
initializeDeque(&dq);
insertRear(&dq, 10);
insertRear(&dq, 20);
displayDeque(&dq);
insertFront(&dq, 5);
displayDeque(&dq);
deleteFront(&dq);
displayDeque(&dq);
deleteRear(&dq);
displayDeque(&dq);
return 0;
Output:
Inserted 10 at the rear.
Inserted 20 at the rear.
Deque elements: 10 20
Inserted 5 at the front.
Deque elements: 5 10 20
Deleted 5 from the front.
Deque elements: 10 20
Deleted 20 from the rear.
Deque elements: 10
4. Write a C program to perform the following operations: a) Insert an element into a binary search tree. b) Delete an element from a binary search tree.
#include <stdio.h>
#include <stdlib.h>
// Define a node of the binary search tree
struct Node {
int data;
struct Node *left, *right;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
// Function to insert an element into the BST
struct Node* insert(struct Node* root, int value) {
if (root == NULL) {
return createNode(value); // Create a new node if tree is empty
}
if (value < root->data) {
root->left = insert(root->left, value); // Insert in the left subtree
} else if (value > root->data) {
root->right = insert(root->right, value); // Insert in the right subtree
return root; // Return the unchanged root
// Function to find the minimum value node in the tree
struct Node* findMin(struct Node* root) {
while (root->left != NULL) {
root = root->left;
return root;
// Function to delete an element from the BST
struct Node* deleteNode(struct Node* root, int value) {
if (root == NULL) {
return root; // Return NULL if the tree is empty
// Traverse the tree to find the node to delete
if (value < root->data) {
root->left = deleteNode(root->left, value);
} else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
// Node to be deleted found
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
// Node with two children: get the inorder successor (smallest in the right subtree)
struct Node* temp = findMin(root->right);
root->data = temp->data; // Copy the inorder successor's value
root->right = deleteNode(root->right, temp->data); // Delete the inorder successor
return root;
}
// Function to perform inorder traversal of the tree
void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
int main() {
struct Node* root = NULL;
int choice, value;
printf("Binary Search Tree Operations:\n");
printf("1. Insert\n2. Delete\n3. Display (Inorder Traversal)\n4. Exit\n");
while (1) {
printf("\nEnter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Enter the value to delete: ");
scanf("%d", &value);
root = deleteNode(root, value);
break;
case 3:
printf("Inorder Traversal: ");
inorder(root);
printf("\n");
break;
case 4:
printf("Exiting program.\n");
exit(0);
default:
printf("Invalid choice. Please try again.\n");
}
return 0;
Output:
Binary Search Tree Operations:
1. Insert
2. Delete
3. Display (Inorder Traversal)
4. Exit
Enter your choice: 1
Enter the value to insert: 12
Enter your choice: 1
Enter the value to insert: 15
Enter your choice: 1
Enter the value to insert: 13
Enter your choice: 3
Inorder Traversal: 12 13 15
Enter your choice: 2
Enter the value to delete: 12
Enter your choice: 3
Inorder Traversal: 13 15
Enter your choice: 4
Exiting program.
5. Write a C program that use recursive functions to traverse the given binary tree in a) Preorder b) Inorder and c) Postorder.
#include <stdio.h>
#include <stdlib.h>
// Definition for a binary tree node
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// Helper function to create a new tree node
struct TreeNode* newTreeNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
// Preorder traversal: Root, Left, Right
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
// Inorder traversal: Left, Root, Right
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
// Postorder traversal: Left, Right, Root
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
// Main function to test the traversals
int main() {
// Create a sample tree:
// 1
// / \
// 2 3
// / \
// 4 5
struct TreeNode* root = newTreeNode(1);
root->left = newTreeNode(2);
root->right = newTreeNode(3);
root->left->left = newTreeNode(4);
root->left->right = newTreeNode(5);
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
printf("Postorder traversal: ");
postorderTraversal(root);
printf("\n");
return 0;
Output:
Preorder traversal: 1 2 4 5 3
Inorder traversal: 4 2 5 1 3
Postorder traversal: 4 5 2 3 1
6. Write a C program for linear search and binary search.
L.S
#include <stdio.h>
// Function for linear search
int linearSearch(int arr[], int size, int target) {
for(int i = 0; i < size; i++) {
if(arr[i] == target) {
return i; // Return the index if the target is found
return -1; // Return -1 if the target is not found
int main() {
int arr[] = {5, 3, 8, 6, 2, 10, 7};
int size = sizeof(arr) / sizeof(arr[0]);
int target = 6;
int result = linearSearch(arr, size, target);
if(result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
return 0;
B.S
#include <stdio.h>
// Function for binary search
int binarySearch(int arr[], int size, int target) {
int left = 0, right = size - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
// Check if target is present at mid
if(arr[mid] == target) {
return mid; // Return the index if the target is found
// If target is greater, ignore the left half
if(arr[mid] < target) {
left = mid + 1;
} else {
// If target is smaller, ignore the right half
right = mid - 1;
return -1; // Return -1 if the target is not found
int main() {
int arr[] = {2, 3, 5, 6, 7, 8, 10}; // Sorted array for binary search
int size = sizeof(arr) / sizeof(arr[0]);
int target = 6;
int result = binarySearch(arr, size, target);
if(result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
return 0;
Output:
Element found at index 3
7. Write C programs for the implementation of BFS and DFS for a given graph.
#include <stdio.h>
#include <stdlib.h>
// Structure for the adjacency list node
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Structure for the adjacency list
struct AdjList {
struct AdjListNode *head;
};
// Structure for the graph
struct Graph {
int V;
struct AdjList* array;
};
// Create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
// Create a graph with V vertices
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i) {
graph->array[i].head = NULL;
return graph;
// Add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
// BFS traversal from a given source
void BFS(struct Graph* graph, int startVertex) {
int *visited = (int*) malloc(graph->V * sizeof(int));
for (int i = 0; i < graph->V; i++)
visited[i] = 0;
int queue[graph->V];
int front = 0, rear = 0;
visited[startVertex] = 1;
queue[rear++] = startVertex;
while (front < rear) {
int currentVertex = queue[front++];
printf("%d ", currentVertex);
struct AdjListNode* adjList = graph->array[currentVertex].head;
while (adjList) {
int adjVertex = adjList->dest;
if (!visited[adjVertex]) {
queue[rear++] = adjVertex;
visited[adjVertex] = 1;
adjList = adjList->next;
free(visited);
// DFS traversal from a given source
void DFSUtil(struct Graph* graph, int vertex, int *visited) {
visited[vertex] = 1;
printf("%d ", vertex);
struct AdjListNode* adjList = graph->array[vertex].head;
while (adjList) {
int adjVertex = adjList->dest;
if (!visited[adjVertex]) {
DFSUtil(graph, adjVertex, visited);
adjList = adjList->next;
void DFS(struct Graph* graph, int startVertex) {
int *visited = (int*) malloc(graph->V * sizeof(int));
for (int i = 0; i < graph->V; i++)
visited[i] = 0;
DFSUtil(graph, startVertex, visited);
free(visited);
int main() {
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printf("Breadth-First Search starting from vertex 0:\n");
BFS(graph, 0);
printf("\n");
printf("Depth-First Search starting from vertex 0:\n");
DFS(graph, 0);
printf("\n");
return 0;
Output:
Breadth-First Search starting from vertex 0:
04132
Depth-First Search starting from vertex 0:
04321
8. Write C programs for implementing the following sorting methods: a) Merge Sort b) Heap Sort
a)
#include <stdio.h>
// Function to merge two subarrays
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
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++;
// Function to implement merge sort
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
b)
#include <stdio.h>
// Function to heapify a subtree rooted at node i
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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
// Function to implement heap sort
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);
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, n);
heapSort(arr, n);
printf("\nSorted array is \n");
printArray(arr, n);
return 0;
Output:
Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13
9. Write a C program to perform the following operations. a) Insertion into a B-tree b) Deletion from a B-tree.
a)
b)
10. Write a C program to implement quick sort
#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
// Partition function
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;
// Quick Sort function
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);
// Function to print the array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: \n");
printArray(arr, n);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
Output:
Unsorted array:
10 7 8 9 1 5
Sorted array:
1 5 7 8 9 10
