23UCA03
S.NO DATE CONTENT PAGE SIGN
NO
1. Write a program to implement the List ADT using arrays and
linked lists.
2. Write a programs to implement the following using a singly
linked list.
(a)Stack ADT
(b)Queue ADT
3. Write a program that reads an infix expression, converts the
expression to postfix form and then evaluates the postfix
expression (use stack ADT).
4. Write a program to implement priority queue ADT
5. Write a program to perform the following operations:
Insert ,Delete,Search.
6. Write a program to perform the following operations:
1.Insertion into an AVL-tree
2. Deletion from an AVL-tree
7. Write a programs for the implementation of BFS and DFS for a
given graph.
8. Write a programs for implementing the following searching
methods
(a) Linear search
(b) Binary search
9. Write a programs for implementing the following sorting
methods:
(a) Bubble sort
(b)Selection sort
(c) Insertion sort
(d) Radix sort
PROGRAM :1(a)
#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
class ArrayList {
private:
int arr[MAX_SIZE];
int size;
public:
ArrayList() : size(0) {}
void insert(int value) {
if (size < MAX_SIZE) {
arr[size++] = value;
} else {
cout << "Array List is full!" << endl;
void remove(int value) {
for (int i = 0; i < size; i++) {
if (arr[i] == value) {
for (int j = i; j < size - 1; j++) {
arr[j] = arr[j + 1];
size--;
return;
cout << "Value not found in Array List!" << endl;
void display() const {
if (size == 0) {
cout << "Array List is empty!" << endl;
return;
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
cout << endl;
};
int main() {
ArrayList arrayList;
arrayList.insert(10);
arrayList.insert(20);
arrayList.insert(30);
cout << "Initial Array List: ";
arrayList.display();
arrayList.remove(20);
cout << "After removing 20: ";
arrayList.display();
arrayList.remove(40); // Attempting to remove a non-existent value
return 0;
}
OUTPUT:
Initial Array List: 10 20 30
After removing 20: 10 30
Value not found in Array List!
PROGRAM:1(b)
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
void insert(int value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
temp->next = newNode;
void remove(int value) {
if (!head) return;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
Node* current = head;
while (current->next && current->next->data != value) {
current = current->next;
if (current->next) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
} else {
cout << "Value not found in Linked List!" << endl;
void display() const {
Node* temp = head;
if (!temp) {
cout << "Linked List is empty!" << endl;
return;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
cout << endl;
~LinkedList() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
};
int main() {
LinkedList linkedList;
linkedList.insert(10);
linkedList.insert(20);
linkedList.insert(30);
cout << "Initial Linked List: ";
linkedList.display();
linkedList.remove(20);
cout << "After removing 20: ";
linkedList.display();
linkedList.remove(40); // Attempting to remove a non-existent value
return 0;
}
OUTPUT:
Initial Linked List: 10 20 30
After removing 20: 10 30
Value not found in Linked List!
PROGRAM:2(a)
#include <iostream>
using namespace std;
// Node structure for singly linked list
struct Node {
int data;
Node* next;
};
// Stack class using linked list
class Stack {
private:
Node* top;
public:
Stack() {
top = nullptr;
// Push operation
void push(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = top;
top = newNode;
cout << value << " pushed to stack\n";
// Pop operation
void pop() {
if (top == nullptr) {
cout << "Stack is empty\n";
return;
}
Node* temp = top;
top = top->next;
cout << "Popped element: " << temp->data << endl;
delete temp;
// Peek operation
int peek() {
if (top != nullptr) {
return top->data;
} else {
cout << "Stack is empty\n";
return -1;
// Check if stack is empty
bool isEmpty() {
return top == nullptr;
// Display the stack
void display() {
Node* temp = top;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
cout << "NULL\n";
};
// Main function for stack
int main() {
Stack stack;
stack.push(10);
stack.push(20);
stack.push(30);
stack.display();
cout << "Top element: " << stack.peek() << endl;
stack.pop();
stack.display();
return 0;
}
OUTPUT:
10 pushed to stack
20 pushed to stack
30 pushed to stack
30 -> 20 -> 10 -> NULL
Top element: 30
Popped element: 30
20 -> 10 -> NULL
PROGRAM:2(b)
#include <iostream>
using namespace std;
// Node structure for singly linked list
struct Node {
int data;
Node* next;
};
// Queue class using linked list
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = nullptr;
rear = nullptr;
// Enqueue operation
void enqueue(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->next = nullptr;
if (rear == nullptr) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
cout << value << " enqueued to queue\n";
}
// Dequeue operation
void dequeue() {
if (front == nullptr) {
cout << "Queue is empty\n";
return;
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
cout << "Dequeued element: " << temp->data << endl;
delete temp;
// Peek operation
int peek() {
if (front != nullptr) {
return front->data;
} else {
cout << "Queue is empty\n";
return -1;
// Check if queue is empty
bool isEmpty() {
return front == nullptr;
// Display the queue
void display() {
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " -> ";
temp = temp->next;
cout << "NULL\n";
};
// Main function for queue
int main() {
Queue queue;
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.display();
cout << "Front element: " << queue.peek() << endl;
queue.dequeue();
queue.display();
return 0;
}
OUTPUT:
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
10 -> 20 -> 30 -> NULL
Front element: 10
Dequeued element: 10
20 -> 30 -> NULL
PROGRAM:3
#include <iostream>
#include <stack>
#include <string>
#include <cctype> // for isdigit()
using namespace std;
// Function to determine precedence of operators
int precedence(char op) {
if (op == '+' || op == '-')
return 1;
if (op == '*' || op == '/')
return 2;
return 0;
// Function to perform arithmetic operations
int applyOperation(int a, int b, char op) {
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
return 0;
// Function to convert infix expression to postfix
string infixToPostfix(string exp) {
stack<char> s;
string postfix;
for (char ch : exp) {
// If the character is an operand, add it to postfix string
if (isdigit(ch)) {
postfix += ch;
// If the character is '(', push it to the stack
else if (ch == '(') {
s.push(ch);
// If the character is ')', pop and append until '(' is found
else if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix += s.top();
s.pop();
s.pop(); // Pop '('
// If an operator is encountered
else {
while (!s.empty() && precedence(s.top()) >= precedence(ch)) {
postfix += s.top();
s.pop();
s.push(ch);
// Pop all the operators from the stack
while (!s.empty()) {
postfix += s.top();
s.pop();
return postfix;
}
// Function to evaluate postfix expression
int evaluatePostfix(string postfix) {
stack<int> s;
for (char ch : postfix) {
// If the character is an operand, push it to the stack
if (isdigit(ch)) {
s.push(ch - '0'); // Convert char to int
// If the character is an operator, pop two elements and apply the operation
else {
int val2 = s.top(); s.pop();
int val1 = s.top(); s.pop();
int result = applyOperation(val1, val2, ch);
s.push(result);
return s.top(); // The result will be the last element in the stack
int main() {
string infixExp;
// Taking input from user
cout << "Enter an infix expression (single-digit operands only): ";
cin >> infixExp;
// Convert infix to postfix
string postfixExp = infixToPostfix(infixExp);
cout << "Postfix expression: " << postfixExp << endl;
// Evaluate the postfix expression
int result = evaluatePostfix(postfixExp);
cout << "Evaluation result: " << result << endl;
return 0;
}
OUTPUT:
Enter an infix expression (single-digit operands only): 2+3*4
Postfix expression: 234*+
Evaluation result: 14
PROGRAM:4
#include <iostream>
#include <vector>
using namespace std;
// Class representing a Priority Queue using Max-Heap
class PriorityQueue {
private:
vector<int> heap;
// Helper function to maintain heap order (bottom to top)
void heapifyUp(int index) {
if (index == 0) return; // Base case: root element
int parentIndex = (index - 1) / 2;
if (heap[index] > heap[parentIndex]) {
swap(heap[index], heap[parentIndex]);
heapifyUp(parentIndex); // Recursively fix the parent node
// Helper function to maintain heap order (top to bottom)
void heapifyDown(int index) {
int largest = index;
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
if (leftChild < heap.size() && heap[leftChild] > heap[largest]) {
largest = leftChild;
if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
largest = rightChild;
if (largest != index) {
swap(heap[index], heap[largest]);
heapifyDown(largest); // Recursively fix the subtree
}
public:
// Insert an element into the priority queue
void enqueue(int value) {
heap.push_back(value); // Insert at the end
heapifyUp(heap.size() - 1); // Fix the heap order
cout << "Inserted " << value << " into the priority queue.\n";
// Remove and return the element with the highest priority
int dequeue() {
if (heap.empty()) {
cout << "Priority queue is empty!\n";
return -1;
int topElement = heap[0];
heap[0] = heap.back(); // Replace root with last element
heap.pop_back();
heapifyDown(0); // Fix the heap order
cout << "Removed " << topElement << " from the priority queue.\n";
return topElement;
// Peek the element with the highest priority
int peek() {
if (heap.empty()) {
cout << "Priority queue is empty!\n";
return -1;
return heap[0];
// Check if the priority queue is empty
bool isEmpty() {
return heap.empty();
// Display the priority queue
void display() {
if (heap.empty()) {
cout << "Priority queue is empty!\n";
return;
cout << "Priority Queue: ";
for (int i : heap) {
cout << i << " ";
cout << endl;
};
// Main function to demonstrate the priority queue
int main() {
PriorityQueue pq;
pq.enqueue(10);
pq.enqueue(20);
pq.enqueue(5);
pq.enqueue(30);
pq.display();
cout << "Highest priority element (peek): " << pq.peek() << endl;
pq.dequeue();
pq.display();
return 0;
}
OUTPUT:
Inserted 10 into the priority queue.
Inserted 20 into the priority queue.
Inserted 5 into the priority queue.
Inserted 30 into the priority queue.
Priority Queue: 30 20 5 10
Highest priority element (peek): 30
Removed 30 from the priority queue.
Priority Queue: 20 10 5
PROGRAM:5
#include <iostream>
using namespace std;
// Definition of a tree node
struct Node {
int data;
Node* left;
Node* right;
};
// Function to create a new node
Node* createNode(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->left = newNode->right = nullptr;
return newNode;
// Function to insert an element into the BST
Node* insert(Node* root, int value) {
if (root == nullptr) {
return createNode(value);
if (value < root->data) {
root->left = insert(root->left, value);
} else {
root->right = insert(root->right, value);
return root;
// Function to search for a key in the BST
bool search(Node* root, int key) {
if (root == nullptr) {
return false;
if (root->data == key) {
return true;
} else if (key < root->data) {
return search(root->left, key);
} else {
return search(root->right, key);
// Function to find the minimum value node in the right subtree
Node* findMin(Node* root) {
while (root && root->left != nullptr) {
root = root->left;
return root;
// Function to delete an element from the BST
Node* deleteNode(Node* root, int value) {
if (root == nullptr) {
return root;
if (value < root->data) {
root->left = deleteNode(root->left, value);
} else if (value > root->data) {
root->right = deleteNode(root->right, value);
} else {
// Node with only one child or no child
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
// Node with two children
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
return root;
// In-order traversal (to print the tree)
void inorder(Node* root) {
if (root == nullptr) {
return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
int main() {
Node* root = nullptr;
// Insert elements into the BST
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);
cout << "Inorder traversal of the BST: ";
inorder(root);
cout << endl;
// Search for a key
int key = 40;
if (search(root, key)) {
cout << key << " found in the BST\n";
} else {
cout << key << " not found in the BST\n";
// Delete an element from the BST
cout << "Deleting 20 from the BST\n";
root = deleteNode(root, 20);
cout << "Inorder traversal after deletion: ";
inorder(root);
cout << endl;
return 0;
}
OUTPUT:
Inorder traversal of the BST: 20 30 40 50 60 70 80
40 found in the BST
Deleting 20 from the BST
Inorder traversal after deletion: 30 40 50 60 70 80
PROGRAM:6
#include <iostream>
using namespace std;
// Node structure for AVL Tree
struct Node {
int key;
Node* left;
Node* right;
int height;
};
// Function to get the height of the tree
int height(Node* N) {
if (N == nullptr)
return 0;
return N->height;
// Function to create a new node
Node* newNode(int key) {
Node* node = new Node();
node->key = key;
node->left = nullptr;
node->right = nullptr;
node->height = 1; // New node is initially added at leaf
return node;
// Function to perform right rotation
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// Return new root
return x;
// Function to perform left rotation
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// Return new root
return y;
// Get the balance factor of node N
int getBalance(Node* N) {
if (N == nullptr)
return 0;
return height(N->left) - height(N->right);
// Insertion function
Node* insert(Node* node, int key) {
// Step 1: Perform normal BST insertion
if (node == nullptr)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Duplicate keys not allowed
return node;
// Step 2: Update the height of the ancestor node
node->height = 1 + max(height(node->left), height(node->right));
// Step 3: Get the balance factor
int balance = getBalance(node);
// Step 4: Balance the tree
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
// Right Left Case
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
// Return the unchanged node pointer
return node;
}
// Function to find the node with minimum value
Node* minValueNode(Node* node) {
Node* current = node;
// Loop down to find the leftmost leaf
while (current->left != nullptr)
current = current->left;
return current;
// Function to delete a node from the AVL tree
Node* deleteNode(Node* root, int key) {
// Step 1: Perform standard BST deletion
if (root == nullptr)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// Node with one child or no child
if ((root->left == nullptr) || (root->right == nullptr)) {
Node* temp = root->left ? root->left : root->right;
// No child case
if (temp == nullptr) {
temp = root;
root = nullptr;
} else // One child case
*root = *temp; // Copy the contents of the non-empty child
delete temp;
} else {
// Node with two children: Get the inorder successor
Node* temp = minValueNode(root->right);
// Copy the inorder successor's data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
// If the tree had only one node
if (root == nullptr)
return root;
// Step 2: Update height
root->height = 1 + max(height(root->left), height(root->right));
// Step 3: Get balance factor
int balance = getBalance(root);
// Step 4: Balance the tree
// Left Left Case
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
// Right Right Case
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
// In-order traversal of the tree
void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
int main() {
Node* root = nullptr;
// Insert elements into the AVL tree
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
// Display in-order traversal
cout << "In-order traversal of the AVL tree: ";
inorder(root);
cout << endl;
// Delete a node from the AVL tree
root = deleteNode(root, 30);
// Display in-order traversal after deletion
cout << "In-order traversal after deletion of 30: ";
inorder(root);
cout << endl;
return 0;
}
OUTPUT:
In-order traversal of the AVL tree: 10 20 25 30 40 50
In-order traversal after deletion of 30: 10 20 25 40 50
PROGRAM:7
#include <iostream>
#include <list>
#include <queue>
#include <stack>
using namespace std;
class Graph {
int V; // Number of vertices
list<int> *adj; // Pointer to adjacency list
public:
// Constructor
Graph(int V);
// Function to add an edge to the graph
void addEdge(int v, int w);
// BFS traversal
void BFS(int start);
// DFS traversal
void DFS(int start);
// Helper function for DFS (recursive)
void DFSUtil(int v, bool visited[]);
};
// Constructor
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
// Add an edge to the graph
void Graph::addEdge(int v, int w) {
adj[v].push_back(w); // Add w to v's list
// BFS implementation
void Graph::BFS(int start) {
// Initially mark all vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
queue<int> q;
// Mark the current node as visited and enqueue it
visited[start] = true;
q.push(start);
while (!q.empty()) {
// Dequeue a vertex and print it
int v = q.front();
cout << v << " ";
q.pop();
// Get all adjacent vertices of the dequeued vertex
// If an adjacent vertex hasn't been visited, mark it visited and enqueue it
for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
q.push(*i);
delete[] visited;
// Helper function for DFS (recursive)
void Graph::DFSUtil(int v, bool visited[]) {
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all adjacent vertices
for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
if (!visited[*i]) {
DFSUtil(*i, visited);
// DFS implementation
void Graph::DFS(int start) {
// Initially mark all vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
DFSUtil(start, visited);
delete[] visited;
// Main function
int main() {
// Create a graph given in the above diagram
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.addEdge(4, 5);
cout << "BFS starting from vertex 0: ";
g.BFS(0);
cout << "\nDFS starting from vertex 0: ";
g.DFS(0);
return 0;
}
OUTPUT:
BFS starting from vertex 0: 0 1 2 3 4 5
DFS starting from vertex 0: 0 1 3 4 5 2
PROGRAM:8(a)
#include <iostream>
using namespace std;
// Function to perform linear search
int linearSearch(int arr[], int size, int key) {
for (int i = 0; i < size; i++) {
if (arr[i] == key) {
return i; // Return the index where the key is found
return -1; // Return -1 if the key is not found
int main() {
int n, key;
// Input array size
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[n];
// Input array elements
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
// Input the key to search
cout << "Enter the element to search for: ";
cin >> key;
// Perform linear search
int result = linearSearch(arr, n, key);
// Output the result
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
}
return 0;
}
OUTPUT:
Enter the number of elements in the array: 5
Enter the elements of the array: 10 20 30 40 50
Enter the element to search for: 30
Element found at index 2
PROGRAM:8(b)
#include <iostream>
using namespace std;
// Function to perform binary search
int binarySearch(int arr[], int size, int key) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Calculate the mid-point
// Check if the key is at the middle
if (arr[mid] == key)
return mid;
// If the key is smaller, ignore the right half
if (arr[mid] > key)
right = mid - 1;
// If the key is larger, ignore the left half
else
left = mid + 1;
return -1; // Return -1 if the key is not found
int main() {
int n, key;
// Input array size
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[n];
// Input array elements (must be sorted)
cout << "Enter the elements of the sorted array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
// Input the key to search
cout << "Enter the element to search for: ";
cin >> key;
// Perform binary search
int result = binarySearch(arr, n, key);
// Output the result
if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
return 0;
}
OUTPUT:
Enter the number of elements in the array: 6
Enter the elements of the sorted array: 10 20 30 40 50 60
Enter the element to search for: 40
Element found at index 3
PROGRAM:9(a)
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
for (int j = 0; j < size - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int size = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, size);
cout << "Sorted array using Bubble Sort: ";
printArray(arr, size);
return 0;
}
OUTPUT:
Sorted array using Bubble Sort: 11 12 22 25 34 64 90
PROGRAM:9(b)
#include <iostream>
using namespace std;
void selectionSort(int arr[], int size) {
for (int i = 0; i < size - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < size; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
swap(arr[minIdx], arr[i]);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int size = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, size);
cout << "Sorted array using Selection Sort: ";
printArray(arr, size);
return 0;
}
OUTPUT:
Sorted array using Selection Sort: 11 12 22 25 64
PROGRAM:9(c)
#include <iostream>
using namespace std;
// Function to perform insertion sort
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = key; // Insert the key at its correct position
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
int main() {
int n;
// Input array size
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[n];
// Input array elements
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
// Perform insertion sort
insertionSort(arr, n);
// Output sorted array
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
OUTPUT:
Enter the number of elements in the array: 5
Enter the elements of the array: 64 25 12 22 11
Sorted array: 11 12 22 25 64
PROGRAM:9(d)
#include <iostream>
using namespace std;
// A utility function to get the maximum value in an array
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
// A function to do counting sort based on the digit represented by exp (exponent)
void countingSort(int arr[], int n, int exp) {
int output[n]; // Output array to store the sorted order
int count[10] = {0}; // Count array to store the count of each digit (0-9)
// Count occurrences of digits
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
// Change count[i] so that it contains the actual position of this digit in output[]
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
// Build the output array
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
// Copy the sorted elements into the original array
for (int i = 0; i < n; i++)
arr[i] = output[i];
// The main function to implement radix sort
void radixSort(int arr[], int n) {
// Find the maximum number to know the number of digits
int max = getMax(arr, n);
// Perform counting sort for every digit (1s, 10s, 100s, etc.)
for (int exp = 1; max / exp > 0; exp *= 10)
countingSort(arr, n, exp);
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
int main() {
int n;
// Input array size
cout << "Enter the number of elements in the array: ";
cin >> n;
int arr[n];
// Input array elements
cout << "Enter the elements of the array: ";
for (int i = 0; i < n; i++) {
cin >> arr[i];
// Perform radix sort
radixSort(arr, n);
// Output sorted array
cout << "Sorted array: ";
printArray(arr, n);
return 0;
}
OUTPUT:
Enter the number of elements in the array: 5
Enter the elements of the array: 170 45 75 90 802
Sorted array: 45 75 90 170 802
