NAME – Prateek Thakur

ROLL NO. – 195012

BRANCH – CSE([Link])

COURSE – DATA STRUCTURES

LAB

COURSE CODE – [CS- 202]

LAB EXPERIMENT – 1
⇨ Write 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 <stdio.h>

#include<stdlib.h>

int main()

int input, i,j,c;

int count=0; //keeps track of size of array

int *numbers=NULL; //pointer to integer array

int *more; //pointer to temporary array

int FLAG;

printf("Enter the numbers(Enter -1000 to stop): ");

do

scanf("%d",&input);

count++;

//ask for more memory

more=(int*)realloc(numbers,count*sizeof(int));

if(more!=NULL)

//if memory allocation successful

numbers=more; //make "numbers" point to memory block pointed by "more"

numbers[count-1]=input; //store the given number in the array

else

//if there's an error allocating memory

 free(numbers);

printf("Error reallocating memory");

exit(1); //exit out of the program,with return code "1"

}while(input!=-1000); //keep asking for more numbers untill,-1000 entered by the

user

//print out the given array

printf("Numbers entered: ");

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

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

printf("\n");

/* BUBBLE SORT */

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

{ FLAG=0;

for (j=0;j<count-1-1;j++)

if (numbers[j] > numbers[j+1])

{ FLAG=1;

c=numbers[j];

numbers[j]=numbers[j+1];

numbers[j+1]=c;

if (FLAG==0){

exit(0);

}
 //printing the sorted list

printf("\nSorted list in ascending order:\n");

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

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

printf("\n");

free(numbers); //freeing the memory

return 0;

OUTPUT:
LAB EXPERIMENT – 2

WAP to search an ITEM (integer) in an array using binary search, if

FOUND then delete that item from array and if NOT FOUND than insert
that item in kth position (Input “k” from user).
#include <iostream>

using namespace std;

// To search a ley to be deleted

int binarySearch(int arr[], int low, int high, int key);

int insertSorted(int arr[], int n, int key, int capacity)

// Cannot insert more elements if n is already

// more than or equal to capcity

if (n >= capacity)

return n;

int i;

for (i = n - 1; (i >= 0 && arr[i] > key); i--)

arr[i + 1] = arr[i];

arr[i + 1] = key;

return (n + 1);

/* Function to delete an element */

int deleteElement(int arr[], int n, int key)

// Find position of element to be deleted

int pos = binarySearch(arr, 0, n - 1, key);

// Deleting element

int i;

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

 arr[i] = arr[i + 1];

return n - 1;

int binarySearch(int arr[], int low, int high, int key)

if (high < low)

return -1;

int mid = (low + high) / 2;

if (key == arr[mid])

return mid;

if (key > arr[mid])

return binarySearch(arr, (mid + 1), high, key);

return binarySearch(arr, low, (mid - 1), key);

// Driver code

int main()

int i,size,key,k;

int arr[100];

cout<<"how much you want to enter:";

cin>>size;

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

cin>>arr[i];

cout<< "enter the element :";

cin>>key;

k= binarySearch(arr, 0, size - 1, key);

if(k==-1){ int capacity = sizeof(arr) / sizeof(arr[0]);

size = insertSorted(arr, size, key, capacity);

cout << "\nAfter Insertion: ";

 for(i = 0; i < size; i++){

cout << arr[i]<< " ";}}

else{

size = deleteElement(arr, size, key);

cout << "\n\nArray after deletion\n";

for(i = 0; i < size; i++){

cout << arr[i] << " ";}}

return 0;

⇨ OUTPUT:
 LAB EXPERIMENT – 3
⇨ WAP to enter records of Five students, which should contain
fields like roll No., name, CGPI, semester. (a) List all record of all
students having CGPI greater than k. (b) Insert a new record of
student at kth position and print the final record.
#include <stdio.h>

#include<string.h>

struct student

char name[50];

int roll;

float CGPI;

} s[100];

int main()

int i,n,K;

char NAME[50];

int Roll;

float cgpi;

float k;

struct student s[100];

printf("Enter total of students:\n");

scanf("%d",&n);

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

printf("\n Enter information of student %d:\n",i+1);

printf("Enter name: ");

scanf("%s", s[i].name);

printf("Enter roll number: ");

scanf("%d", &s[i].roll);

printf("Enter CGPI: ");

scanf("%f", &s[i].CGPI);

printf("Enter CGPI From which you want to see: ");

scanf("%f", &k);

printf("Displaying Information:\n");

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

if(s[i].CGPI>k){

printf("\n %d no. student info\n",i+1);

printf("\tName:%s\n ",s[i].name);

printf("\t Roll number: %d\n",s[i].roll);

printf("\t CGPI: %f\n\n",s[i].CGPI);

printf("Enter the position you want to enter in : ");

scanf("%d", &K);

printf("Enter name: ");

scanf("%s", NAME);

printf("Enter roll number: ");

scanf("%d", &Roll);

printf("Enter CGPI: ");

scanf("%f", &cgpi);

// increase the size by 1

n++;

// shift elements forward

for (i = n-1; i >= K; i--)

strcpy(s[i].name,s[i - 1].name);

s[i].roll = s[i - 1].roll;

s[i].CGPI = s[i - 1].CGPI;

 // insert x at pos

strcpy(s[K - 1].name,NAME);

s[K - 1].roll = Roll;

s[K - 1].CGPI = cgpi;

printf("Displaying Information:\n");

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

printf("\n %d no. student info\n",i+1);

printf("\tName:%s\n ",s[i].name);

printf("\t Roll number: %d\n",s[i].roll);

printf("\t CGPI: %f\n\n",s[i].CGPI);

return 0;

}
OUTPUT:
LAB EXPERIMENT – 4

⇨ Implement linked list and insert and delete an element into the list.
#include<stdlib.h>

#include <stdio.h>

void create();

void display();

void insert_begin();

void insert_end();

void insert_pos();

void delete_begin();

void delete_end();

void delete_pos();

struct node

int info;

struct node *next;

};

struct node *start=NULL;

int main()

int choice;

while(1){

printf("\n MENU \n");

printf("\n [Link] \n");

printf("\n [Link] \n");

printf("\n [Link] at the beginning \n");

printf("\n [Link] at the end \n");

printf("\n [Link] at specified position \n");

printf("\n [Link] from beginning \n");

printf("\n [Link] from the end \n");

printf("\n [Link] from specified position \n");

printf("\n [Link] \n");

printf("\n--------------------------------------\n");

printf("Enter your choice:\t");

scanf("%d",&choice);

switch(choice)

case 1:

create();

break;

case 2:

display();

break;

case 3:

insert_begin();

break;

case 4:

insert_end();

break;

case 5:

insert_pos();

break;

case 6:

delete_begin();

break;

case 7:

delete_end();

break;

case 8:

delete_pos();

break;

case 9:

exit(0);
 break;

default:

printf("\n Wrong Choice:\n");

break;

return 0;

void create()

struct node *temp,*ptr;

temp=(struct node *)malloc(sizeof(struct node));

if(temp==NULL)

printf("\nOut of Memory Space:\n");

exit(0);

printf("\nEnter the data value for the node:\t");

scanf("%d",&temp->info);

temp->next=NULL;

if(start==NULL)

start=temp;

else

ptr=start;

while(ptr->next!=NULL)

ptr=ptr->next;

ptr->next=temp;

void display()
{

struct node *ptr;

if(start==NULL)

printf("\nList is empty:\n");

return;

else

ptr=start;

printf("\nThe List elements are:\n");

while(ptr!=NULL)

printf("%d\t",ptr->info );

ptr=ptr->next ;

void insert_begin()

struct node *temp;

temp=(struct node *)malloc(sizeof(struct node));

if(temp==NULL)

printf("\nOut of Memory Space:\n");

return;

printf("\nEnter the data value for the node:\t" );

scanf("%d",&temp->info);

temp->next =NULL;

if(start==NULL)

start=temp;

else

{
 temp->next=start;

start=temp;

void insert_end()

struct node *temp,*ptr;

temp=(struct node *)malloc(sizeof(struct node));

if(temp==NULL)

printf("\nOut of Memory Space:\n");

return;

printf("\nEnter the data value for the node:\t" );

scanf("%d",&temp->info );

temp->next =NULL;

if(start==NULL)

start=temp;

else

ptr=start;

while(ptr->next !=NULL)

ptr=ptr->next ;

ptr->next =temp;

void insert_pos()

struct node *ptr,*temp;

int i,pos;

temp=(struct node *)malloc(sizeof(struct node));

if(temp==NULL)
 {

printf("\nOut of Memory Space:\n");

return;

printf("\nEnter the position for the new node to be inserted:\t");

scanf("%d",&pos);

printf("\nEnter the data value of the node:\t");

scanf("%d",&temp->info) ;

temp->next=NULL;

if(pos==0)

temp->next=start;

start=temp;

else

for(i=0,ptr=start;i<pos-1;i++) { ptr=ptr->next;

if(ptr==NULL)

printf("\nPosition not found:[Handle with care]\n");

return;

temp->next =ptr->next ;

ptr->next=temp;

void delete_begin()

struct node *ptr;

if(ptr==NULL)

printf("\nList is Empty:\n");

return;

}
 else

ptr=start;

start=start->next ;

printf("\nThe deleted element is :%d\t",ptr->info);

free(ptr);

void delete_end()

struct node *temp,*ptr;

if(start==NULL)

printf("\nList is Empty:");

exit(0);

else if(start->next ==NULL)

ptr=start;

start=NULL;

printf("\nThe deleted element is:%d\t",ptr->info);

free(ptr);

else

ptr=start;

while(ptr->next!=NULL)

temp=ptr;

ptr=ptr->next;

temp->next=NULL;

printf("\nThe deleted element is:%d\t",ptr->info);

free(ptr);

}
void delete_pos()

int i,pos;

struct node *temp,*ptr;

if(start==NULL)

printf("\nThe List is Empty:\n");

exit(0);

else

printf("\nEnter the position of the node to be deleted:\t");

scanf("%d",&pos);

if(pos==0)

ptr=start;

start=start->next ;

printf("\nThe deleted element is:%d\t",ptr->info );

free(ptr);

else

ptr=start;

for(i=0;i<pos;i++) { temp=ptr; ptr=ptr->next ;

if(ptr==NULL)

printf("\nPosition not Found:\n");

return;

temp->next =ptr->next ;

printf("\nThe deleted element is:%d\t",ptr->info );

free(ptr);

}
⇨ OUTPUT :
 LAB EXPERIMENT -5
⇨ Evaluate a postfix algebraic expression with the help of stack.
#include<iostream>
#include<stdio.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>
#define MAX 100
using namespace std;
struct postfix
{
int stack[MAX];
int top,n;
char *s;
}p;
void init_post()
{
[Link]=-1;
}
void init_exp(char *str)
{
p.s=str;
}
void push(int number)
{
[Link]++;
[Link][[Link]]=number;
}
int pop()
{
int number=[Link][[Link]];
[Link]--;
return number;
}
void calculate()
{
int n1, n2, x;
while(*(p.s))
{
if(*(p.s)==' ' || *(p.s)==' ')
{
p.s++;
continue;
}
if(isdigit(*(p.s)))
{
p.n=*(p.s)-'0';
push(p.n);
}
else
{
n1=pop();
n2=pop();
switch(*(p.s))
{
case '+':
 x=n2+n1 ;
break;
case '-':
x=n2-n1 ;
break;
case '*':
x=n2*n1 ;
break;
case '/':
x=n2/n1 ;
break;
case '%':
x=n2%n1 ;
break;
case '^':
x=(int)pow(n2,n1) ;
break;
default:
cout<<"Invalid operator !!\n" ;
exit(1);
}
push(x);
}
p.s++;
}
}
void disp_result()
{
p.n=pop();
cout<<"\nResult = "<<p.n;
}
int main()
{
char exp[MAX];
init_post();
cout<<"Enter the postfix formed expression : ";
gets(exp);
init_exp(exp);

calculate();

disp_result();
return 0;
}

⇨ OUTPUT:
 LAB EXPERIMENT – 6
⇨ Implement a queue using linked list.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delet();
void display();
int main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\n");
printf("\
n======================================================
===========\n");
printf("\[Link] an element\[Link] an element\[Link] the queue\
[Link]\n");
printf("\nEnter your choice: \t");
scanf("%d",& choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice : \n");
}
}
}
void insert()
{
struct node *ptr;
int item;

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
 }
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delet()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}

⇨ OUTPUT:
⇨ Implement a queue using arrays.

#include<iostream>
#include <stdio.h>

#define MAX 50

void insert();
void delet();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
int choice;
while (1)
{
printf("\[Link] element to queue \n");
printf("\[Link] element from queue \n");
printf("\[Link] all elements of queue \n");
printf("\[Link] \n");
printf("\nEnter your choice :\t ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nWrong choice \n");
} /* End of switch */
} /* End of while */
} /* End of main() */

void insert()
{
int add_item;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
 {
if (front == - 1)
/*If queue is initially empty */
front = 0;
printf("\nInset the element in queue :\t ");
scanf("%d", &add_item);
rear = rear + 1;
queue_array[rear] = add_item;
}
} /* End of insert() */

void delet()
{
if (front == - 1 || front > rear)
{
printf("\nQueue Underflow \n");
return ;
}
else
{
printf("\nElement deleted from queue is :\t %d\n", queue_array[front]);
front = front + 1;
}
} /* End of delete() */

void display()
{
int i;
if (front == - 1)
printf("Queue is empty \n");
else
{
printf("\nQueue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
} /* End of display() */

⇨
⇨ OUTPUT:
 LAB EXPERIMENT – 7
⇨ Implement a binary tree and implement any traversal technique as you
like.

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

// Define the types of Traversals here

enum Traversal {PREORDER, INORDER, POSTORDER};

typedef enum Traversal Traversal;

typedef struct Node Node;

// Define the Tree Node here

struct Node {
int value;
// Pointers to the left and right children
Node* left, *right;
};

Node* init_tree(int data) {

// Creates the tree and returns the
// root node
Node* root = (Node*) malloc (sizeof(Node));
root->left = root->right = NULL;
root->value = data;
return root;
}

Node* create_node(int data) {

// Creates a new node
Node* node = (Node*) malloc (sizeof(Node));
node->value = data;
node->left = node->right = NULL;
return node;
}
void free_tree(Node* root) {
// Deallocates memory corresponding
// to every node in the tree.
Node* temp = root;
if (!temp)
return;
free_tree(temp->left);
free_tree(temp->right);
 if (!temp->left && !temp->right) {
free(temp);
return;
}
}

void print_tree(Traversal traversal, Node* root) {

// Prints the tree according to
// various types of traversals
if (!root)
return;
switch(traversal) {
case (PREORDER):
// Do a Preorder Traversal
printf("%d -> ", root->value);
print_tree(traversal, root->left);
print_tree(traversal, root->right);
break;

case (INORDER):
// Do an Inorder Traversal
print_tree(traversal, root->left);
printf("%d -> ", root->value);
print_tree(traversal, root->right);
break;

case (POSTORDER):
// Do a postorder Traversal
print_tree(traversal, root->left);
print_tree(traversal, root->right);
printf("%d -> ", root->value);
break;
}
}

int main() {
// Program to demonstrate finding the height of a Binary Tree

// Create the root node having a value of 10

Node* root = init_tree(10);

// Insert nodes onto the tree

root->left = create_node(20);
root->right = create_node(30);

root->left->left = create_node(40);
root->left->right = create_node(50);

root->right->left = create_node(60);
root->right->right = create_node(70);

printf("----Preorder Traversal:----\n");
print_tree(PREORDER, root);
printf("\n\n");

printf("----Inorder Traversal:----\n");
 print_tree(INORDER, root);
printf("\n\n");

printf("----Postorder Traversal:----\n");
print_tree(POSTORDER, root);
printf("\n\n");

// Free the tree!

free_tree(root);
return 0;
}

⇨ OUTPUT:
 LAB EXPERIMENT- 8
⇨ Implement a binary Search Tree and insert and
delete a node in the BST.

#include <bits/stdc++.h>
using namespace std;

class Node{
public:
int data;
Node *left;
Node *right;

public:
Node(int x){
data = x;
left = NULL;
right = NULL;
}

};

Node *insert_BST(Node *tree, int val)

{
if(tree == NULL){
cout<<val <<" is inserted into BST successfully"<<endl;
return (new Node(val));
}
if(tree->data >= val)
tree->left = insert_BST(tree->left, val);
else
tree->right = insert_BST(tree->right, val);

return tree;
}

int search_BST(Node *tree, int val)

{
if(tree == NULL){
cout<<val<<" is not present in the tree\n";
return 0;
 }

string ret_val;
if(tree->data == val)
cout<<val<<" is present in the tree\n";
else if(tree->data > val)
search_BST(tree->left, val);
else
search_BST(tree->right, val);

return 0;

Node* delete_BST(Node *tree, int val)

{
if(tree == NULL){
cout<<"value is not present in BST"<<endl;
return tree;
}

if(tree->data > val)

tree->left = delete_BST(tree->left, val);
else if(tree->data < val)
tree->right = delete_BST(tree->right, val);

else{
//if left child of the node is empty
if(tree->left == NULL){
Node *temp = tree->right;
free(tree);
tree= temp;
}
//if right child of the node is empty
else if(tree->right == NULL){
Node *temp = tree->left;
tree = temp;
free(temp);
}
//if both left and right child exists for the node
else{
Node *temp = tree->left;
while(temp->right->right!=NULL){ // traverse until you don't reach, the
second last right node of the left child of node to be deleted
temp = temp->right;
}
tree->data = temp->right->data; // update the value to be deleted with
the value of the rightmost node
Node *temp2 = temp->right->left; // pointer to the left child of the last
right node
free(temp->right); // delete the last node
temp->right = temp2; // assign the left child of last right node to
second last right node
}

}
return tree;
}

void inorder(Node *tree)

{
if (tree != NULL)
{
inorder(tree->left);
cout<<tree->data<<" ";
inorder(tree->right);
}
}

int main(){

Node *tree;

tree = new Node(10);

tree->left = new Node(5);

tree->left->left = new Node(2);
tree->left->right = new Node(8);
tree->left->left->left = new Node(1);
tree->left->left->right = new Node(4);
tree->left->right->left = new Node(7);

tree->right = new Node(17);

tree->right->left = new Node(16);
tree->right->right = new Node(18);

insert_BST(tree, 9);
cout<<"inorder traversal of the current tree is: ";
inorder(tree);
cout<<endl;

search_BST(tree,9);

tree = delete_BST(tree,5);
cout<<"deleted 5 successfully \n";
search_BST(tree,5);
cout<<"inorder traversal of the current tree is: ";
inorder(tree);
cout<<endl;

return 0;
}

⇨ OUTPUT:
 LAB EXPERIMENT – 9

⇨ Implement Max Priority queue using Max Heap.

#include <stdio.h>

int tree_array_size = 20;

int heap_size = 0;

const int INF = 100000;

void swap( int *a, int *b ) {

int t;

t = *a;

*a = *b;

*b = t;

//function to get right child of a node of a tree

int get_right_child(int A[], int index) {

if((((2*index)+1) < tree_array_size) && (index >= 1))

return (2*index)+1;
 return -1;

//function to get left child of a node of a tree

int get_left_child(int A[], int index) {

if(((2*index) < tree_array_size) && (index >= 1))

return 2*index;

return -1;

//function to get the parent of a node of a tree

int get_parent(int A[], int index) {

if ((index > 1) && (index < tree_array_size)) {

return index/2;

return -1;

void max_heapify(int A[], int index) {

int left_child_index = get_left_child(A, index);

int right_child_index = get_right_child(A, index);

// finding largest among index, left child and right child

int largest = index;

if ((left_child_index <= heap_size) && (left_child_index>0)) {

if (A[left_child_index] > A[largest]) {

largest = left_child_index;

if ((right_child_index <= heap_size && (right_child_index>0))) {

if (A[right_child_index] > A[largest]) {

largest = right_child_index;

}
 // largest is not the node, node is not a heap

if (largest != index) {

swap(&A[index], &A[largest]);

max_heapify(A, largest);

void build_max_heap(int A[]) {

int i;

for(i=heap_size/2; i>=1; i--) {

max_heapify(A, i);

int maximum(int A[]) {

return A[1];

int extract_max(int A[]) {

int maxm = A[1];

A[1] = A[heap_size];

heap_size--;

max_heapify(A, 1);

return maxm;

void increase_key(int A[], int index, int key) {

A[index] = key;

while((index>1) && (A[get_parent(A, index)] < A[index])) {

swap(&A[index], &A[get_parent(A, index)]);

index = get_parent(A, index);

void decrease_key(int A[], int index, int key) {

 A[index] = key;

max_heapify(A, index);

void insert(int A[], int key) {

heap_size++;

A[heap_size] = -1*INF;

increase_key(A, heap_size, key);

void print_heap(int A[]) {

int i;

for(i=1; i<=heap_size; i++) {

printf("%d\n",A[i]);

printf("\n");

int main() {

int A[tree_array_size];

insert(A, 20);

insert(A, 15);

insert(A, 8);

insert(A, 10);

insert(A, 5);

insert(A, 7);

insert(A, 6);

insert(A, 2);

insert(A, 9);

insert(A, 1);

print_heap(A);

increase_key(A, 5, 22);

print_heap(A);
decrease_key(A, 1, 13);

print_heap(A);

printf("%d\n\n", maximum(A));

printf("%d\n\n", extract_max(A));

print_heap(A);

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

printf("%d\n", extract_max(A));

return 0;

⇨ OUTPUT:
LAB EXPERIMENT – 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 <bits/stdc++.h>

using namespace std;

// function to add an edge from vertex source to vertex dest

void addEdge(vector<int> adj[], int src, int dest)

adj[src].push_back(dest);

// function to print adjacency list of a graph

void displayGraph(vector<int> adj[], int v)

for (int i = 0; i < v; i++) {

cout << i << "--> ";

for (int j = 0; j < adj[i].size(); j++)

cout << adj[i][j] << " ";

cout << "\n";

// function to get Transpose of a graph taking adjacency

// list of given graph and that of Transpose graph

void transposeGraph(vector<int> adj[],

vector<int> transpose[], int v)

// traverse the adjacency list of given graph and

// for each edge (u, v) add an edge (v, u) in the

// transpose graph's adjacency list

for (int i = 0; i < v; i++)

for (int j = 0; j < adj[i].size(); j++)

addEdge(transpose, adj[i][j], i);

int main()
{

int v = 5;

vector<int> adj[v];

addEdge(adj, 0, 1);

addEdge(adj, 0, 4);

addEdge(adj, 0, 3);

addEdge(adj, 2, 0);

addEdge(adj, 3, 2);

addEdge(adj, 4, 1);

addEdge(adj, 4, 3);

// Finding transpose of graph represented

// by adjacency list adj[]

vector<int> transpose[v];

transposeGraph(adj, transpose, v);

// displaying adjacency list of transpose

// graph i.e. b

displayGraph(transpose, v);

return 0;

⇨ OUTPUT:

LAB EXPERIMENT -11

⇨ IMPLEMENT QUICK SORT.
#include <bits/stdc++.h>
using namespace std;

// A utility function to swap two elements

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]; // pivot
int i = (low - 1); // Index of smaller element and indicates the right position
of pivot found so far

for (int j = low; j <= high - 1; j++)

{
// If current element is smaller than the pivot
if (arr[j] < pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

/* The main function that implements QuickSort

arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);

// Separately sort elements before

// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

/* Function to print an array */

void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

int main()
{
int arr[] = {10, 7, 8, 9, 1, 2, 11, 15, 20, 5};
int n = sizeof(arr) / sizeof(arr[0]);
 quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
⇨ OUTPUT:

⇨ IMPLEMENT INSERTION SORT.

#include <bits/stdc++.h>
using namespace std;

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
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;
}
}

// A utility function to print an array of size n

void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main()
{
int arr[] = { 12, 11, 13, 5, 6, 1, 3, 4, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
 insertionSort(arr, n);
printArray(arr, n);

return 0;
}

⇨ OUTPUT:

⇨ IMPLEMENT SELECTION SORT.

#include <bits/stdc++.h>

using namespace std;

void swap(int *xp, int *yp)

int temp = *xp;

*xp = *yp;

*yp = temp;

void selectionSort(int arr[], int n)

int i, j, min_idx;

// One by one move boundary of unsorted subarray

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

// Find the minimum element in unsorted array

min_idx = i;

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

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

min_idx = j;
 // Swap the found minimum element with the first element

swap(&arr[min_idx], &arr[i]);

/* Function to print an array */

void printArray(int arr[], int size)

int i;

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

cout << arr[i] << " ";

cout << endl;

int main()

int arr[] = {64, 25, 12, 22, 11, 1, 5, 10, 15};

int n = sizeof(arr)/sizeof(arr[0]);

selectionSort(arr, n);

cout << "Sorted array: \n";

printArray(arr, n);

return 0;

⇨ OUTPUT:

⇨ IMPLEMENT MERGE SORT.

#include <iostream>
using namespace std;
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;

// Create temp arrays

int L[n1], R[n2];

// Copy data to temp arrays L[] and R[]

for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temp arrays back into arr[l..r]

// Initial index of first subarray

int i = 0;

// Initial index of second subarray

int j = 0;

// Initial index of merged subarray

int k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of

// L[], if there are any
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

// Copy the remaining elements of

// R[], if there are any
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[],int l,int r){
if(l>=r){
return;//returns recursively
}
int m =l+ (r-l)/2;
mergeSort(arr,l,m);
mergeSort(arr,m+1,r);
merge(arr,l,m,r);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7, 1, 20, 15, 3 };
int arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is \n";

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";

printArray(arr, arr_size);
return 0;
}

⇨ OUTPUT: