Practical No.
- 1
Aim: Write a program to implement push and pop operations on a queue using linked
list.
Code:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int value) {
data = value;
next = nullptr;
}
};
class Queue {
private:
Node* front;
Node* rear;
public:
Queue() {
front = rear = nullptr;
}
void push(int value) {
Node* newNode = new Node(value);
if (rear == nullptr) {
Anoorag Singh 2337373
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
void pop() {
if (front == nullptr) {
cout << "Queue is empty" << endl;
return;
}
Node* temp = front;
front = front->next;
if (front == nullptr) {
rear = nullptr;
}
delete temp;
}
void display() {
if (front == nullptr) {
cout << "Queue is empty" << endl;
return;
}
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
Anoorag Singh 2337373
}
};
int main() {
Queue q;
q.push(10);
q.push(20);
q.push(30);
cout << "Queue after pushes: ";
q.display();
q.pop();
cout << "Queue after one pop: ";
q.display();
return 0;
}
Output :
Practical No. - 14
Anoorag Singh 2337373
Aim: Write a program to sort an array of integers in ascending order using bubble sort .
Code:
#include <iostream>
using namespace std;
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;
}
}
}
}
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Original array: ";
displayArray(arr, n);
Anoorag Singh 2337373
bubbleSort(arr, n);
cout << "Sorted array in ascending order: ";
displayArray(arr, n);
return 0;
}
Output :
Practical No. - 15
Anoorag Singh 2337373
Aim: Write a program to sort an array of integers in ascending order using selection
sort.
Code:
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
Anoorag Singh 2337373
cout << "Original array: ";
displayArray(arr, n);
selectionSort(arr, n);
cout << "Sorted array in ascending order: ";
displayArray(arr, n);
return 0;
}
Output :
Practical No. - 16
Anoorag Singh 2337373
Aim: Write a program to sort an array of integers in ascending order using insertion
sort.
Code:
#include <iostream>
using namespace std;
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;
}
}
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Original array: ";
displayArray(arr, n);
Anoorag Singh 2337373
insertionSort(arr, n);
cout << "Sorted array in ascending order: ";
displayArray(arr, n);
return 0;
}
Output :
Practical No. - 17
Aim: Write a program to sort an array of integers in ascending order using quick sort.
Anoorag Singh 2337373
Code:
#include <iostream>
using namespace std;
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);
}
}
void displayArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
Anoorag Singh 2337373
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
displayArray(arr, n);
quickSort(arr, 0, n - 1);
cout << "Sorted array in ascending order: ";
displayArray(arr, n);
return 0;
}
Output :
Practical No. - 18
Aim: Write a program to traverse a Binary search tree in Pre-order, In-order and Post-
order.
Anoorag Singh 2337373
Code:
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
class BST {
public:
Node* root;
BST() {
root = nullptr;
}
Node* insert(Node* node, int value) {
if (node == nullptr) {
return new Node(value);
}
if (value < node->data) {
node->left = insert(node->left, value);
} else if (value > node->data) {
node->right = insert(node->right, value);
}
return node;
}
Anoorag Singh 2337373
void preOrder(Node* node) {
if (node != nullptr) {
cout << node->data << " ";
preOrder(node->left);
preOrder(node->right);
}
}
void inOrder(Node* node) {
if (node != nullptr) {
inOrder(node->left);
cout << node->data << " ";
inOrder(node->right);
}
}
void postOrder(Node* node) {
if (node != nullptr) {
postOrder(node->left);
postOrder(node->right);
cout << node->data << " ";
}
}
};
int main() {
BST tree;
tree.root = tree.insert(tree.root, 50);
tree.insert(tree.root, 30);
tree.insert(tree.root, 20);
tree.insert(tree.root, 40);
tree.insert(tree.root, 70);
tree.insert(tree.root, 60);
tree.insert(tree.root, 80);
Anoorag Singh 2337373
cout << "Pre-order traversal: ";
tree.preOrder(tree.root);
cout << endl;
cout << "In-order traversal: ";
tree.inOrder(tree.root);
cout << endl;
cout << "Post-order traversal: ";
tree.postOrder(tree.root);
cout << endl;
return 0;
}
Output :
Practical No. - 19
Aim: Write a program to traverse graphs using BFS.
Anoorag Singh 2337373
Code:
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
int V;
list<int>* adj;
public:
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void addEdge(int v, int w) {
adj[v].push_back(w);
}
void BFS(int start) {
bool* visited = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
}
queue<int> q;
visited[start] = true;
q.push(start);
Anoorag Singh 2337373
while (!q.empty()) {
int vertex = q.front();
cout << vertex << " ";
q.pop();
for (auto i = adj[vertex].begin(); i != adj[vertex].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
q.push(*i);
}
}
}
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 4);
cout << "BFS starting from vertex 2: ";
g.BFS(2);
return 0;
}
Anoorag Singh 2337373
Output :
Practical No. - 20
Aim: Write a program to traverse graphs using BFS.
Anoorag Singh 2337373
Code:
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
int V;
list<int>* adj;
public:
Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void addEdge(int v, int w) {
adj[v].push_back(w);
}
void BFS(int start) {
bool* visited = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
}
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
Anoorag Singh 2337373
int vertex = q.front();
cout << vertex << " ";
q.pop();
for (auto i = adj[vertex].begin(); i != adj[vertex].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
q.push(*i);
}
}
}
delete[] visited;
}
~Graph() {
delete[] adj;
}
};
int main() {
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.addEdge(3, 4);
cout << "BFS starting from vertex 2: ";
Anoorag Singh 2337373
g.BFS(2);
return 0;
}
Output :
Anoorag Singh 2337373
