DSA LAB FILE
NAME : ABHISHIKA CHOUDHARY
ROLL NO : 24BCS005
SECTION : CS A
BATCH : 2024
COURSE INSTRUCTOR : DR . NITIN GUPTA
[Link] LIST OF EXPERIMENTS DATE REMARKS
Given an array X. Compute the array A such that A[i] is the 30/07/2025
1. average of elements X[0]. . . X[i], for i = 0....n − 1. You can
solve this with two methods, one with O(n2 ) and one
with O(n) time complexities. Compare time complexities
of both the methods by experimental approach plotting
graph between ‘n’ and time taken for execution.
2. Write a program to sort an array (make a dynamic 06/08/2025
array) using Bubble sort. Use 1-bit variable FLAG to
signal when no interchange take place during pass. If
FLAG is 0 after any pass, then list is already sorted
and there is no need to continue.
3. WAP to search an ITEM (integer) in an array using 13/08/2025
binary search, if FOUND then delete that item from
array and if NOT FOUND than insert that item in
position such that array remain sorted.
4. Implement linked list and insert and delete an 20/08/2025
element into the list.
5. Evaluate a postfix algebraic expression with the help 03/09/2025
of stack.
6. Implement a queue using arrays and linked list. 10/09/2025
7. Implement a binary tree and implement any 17/09/2025
traversal technique as you like.
8. Implement a binary Search Tree and insert and 01/10/2025
delete a node in the BST.
9. Implement Max Priority queue using Max Heap. 22/10/2025
Implement a graph and find transpose of a graph where 29/10/2025
10. Transpose of a directed graph G is another directed graph
on the same set of vertices with all of the edges reversed
compared to the orientation of the corresponding edges
in G. That is, if G contains an edge (u, v) then the
converse/transpose/reverse of G contains an edge (v, u)
and vice versa. Implement it with the help of adjacency
list and adjacency matrix.
11. Implement Quick Sort, Merge Sort, Insertion Sort 05/11/2025
and Selection Sort.
PROGRAM 1
Output:
Q1. Given an array X. Compute the array A such that A[i] is the average
of elements X[0]. . . X[i], for i = 0....n − 1. You can solve this with two
methods, one with O(n2 ) and one with O(n) time complexities. Compare
time complexities of both the methods by experimental approach plotting
graph between ‘n’ and time taken for execution.
CODE
C++ Program to Write time taken By methods in csv file :
#include <iostream>
#include <vector>
#include <chrono>
#include <fstream>
#include <random>
using namespace std;
void quadraticFunc(const vector<int>& arr) {
volatile long long dummy = 0;
for (size_t i = 0; i < [Link](); i++) {
for (size_t j = 0; j <= i; j++) {
dummy += arr[j];
void linearFunc(const vector<int>& arr) {
volatile long long dummy = 0;
for (size_t i = 0; i < [Link](); i++) {
dummy += arr[i];
template<typename Func>
double measure(Func f, const vector<int>& arr) {
double total = 0;
for (int t = 0; t < 50; t++) {
auto start = chrono::high_resolution_clock::now();
f(arr);
auto end = chrono::high_resolution_clock::now();
chrono::duration<double, nano> duration = end - start;
total += [Link]();
return total / 50.0;
vector<int> generateVector(int n) {
static mt19937 rng(12345);
uniform_int_distribution<int> dist(1, 1000);
vector<int> v(n);
for (int& x : v) x = dist(rng);
return v;
int main() {
ofstream L("linear_times.csv");
ofstream Q("quadratic_times.csv");
L << "n,linear_time\n";
Q << "m,quadratic_time\n";
for (int n = 50000; n <= 1000000; n += 50000) {
auto arr = generateVector(n);
double t = measure(linearFunc, arr);
L << n << "," << t << "\n";
cout << "Linear n=" << n << " time=" << t << " ns\n";
for (int m = 200; m <= 2000; m += 50) {
auto arr = generateVector(m);
double t = measure(quadraticFunc, arr);
Q << m << "," << t << "\n";
cout << "Quadratic m=" << m << " time=" << t << " ns\n";
cout << "CSV Generated.\n";
return 0;
}
TIMING RESULTS BRUTE FORCE
PYTHON PROGRAM TO READ CSV FILE AND PLOT GRAPH:
import pandas as pd
import [Link] as plt
# Read from SAME folder as the script
linear = pd.read_csv("linear_times.csv")
quadratic = pd.read_csv("quadratic_times.csv")
# ----------- Plot Linear -----------
[Link](figsize=(10,6))
[Link](linear["n"], linear["linear_time"], marker='o', linewidth=2)
[Link]("Linear Algorithm Execution Time O(n)")
[Link]("Input Size (n)")
[Link]("Execution Time (microseconds)")
[Link](True)
[Link]()
# ----------- Plot Quadratic --------
[Link](figsize=(10,6))
[Link](quadratic["m"], quadratic["quadratic_time"], marker='s', linewidth=2)
[Link]("Quadratic Algorithm Execution Time O(n²)")
[Link]("Input Size (m)")
[Link]("Execution Time (microseconds)")
[Link](True)
[Link]()
PROGRAM-2:
OUTPUT
Program [Link] a program to sort an array (make a dynamic array)
using Bubble sort. Use 1-bit variable FLAG to signal when no interchange
take place during pass. If FLAG is 0 after any pass, then list is already
sorted and there is no need to continue.
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
using namespace std;
int* bubbleSort (vector <int> *A)
int n = A->size();
int * R = new int[n];
for (int i = 0; i<n; i++){
R[i]=(*A)[i];
for (int pass = 0; pass <n-1;pass++)
{ bool flag = false;
for (int i = 0; i<n-1-pass;i++){
if (R[i]>R[i+1]){
swap(R[i],R[i+1]);
flag = true;
if (flag==false){
break;
}}
return R;
vector <int> generateRandom(int n){
vector <int> X(n);
srand(time(0));
for (int i = 0; i < n; i++) {
X[i] = (rand() % 100) + 1;
return X;
int main(){
cout<<"Enter size of array: ";
int n;
cin>>n;
vector <int> A = generateRandom(n);
int * SortedArray = bubbleSort(&A);
for(int i = 0 ; i<n; i++){
cout<<SortedArray[i]<<" ";
delete[] SortedArray;
return 0;
}
PROGRAM-3
OUTPUT
Program 3. WAP to search an ITEM (integer) in an array using binary
search, if FOUND, delete that item from array and if NOT FOUND then
insert that item in position such that array remain sorted.
#include <iostream>
using namespace std;
int BinarySearch(int arr[], int n , int key , bool &found ){
int l = 0 , h = n-1 ;
found = false ;
while (l<=h){
int mid = (h+l)/2;
if ( arr[mid] == key){
cout<<"element is found"<<endl;
found = true;
return mid;}
else if (arr[mid]< key){
l = mid +1;}
else {
h = mid -1;}
return l;
int Insert(int arr[], int n , int pos , int size , int value){
if (n >= size){
cout<< "array is full cannot insert\n"<<endl;
return n;
else {
for ( int i = n-1; i >= pos ; i--){
arr[i]=arr[i-1]; }
arr[pos]= value;
return n+1;
}}
int Delete (int arr[], int n , int pos ){
for ( int i = pos ; i <n-1; i++ ){
arr[i]= arr[i+1];}
return n-1;
void displayarr(int arr[], int n){
for (int i = 0 ; i < n ; i ++){
cout<< arr[i]<< " ";}}
int main (){
int arr [20] = {2,3,4,6,7,8,12, 13 , 14 , 16};
int size = 20;
int n = 10;
int key;
cout<<"Enter the key value: ";
cin>>key;
bool found;
int index = BinarySearch(arr, n , key , found);
if (found){
cout<<"Element found at position "<< index << "deleting";
Delete(arr , n , index);
cout<<"REsultant array: ";
displayarr ( arr, n-1);
}else {
cout << "Element not found inserting at "<<index << endl;
Insert(arr, n , index , size , key);
cout<<"REsultant array: ";
displayarr( arr, n+1);
}return 0;
}
PROGRAM-4
OUTPUT
Program [Link] linked list and insert and delete an element into
the list.
#include <iostream>
#include <string>
using namespace std;
class LinkedList {
public:
struct info {
int rollNo;
string name;
float cgpa;
};
struct Node {
info data;
Node* next;
Node(const info& s, Node* n = nullptr) : data(s), next(n) {}
};
Node* head = nullptr;
Node* tail = nullptr;
info inputInfo() {
info s;
std::cout << "Enter rollNo, name, cgpa: ";
std::cin >> [Link] >> [Link] >> [Link];
return s;
void insertStart() {
info s = inputInfo();
Node* newNode = new Node(s, head);
head = newNode;
if (tail == nullptr) tail = newNode;
void insertEnd() {
info s = inputInfo();
Node* newNode = new Node(s);
if (!head) {
head = newNode;
tail = newNode;
return;
tail->next = newNode;
tail = newNode;
void insertAtPos(int pos) {
if (pos == 0) {
insertStart();
return;
info s = inputInfo();
Node* temp = head;
for (int i = 0; temp && i < pos - 1; i++) temp = temp->next;
if (!temp) return;
Node* newNode = new Node(s, temp->next);
temp->next = newNode;
if (newNode->next == nullptr) {
tail = newNode;
void deleteAtStart() {
if (!head) return;
Node* temp = head;
head = head->next;
delete temp;
if (!head) tail = nullptr;
void deleteAtEnd() {
if (!head) return;
if (!head->next) {
delete head;
head = nullptr;
tail = nullptr;
return;
Node* temp = head;
while (temp->next && temp->next->next) temp = temp->next;
delete temp->next;
temp->next = nullptr;
tail = temp;
void deleteAtPosition(int pos) {
if (!head) return;
if (pos == 0) {
deleteAtStart();
return;
Node* temp = head;
for (int i = 0; temp->next && i < pos - 1; i++) temp = temp->next;
if (!temp->next) return;
Node* delNode = temp->next;
temp->next = delNode->next;
if (temp->next == nullptr) tail = temp;
delete delNode;
void display() {
Node* temp = head;
while (temp) {
cout << "Roll No: " << temp->[Link] << ", Name: " << temp->[Link] << ", CGPA: " <<
temp->[Link] << std::endl;
temp = temp->next;
};
int main() {
LinkedList list;
int choice, pos;
while (true) {
cout << "\n1. Insert at Start\n2. Insert at End\n3. Insert at Position\n4. Delete at Start\n5. Delete
at End\n6. Delete at Position\n7. Display\n8. Exit\nEnter choice: ";
cin >> choice;
switch (choice) {
case 1:
[Link]();
break;
case 2:
[Link]();
break;
case 3:
cout << "Enter position: ";
cin >> pos;
[Link](pos);
break;
case 4:
[Link]();
break;
case 5:
[Link]();
break;
case 6:
cout << "Enter position: ";
cin >> pos;
[Link](pos);
break;
case 7:
[Link]();
break;
case 8:
return 0;
default:
cout << "Invalid choice!" << endl;
}
PROGRAM 5
OUTPUT
Program 5. Evaluate a postfix algebraic expression with the help of
stack.
#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#define MAXSIZE 50
using namespace std;
class Stack {
int arr[MAXSIZE];
int top;
public:
Stack() { top = -1; }
bool isEmpty() { return top == -1; }
bool isFull() { return top == MAXSIZE - 1; }
void push(int val) {
if (isFull()) {
cout << "Stack Overflow!" << endl;
return;
arr[++top] = val;
int pop() {
if (isEmpty()) {
throw runtime_error("Stack Underflow: Invalid postfix expression");
return arr[top--];
int peek() {
if (isEmpty()) {
throw runtime_error("Stack is empty");
return arr[top];
};
bool isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
int evaluatePostfix(const string& expr) {
Stack stack;
stringstream ss(expr);
string token;
while (ss >> token) {
if (isdigit(token[0]) || (token[0] == '-' && [Link]() > 1 && isdigit(token[1]))) {
[Link](stoi(token));
else if ([Link]() == 1 && isOperator(token[0])) {
if ([Link]()) {
throw runtime_error("Invalid expression: Not enough operands");
int val2 = [Link]();
if ([Link]()) {
throw runtime_error("Invalid expression: Not enough operands");
int val1 = [Link]();
int result = 0;
switch (token[0]) {
case '+': result = val1 + val2; break;
case '-': result = val1 - val2; break;
case '*': result = val1 * val2; break;
case '/':
if (val2 == 0) {
throw runtime_error("Division by zero error");
result = val1 / val2;
break;
[Link](result);
else {
throw runtime_error("Invalid token: " + token);
if ([Link]()) {
throw runtime_error("Empty expression");
int finalResult = [Link]();
if (![Link]()) {
throw runtime_error("Invalid expression: Too many operands");
return finalResult;
}
int main() {
string expr;
cout << "Enter postfix expression : ";
getline(cin, expr);
try {
int result = evaluatePostfix(expr);
cout << "Result: " << result << endl;
} catch (const exception& e) {
cout << "Error: " << [Link]() << endl;
return 0;
}
PROGRAM 6
OUTPUT
Program 6. Implement a queue using arrays and linked list.
#include <iostream>
using namespace std;
#define SIZE 10
class QueueArr {
int nums[SIZE];
int front , rear;
public :
QueueArr (){
front = -1;
rear = -1;
bool isEmpty (){
return (front == -1 || front > rear);
bool isFull (){
return (rear == SIZE -1);
void Enqueue (int x){
if (isFull()){
cout << "queue overflow \n";
return;
else if (front == -1) front = 0;
nums[++rear] = x;
cout << x << "enqueued"<< endl;
}
void Dequeue (){
if (isEmpty()){
cout << "queue underflow\n";
return;
else if (front == rear ){
front = rear -1 ;
else {
front ++;
void Peek () {
if (isEmpty()){
cout << "queue is Empty\n";
return ;
else {
cout << "Front : " << nums[front];
};
struct Node {
int data;
Node* next;
};
class Queuell {
Node* front;
Node* rear;
public:
Queuell() {
front = rear = nullptr;
void enqueue(int x) {
Node* temp = new Node();
temp->data = x;
temp->next = nullptr;
if (rear == nullptr) {
front = rear = temp;
return;
rear->next = temp;
rear = temp;
void dequeue() {
if (front == nullptr) {
cout << "Queue is empty\n";
return;
Node* temp = front;
front = front->next;
if (front == nullptr)
rear = nullptr;
delete temp;
void display() {
Node* temp = front;
while (temp != nullptr) {
cout << temp->data << " ";
temp = temp->next;
cout << endl;
};
int main(){
int r ;
cout << "choose the implementation method for queue :\n"<< "1. QueueArr\n" <<
"[Link]\n"<<endl;
cin>> r;
if (r == 1){
QueueArr qu;
int x =0;
while(true){
cout << " Enter Choice :\n " << " [Link]\n " << " [Link] \n" << " [Link]\n"<< "[Link]\n";
cin >> x;
switch (x){
case 2 :
cout << "Enter value to be enqueued : ";
cin >> x;
[Link](x);
[Link]();
break;
case 3 :
cout << "Before Dequeue: " ;
[Link]();
[Link]();
cout << "After Dequeue : ";
[Link]();
break;
case 1 :
[Link]();
break;
case 4 :
return 0;}
else if (r == 2){
Queuell q;
int choice, val;
while (true) {
cout << "1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\nEnter choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value: ";
cin >> val;
[Link](val);
break;
case 2:
[Link]();
break;
case 3:
[Link]();
break;
case 4:
return 0;
default:
cout << "Invalid choice\n";
}
}
else {
cout<<"invalid choice "<<endl;
return 0;
}
PROGRAM 7
OUTPUT
Program 7. Implement a binary tree and implement any traversal
technique as you like.
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int data1) {
data = data1;
left = right = nullptr;
}};
Node* insertBST(Node* root, int val) {
if (root == nullptr)
return new Node(val);
if (val < root->data)
root->left = insertBST(root->left, val);
else
root->right = insertBST(root->right, val);
return root;}
Node* createBST(const vector<int>& arr) {
Node* root = nullptr;
for (int val : arr)
root = insertBST(root, val);
return root;}
void preorder(Node* root) {
if (!root) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);}
void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);}
void postorder(Node* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";}
int main() {
int n;
cout << "Enter size of array: ";
cin >> n;
vector<int> arr(n);
cout << "Enter elements: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
Node* root = createBST(arr);
int choice;
cout << "\nChoose from:\n";
cout << "1. Preorder traversal\n";
cout << "2. Inorder traversal\n";
cout << "3. Postorder traversal\n";
cout << "4. Exit\n";
cout << "Enter choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Preorder Traversal: ";
preorder(root);
cout << endl;
break;
case 2:
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
break;
case 3:
cout << "Postorder Traversal: ";
postorder(root);
cout << endl;
break;
case 4:
cout << "Exiting program\n";
break;
default:
cout << "Invalid choice\n";
return 0;}
PROGRAM-8
OUTPUT
Program 8. Implement a binary search tree and perform insert and
delete on the BST.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = right = nullptr;
};
Node* insertNode(Node* root, int val) {
if (root == nullptr)
return new Node(val);
if (val > root->data)
root->right = insertNode(root->right, val);
else
root->left = insertNode(root->left, val);
return root;
Node* minValueNode(Node* root) {
Node* current = root;
while (current && current->left)
current = current->left;
return current;
}
Node* deleteNode(Node* root, int val) {
if (root == nullptr)
return root;
if (val < root->data)
root->left = deleteNode(root->left, val);
else if (val > root->data)
root->right = deleteNode(root->right, val);
else {
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* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
return root;
void inorder(Node* root) {
if (root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
int main() {
Node* root = nullptr;
root = insertNode(root, 50);
root = insertNode(root, 30);
root = insertNode(root, 70);
root = insertNode(root, 20);
root = insertNode(root, 40);
root = insertNode(root, 60);
root = insertNode(root, 80);
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
int del;
cout << "Enter element to delete: ";
cin >> del;
root = deleteNode(root, del);
cout << "After deletion: ";
inorder(root);
cout << endl;
int ele;
cout << "Enter element to insert: ";
cin >> ele;
root = insertNode(root, ele);
cout << "After insertion: ";
inorder(root);
cout << endl;
return 0;
}
PROGRAM 9
OUTPUT
Program 9. Implement maximum priority queue using max heap.
#include <iostream>
using namespace std;
#define MAX 50
class MaxHeap {
private:
int heap[MAX];
int size;
public:
MaxHeap() {
size = 0;
void insert(int value) {
if (size == MAX - 1) {
cout << "Heap is full!" << endl;
return;
size++;
heap[size] = value;
int i = size;
while (i > 1 && heap[i] > heap[i / 2]) {
swap(heap[i], heap[i / 2]);
i /= 2;
}
int extractMax() {
if (size == 0) {
cout << "Heap is empty!" << endl;
return -1;
int maxVal = heap[1];
heap[1] = heap[size];
size--;
int i = 1;
while (true) {
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
if (left <= size && heap[left] > heap[largest])
largest = left;
if (right <= size && heap[right] > heap[largest])
largest = right;
if (largest != i) {
swap(heap[i], heap[largest]);
i = largest;
} else {
break;
return maxVal;
}
void display() {
if (size == 0) {
cout << "Heap is empty!" << endl;
return;
cout << "\nMax Heap: ";
for (int i = 1; i <= size; i++)
cout << heap[i] << " ";
cout << endl;
};
int main() {
MaxHeap pq;
int choice, value;
do {
cout << "\n--- Max Priority Queue Menu ---";
cout << "\n1. Insert an element";
cout << "\n2. Extract Max element";
cout << "\n3. Display Heap";
cout << "\n4. Exit";
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice) {
case 1:
cout << "Enter value to insert: ";
cin >> value;
[Link](value);
break;
case 2:
value = [Link]();
if (value != -1)
cout << "Max element extracted: " << value << endl;
break;
case 3:
[Link]();
break;
case 4:
cout << "Exiting..." << endl;
break;
default:
cout << "Invalid choice!" << endl;
} while (choice != 4);
return 0;
}
PROGRAM 10
OUTPUT
Program 10. Implement a graph and find transpose of a graph where
Transpose of a directed graph G is another directed graph on the same
set of vertices with all of the edges reversed compared to the
orientation of the corresponding edges in G. That is, if G contains an
edge (u, v) then the converse/transpose/reverse of G contains an edge
(v, u) and vice versa. Implement it with the help of adjacency list and
adjacency matrix.
#include <iostream>
#include <vector>
using namespace std;
class Graph {
int V;
vector<vector<int>> adjList;
vector<vector<int>> adjMatrix;
public:
Graph(int vertices) {
V = vertices;
[Link](V);
[Link](V, vector<int>(V, 0));
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjMatrix[u][v] = 1;
void displayAdjList() {
cout << "\nAdjacency List:\n";
for (int i = 0; i < V; i++) {
cout << i << " -> ";
for (int v : adjList[i])
cout << v << " ";
cout << endl;
void displayAdjMatrix() {
cout << "\nAdjacency Matrix:\n";
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++)
cout << adjMatrix[i][j] << " ";
cout << endl;
Graph getTranspose() {
Graph gT(V);
for (int u = 0; u < V; u++) {
for (int v : adjList[u])
[Link](v, u);
return gT;
};
int main() {
int V, E;
cout << "Enter number of vertices: ";
cin >> V;
Graph g(V);
cout << "Enter number of edges: ";
cin >> E;
cout << "Enter edges (u v):\n";
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
[Link](u, v);
cout << "\nOriginal Graph:";
[Link]();
[Link]();
Graph gT = [Link]();
cout << "\nTranspose Graph:";
[Link]();
[Link]();
return 0;
}
PROGRAM 11
OUTPUT
Program 11. Implement Quick Sort, Merge Sort, Insertion Sort, Selection
Sort.
#include <iostream>
using namespace std;
void insertion_sort(int arr[], int n) {
for (int i = 0; i < n; i++) {
int j = i;
while (j > 0 && arr[j - 1] > arr[j]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
j--;
void merge(int arr[], int low, int mid, int high) {
int left = mid - low + 1;
int right = high - mid;
int L[left], R[right];
for (int i = 0; i < left; i++) L[i] = arr[low + i];
for (int j = 0; j < right; j++) R[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = low;
while (i < left && j < right) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
while (i < left) arr[k++] = L[i++];
while (j < right) arr[k++] = R[j++];
}
void merge_sort(int arr[], int low, int high) {
if (low < high) {
int mid = (low + high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid + 1, high);
merge(arr, low, mid, high);
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;
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min])
min = j;
if (min != i) swap(arr[i], arr[min]);
int main() {
int n;
cout << "Enter size of array: ";
cin >> n;
int arr1[n], arr2[n], arr3[n], arr4[n];
cout << "Enter array elements: ";
for (int i = 0; i < n; i++) {
cin >> arr1[i];
arr2[i] = arr3[i] = arr4[i] = arr1[i];
merge_sort(arr1, 0, n - 1);
quick_sort(arr2, 0, n - 1);
insertion_sort(arr3, n);
selectionSort(arr4, n);
cout << "\nAfter Merge Sort:\n";
for (int i = 0; i < n; i++) cout << arr1[i] << " ";
cout << "\nAfter Quick Sort:\n";
for (int i = 0; i < n; i++) cout << arr2[i] << " ";
cout << "\nAfter Insertion Sort:\n";
for (int i = 0; i < n; i++) cout << arr3[i] << " ";
cout << "\nAfter Selection Sort:\n";
for (int i = 0; i < n; i++) cout << arr4[i] << " ";
cout << endl;
return 0;