S.

NO DATE TABLE OF CONTENTS PAGE SIGNATURE

NO

1 Write a program to implement the List

ADT using arrays and linked lists.

2 Write a program to implement the

Stack ADT using arrays and linked
lists.

3 Write a program to implement the

Queue ADT using arrays and linked
list.

Write a program that reads an infix

expression, converts the expression to
4
postfix form and then evaluates the
postfix expression (use stack ADT).

Write a program to perform the

following operations:
 Insert an element into a Doubly
5 Linked List.
 Delete an element from a Doubly
Linked List.
 Search for a key element in a
Doubly Linked List.
 Write a program to perform the
following operations:
 Insert an element into a binary
search tree.
 Delete an element from a binary
6 search tree.
 Inorder, preorder and postorder
Traversals of a binary search
tree.
Write a programs for the
implementation of BFS and DFS for a
7
given graph.

Write a programs for implementing

the following searching methods:
8
 Linear search
 Binary search

Write a programs for implementing

the following sorting methods:
9
 Bubble sort
 Selection sort
 Insertion sort
EX.NO:01
Write a program to implement the List ADT using arrays and linked
DATE: lists.

AIM:

To write a program to implement the List ADT using arrays and

linked lists.

ALGORITHM:

Step 1: Start the program

Step 2: Initialize the array with dummy data.

Step 3: Write the struct node.

Step 4: Iterate over the array.

Step 5: Create a new node with the data.

Step 6: Insert the new node into the linked list.

Step 7: Print the linked list

Step 8: Finally stop the program.

PROGRAM:
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node* next;
};
struct Node* newNode(int data)
{
Node* node = new Node;
node->data = data;
node->next = NULL;
return node;
}
void insertNewNode(Node** root, int data)
{
Node* node = newNode(data);
Node* ptr;
if (*root == NULL)
{
*root = node;
}
else
{
ptr = *root;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
ptr->next = node;
}
}
void printLinkedList(Node* root)
{
while (root != NULL)
{
cout << root->data << " -> ";
root = root->next;
}
cout << "NULL" << endl;
}
Node* createLinkedList(int arr[], int n)
{
Node *root = NULL;
for (int i = 0; i < n; i++)
{
Insert NewNode(&root, arr[i]);
}
return root;
}
int main()
{
Int arr[]={1,2,3,4,5},n=5;
Node* root = createLinkedList(arr, n);
printLinkedList(root);
return 0;
}

OUTPUT:
RESULT:
Thus, the program has been completed and verified successfully.
EX.NO:02
Write a program to implement the Stack ADT using arrays and linked
DATE: lists.

AIM:
Write a program to implement the Stack ADT using arrays and linked
lists.

ALGORITHM:

Step 1: Start the program

Step 2: Push () to insert data into the stack

Step 3: Pop () to remove/delete data from the stack

Step 4: is Empty () to check whether a stack is empty or not

Step 5: is Full () to check whether a stack is full or not

Step 6: Peek () is used to check data at a particular index

Step 7: Stack Top () is used to find what is at the top of the stack

Step 8: Stop the Program.

PROGRAM:

#include <iostream>
Using namespace std;
int stack[100], n=100, top=-1; void push(int val)
{
if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else
{
top++;
stack[top]=val;
}
}
void pop()
{
if(top<=-1)
cout<<"Stack Underflow"<<endl;
else
{
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
}
void display()
{
if(top>=0)
{
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<<stack[i]<<" ";
cout<<endl;
}
else
cout<<"Stack is empty";
}
int main()
{
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do
{
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch)
{
case 1:
{
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
cout<<"Exit"<<endl;
break;
}
default:
{
cout<<"Invalid Choice"<<endl;
}
}
}
while(ch!=4);
return 0;
}

OUTPUT:

1) Push in stack
2) Pop from stack
3) Display stack
4) Exit

Enter choice: 1

Enter value to be pushed: 2

Enter choice: 1

Enter value to be pushed: 6

Enter choice: 1

Enter value to be pushed: 8

Enter choice: 1

Enter value to be pushed: 7

RESULT:
Thus, the program has been completed and verified successfully.
EX.NO: 03
Write a program to implement the Queue ADT using arrays and linked
DATE: list.

AIM:

Write a program to implement the Queue ADT using arrays and linked
list.

ALGORITHM:
1. First, we initialize the Node class which is the main element of our
linked list, a node contains a variable to store data and a pointer to the next
node.
2. Algorithm for Enqueue: -

Return Queue full

Else
Rear+Rear+1
Queue [Rear] =Data
If(Front== -1)
Front= 0

3. Algorithm for Dequeue: -

If(Front==-1||Front==Rear+1)
Return
Else
Queue[Front]=0
Front=Front+1 6. START the program.
4. Stop the program.
PROGRAM:
#include <iostream>

Using namespace std;

int queue[50];
int n = 50; int front = - 1; int rear = - 1;

void Queue_insertion()

int val;

if (rear == n - 1)

cout<<"Queue Overflow"<<endl;

else

front = 0;

cout<<" insert value in the queue : "<<endl;

cin>>val;

rear++;

queue[rear] = val;

void Delete()

if (front == - 1)
{

cout<<"Queue Underflow ";

return ;

else

cout<<"Element deleted from queue is : "<< queue[front] <<endl;

front++;

void Display_Queue ()

if (front == - 1 )
cout<<"Queue is empty"<<endl;

else

cout<<"Queue elements are : ";

for (int i = front; i <= rear; i++)

cout<<queue[i]<<" ";

cout<<endl;

int main()
{

int ch;

cout<<"1) insertion element to the queue"<<endl;

cout<<"2) Delete element from queue"<<endl;

cout<<"3) Display all the elements of queue"<<endl;

cout<<"4) Exit"<<endl;

do

cout<<"Enter your choice : "<<endl;

cin>>ch;

switch (ch)

case 1: Queue_insertion();

break;

case 2:

Delete();

break;

case 3:

Display_Queue ();

break;

case 4:
cout<<"Exit"<<endl;

break;
default: cout<<"Invalid choice"<<endl;
}

while(ch!=4);

return 0;

OUTPUT:
RESULT:
Thus, the program has been completed and verified successfully.
EX.NO: 04
Write a program that reads an infix expression, converts the expression
DATE: to postfix form and then evaluates the postfix expression (use stack
ADT).

AIM:
Write a program that reads an infix expression, converts the
expression to postfix form and then evaluates the postfix expression (use
stack ADT).

ALGORITHM:

STEP 1: Start the program

STEP 2: Scan the infix expression from left to right.
STEP 3: If the scanned character is an operand, put it in the postfix
expression.
STEP 4: f the scanned character is a ‘(‘, push it to the stack.
STEP 5: If the scanned character is a ‘)’, pop the stack and output it until a
‘(‘is encountered, and discard both the parenthesis.
STEP 6: Repeat steps 2-5 until the infix expression is scanned.
STEP 7: Once the scanning is over, Pop the stack and add the operators in
the postfix expression until it is not empty.
STEP 8: Finally, print the postfix expression.
STEP 9: Stop the program.
PROGRAM:

#include <bits/stdc++.h>
using namespace std;
int prec(char c)
{
if (c == '^')
return 3;
else if (c == '/' || c == '*')
return 2;
else if (c == '+' || c == '-')
return 1;
else
return -1;
}
char associativity(char c)
{
if (c == '^')
return 'R';
return 'L'; }
void infixToPostfix(string s)
{
stack<char> st;
string result;
for (int i = 0; i < s.length(); i++)
{
char c = s[i];
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
result += c;
else if (c == '(')
st.push('(');
else if (c == ')')
{
while (st.top() != '(')
{
result += st.top();
st.pop();
}
st.pop();
}
else
{
while (!st.empty() && prec(s[i]) < prec(st.top()) ||
!st.empty() && prec(s[i]) == prec(st.top()) &&
associativity(s[i]) == 'L')
{
result += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty())
{
result += st.top();
st.pop();
}
cout << result << endl;
}
int main()
{
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixtopostfix(exp);
return 0;
}

OUTPUT:

abcd^e-fgh*+^*+i-
RESULT:
Thus, the program has been completed and verified successfully.
EX.NO:05 Write a program to perform the following operations:
1) Insert an element into a Doubly Linked List.
DATE: 2) Delete an element from a Doubly Linked List.
3) Search for a key element in a Doubly Linked List.

AIM:
Write a program to perform the following operations:
1) Insert an element into a Doubly Linked List.
2) Delete an element from a Doubly Linked List.
3) Search for a key element in a Doubly Linked List.

ALGORITHM:

STEP 1: START the program

STEP 2: Create a new node with three variables: prev, data, next.

STEP 3: Store the new data in the data variable

STEP 4: If the list is empty, make the new node as head.

STEP 5: Otherwise, link the address of the existing first node to the

Next variable of the new node, and assign null to the prev variable.

STEP 6: Point the head to the new node.

STEP 7: END the program.

PROGRAM:

1) Insert an element into a Doubly Linked List.

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdbool>

struct node

int data;

int key;

struct node *next;

struct node *prev;

};

struct node *head = NULL;

struct node *last = NULL;

struct node *current = NULL;

bool isEmpty()

return head == NULL;

void printList()

struct node *ptr = head;

while(ptr != NULL)

printf("(%d,%d) ",ptr->key,ptr->data);

ptr = ptr->next;

void insertFirst(int key, int data)

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

link->key = key;

link->data = data;

if(isEmpty()

last = link;

else

head->prev = link;

link->next = head;

head = link;

}
int main()

insertFirst(1,10);

insertFirst(2,20);

insertFirst(3,30);

insertFirst(4,1);

insertFirst(5,40);

insertFirst(6,56);

printf("Doubly Linked List: ");

printList();

return 0;

OUTPUT:

Doubly Linked List: (6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1,10)
 2) Delete an element from a Doubly Linked List.

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdbool>

struct node

int data;

int key;

struct node *next;

struct node *prev;

};

struct node *head = NULL;

struct node *last = NULL;

struct node *current = NULL;

bool isEmpty()

return head == NULL;

void printList()

{
struct node *ptr = head;

while(ptr != NULL)

printf("(%d,%d) ",ptr->key,ptr->data);

ptr = ptr->next;

void insertFirst(int key, int data)

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

link->key = key;

link->data = data;

if(isEmpty())

last = link;

Else

head->prev = link;

link->next = head;

head = link;
}

struct node* deleteFirst()

struct node *tempLink = head;

if(head->next == NULL)

last = NULL;

else

head->next->prev = NULL;

head = head->next;

return tempLink;

int main()

insertFirst(1,10);

insertFirst(2,20);

insertFirst(3,30);

insertFirst(4,1);

insertFirst(5,40);
insertFirst(6,56);

printf("Doubly Linked List: \n");

printList();

printf("\nList after deleting first record: \n");

deleteFirst();

printList();

return 0;

OUTPUT:
Doubly Linked List:
(6, 56) (5, 40) (4, 1) (3, 30) (2, 20) (1, 10)
List after deleting first record:
(5, 40) (4, 1) (3, 30) (2, 20) (1, 10)
 3) Search for a key element in a Doubly Linked List.
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node* next;
Node* prev;
};
void push(Node** head_ref, int new_data)
{
Node* new_node= (Node*)malloc(sizeof(struct Node));
new_node->data = new_data;

new_node->prev = NULL;

ew_node->next = (*head_ref);

if ((*head_ref) != NULL)
{
(*head_ref)->prev = new_node;
}
(*head_ref) = new_node;
}
int search(Node** head_ref, int x)
{
Node* temp = *head_ref;
int pos = 0;
while (temp->data != x&& temp->next != NULL)
{
pos++;
temp = temp->next;
}
if (temp->data != x)
return -1;
return (pos + 1);
}
int main()
{
Node* head = NULL;
int X = 8;
push(&head, 14);
push(&head, 9);
push(&head, 8);
push(&head, 15);
push(&head, 18);
cout << search(&head, X);
return 0;
}

OUTPUT:
3
RESULT:
Thus, the program has been completed and verified successfully.
EX.NO:06 Write a program to perform the following operations:
1) Insert an element into a binary search tree.
DATE: 2) Delete an element from a binary search tree.
3) Inorder, preorder and postorder Traversals of a binary search
tree.
AIM:

Write a program to perform the following operations:

1) Insert an element into a binary search tree.
2) Delete an element from a binary search tree.
3) Inorder, preorder and postorder Traversals of a binary search tree.

ALGORITHM:
STEP 1: Start the program
STEP 2: If the tree is empty, insert the first element as the root node of
the tree. The following elements are added as the leaf nodes.

STEP 3: If an element is less than the root value, it is added into the left

Sub tree as a leaf node.

STEP 4: If an element is greater than the root value, it is added into the
right

Sub tree as a leaf node.

STEP 5: The final leaf nodes of the tree point to NULL values as their

Child nodes.

STEP 6: Stop the program.

PROGRAM:
1) Insert an element into a binary search tree.
#include <iostream>

using namespace std;

struct node

int data;

struct node *leftChild, *rightChild;

};

struct node *root = NULL;

struct node *newNode(int item)

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

temp->data = item;

temp->leftChild = temp->rightChild = NULL;

return temp;

void insert(int data)

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

struct node *current;

struct node *parent;

tempNode->data = data;
tempNode->leftChild = NULL;

tempNode->rightChild = NULL;

if(root == NULL)

root = tempNode;

else

current = root;

parent = NULL;

while(1)

parent = current;

if(data < parent->data)

current = current->leftChild;

if(current == NULL)

parent->leftChild = tempNode;

return;

}
else

current = current->rightChild;

if(current == NULL)

parent->rightChild = tempNode;

return;

void printTree(struct node* Node)

if(Node == NULL)

return;

printTree(Node->leftChild);

cout<<" --"<<Node->data;

printTree(Node->rightChild);

int main()

{
insert(55);

insert(20);

insert(90);

insert(50);

insert(35);

insert(15);

insert(65);

cout<<"Insertion done\n";

cout<<"BST:"<<endl;

printTree(root);

return 0;

OUTPUT:

Insertion done
BST:
--15 --20 --35 --50 --55 --65 –90
2) Delete an element from a binary search tree.

#include<bits/stdc++.h>
using namespace std;
class Tree
{
public:
int data;
Tree *left = NULL, *right = NULL;
Tree (int x)
{
data = x;
left = NULL;
right = NULL;
}
};
Tree *Delete (Tree * root, int x)
{
if (root == NULL)
{
cout << "Node not found ";
return NULL;
}
if (root->data > x)
{
root->left = Delete (root->left, x);
}
else if (root->data < x)
{
root->right = Delete (root->right, x);
}
else
{
if (root->left == NULL)
{
Tree *temp = root->right;
free (root);
return temp;
}
else if (root->right == NULL)
{
Tree *temp = root->left;
free (root);
return temp;
}
else
{
Tree *temp = root->right;
while (temp->left != NULL)
temp = temp->left;
root->data = temp->data;
root->right = Delete (root->right, temp->data);
}
}
return root;
}
void inorder_traversal (Tree * root)
{
if (root == NULL)
return;
inorder_traversal (root->left);
cout << root->data << " ";
inorder_traversal (root->right);
}
int main ()
{
Tree *root = new Tree (15);
root->left = new Tree (13);
root->right = new Tree (18);
root->left->left = new Tree (8);
root->left->right = new Tree (14);
root->right->left = new Tree (16);
root->right->right = new Tree (19);
cout << "Inorder Traversal of the Binary Search Tree:";
inorder_traversal (root);
cout << endl;
cout << "Value to be deleted : 18 \n";
Delete (root, 18);
cout << "Inorder Traversal :";
inorder_traversal (root);
cout << endl;
}

OUTPUT:

Inorder Traversal of the Binary Search Tree: 8 13 14 15 16 18 19

Value to be deleted: 18
Inorder Traversal: 8 13 14 15 16 19
3) Inorder, preorder and postorder Traversals of a binary search tree.

#include<bits/stdc++.h>
using namespace std;
class Tree
{
public:
int data;
Tree *left = NULL, *right = NULL;
Tree (int x)
{
data = x;
left = NULL;
right = NULL;
}
};
void preorder_traversal (Tree * root)
{
if (root == NULL)
return;
cout << root->data << " ";
preorder_traversal (root->left);
preorder_traversal (root->right);
}
void inorder_traversal (Tree * root)
{
if (root == NULL)
return;
inorder_traversal (root->left);
cout << root->data << " ";
inorder_traversal (root->right);
}
void postorder_traversal (Tree * root)
{
if (root == NULL)
return;
postorder_traversal (root->left);
postorder_traversal (root->right);
cout << root->data << " ";
}
int main ()
{
Tree *root = new Tree (17);
root->left = new Tree (10);
root->right = new Tree (11);
root->left->left = new Tree (7);
root->right->left = new Tree (27);
root->right->right = new Tree (9);
cout << "Preorder => ";
preorder_traversal (root);
cout << endl;
cout << "Inorder => ";
inorder_traversal (root);
cout << endl;
cout << "Postorder => ";
postorder_traversal (root);
cout << endl;
return 0;
}

OUTPUT:

Preorder => 17 10 7 11 27 9
Inorder => 7 10 17 27 11 9
Postorder => 7 10 27 9 11 17
RESULT:
Thus, the program has been completed and verified successfully.
EX.NO: 07
Write a programs for the implementation of BFS and DFS for a given
DATE:
graph.

AIM:

To write a program for the implementation of BFS and DFS for a given graph.

ALGORITHM:

Algorithm for BFS:

1. Take the empty queue and bool type array (visit) initialize with FALSE.
2. Push the starting node in the queue and set the value TRUE for this node
in visited array.
3. Pop out the front node of the queue and print the node.
4. Push the adjacent node of pop node in queue which are not visited. Set
the value TRUE in visited array of adding node.
5. Repeat step 3 and 4 until the queue becomes empty.
Algorithm for DFS:

1. Take the empty stack and bool type array (visit) initialize with FALSE.
2. Push the starting node in the stack and set the value TRUE for this node
in visited array.
3. Pop the top node from the stack and print that node.
4. Push the adjacent node of pop node in the stack which is not visited. Set
the value TRUE in visited array of adding node.
5. Repeat step 3 and 4until the stack becomes empty.
PROGRAM:

#include<iostream.h>

#include<vector>

#include<queue>

#include<stack>

using namespace std;

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

adj[u].push_back(v);

void bfs(int s,vector<int>adj[],bool visit[])

queue<int>q;

q.push(s);

visit[s]=true;

while(!q.empty())

int u=q.front();

cout<<u<<" ";

q.pop();

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

if(!visit[adj[u][i]])

q.push(adj[u][i]);

visit[adj[u][i]]=true;

void dfs(int s,vector<int>adj[],bool visit[])

stack<int>stk;

stk.push(s);

visit[s]=true;

while(!stk.empty())

int u=stk.top();

cout<<u<<" ";

stk.pop();

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

if(!visit[adj[u][i]])
{

stk.push(adj[u][i]);

visit[adj[u][i]]=true;

int main()

vector<int>adj[5];

bool visit[5];

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

visit[i]=false;

edge(adj,0,2);

edge(adj,0,1);

edge(adj,1,3);

edge(adj,2,0);

edge(adj,2,3);

edge(adj,2,4);

cout<<"BFS traversal is"<<" ";

bfs(0,adj,visit);

cout<<endl;

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

visit[i]=false;

cout<<"DFS traversal is"<<" ";

dfs(0,adj,visit);

}
OUTPUT:

BFS traversal is 0 2 1 3 4
DFS traversal is 0 1 3 2 4
RESULT:
Thus, the program has been completed and verified successfully.
EX.NO:08 Write a programs for implementing the following searching methods:
1) Linear search
DATE:
2) Binary search

AIM:

Write a programs for implementing the following searching methods:

1) Linear search
2) Binary search

ALGORITHM:

Linear search:

Step 1 – start the program and read the search element from the user.
Step 2 - Compare the search element with the first element in the list.
Step 3 - If both are matched, then display "Given element is found!!!"
and terminate the function

Step 4 - If both are not matched, then compare the search element with
the next element in the list.

Step 5 - Repeat steps 3 and 4 until the search element is compared with
the last element in the list.

Step 6 - If the last element in the list also doesn't match, then display
"Element is not found!!!" and terminate the function.

Step 7-stop the program.

Binary search:

Step 1 - start the program and read the search element from the user.

Step 2 - Find the middle element in the sorted list.

Step 3 - Compare the search element with the middle element in the
sorted list.

Step 4 - If both are matched, then display "Given element is found!!!"

and terminate the function.

Step 5 - If both are not matched, then check whether the search element
is smaller or larger than the middle element.
Step 6 - If the search element is smaller than the middle element, repeat
steps 2, 3, 4 and 5 for the left sub-list of the middle element.

Step 7 - If the search element is larger than the middle element, repeat
steps 2, 3, 4 and 5 for the right sub-list of the middle element.

Step 8 - Repeat the same process until we find the search element in the
list or until the sub-list contains only one element.

Step 9 - If that element also doesn't match with the search element, then
display "Element is not found in the list!!!" and terminate the function.

Step 10: Finally stop the program.

PROGRAM:

1) Linear search:

#include <bits/stdc++.h>

using namespace std;

int search(int arr[], int N, int x)

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

if (arr[i] == x)

return i;

return -1;

int main(void)

int arr[] = { 2, 3, 4, 10, 40 };

int x = 10;

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

int result = search(arr, N, x);

(result == -1)

cout << "Element is not present in array"

cout << "Element is present at index " << result;

return 0;

}
OUTPUT:

Element is present at index 3

 2) Binary search:

#include <bits/stdc++.h>

using namespace std;

int binary search(int arr[], int l, int r, int x)

while (l <= r)

int m = l + (r - l) / 2;

if (arr[m] == x)

return m;

if (arr[m] < x)

l = m + 1;

else

r = m - 1;

return -1;

int main(void)

int arr[] = { 2, 3, 4, 10, 40 };

int x = 10;

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

int result = binary search(arr, 0, n - 1, x);

(result == -1)

cout << "Element is not present in array"

cout << "Element is present at index " << result;

return 0;

OUTPUT:

Element is present at index 3

RESULT:
Thus, the program has been completed and verified successfully.
EX.NO: 09 Write a programs for implementing the following sorting methods:
1) Bubble sort
DATE: 2) Selection sort
3) Insertion sort

AIM:

Write a programs for implementing the following sorting methods:

1) Bubble sort
2) Selection sort
3) Insertion sort

ALGORITHM:

1) Bubble sort

Step 1 − Check if the first element in the input array is greater than the next
element in the array.

Step 2 − If it is greater, swap the two elements; otherwise move the pointer
forward in the array.

Step 3 − Repeat Step 2 until we reach the end of the array.

Step 4 − Check if the elements are sorted; if not, repeat the same process (Step
1 to Step 3) from the last element of the array to the first.

Step 5 − The final output achieved is the sorted array.

PROGRAM:
Bubble sort:

#include <bits/stdc++.h>
using namespace std;
void bubbleSort(int arr[], int n)
{
int i, j;
bool swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (swapped == false)
break;
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << " " << arr[i];
}
int main()
{
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
cout << "Sorted array: \n";
printArray(arr, N);
return 0;
}

OUTPUT:

Sorted array:
11 12 22 25 34 64 90
2) Selection sort

Step 1- Start the program and set MIN to location 0.

Step 2- Search the minimum element in the list.

Step 3- Swap with value at location MIN.

Step 4 - Increment MIN to point to the next element.

Step 5 - Repeat until the list is sorted.

Step 6 - Finally stop the program.

PROGRAM:

Selection sort

#include <bits/stdc++.h>

using namespace std;

void selectionSort(int arr[], int n)

int i, j, min_idx;

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

min_idx = i;

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

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

min_idx = j;

if (min_idx != i)

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

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 };

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

selectionsort(arr, n);

cout << "Sorted array: \n";

printArray(arr, n);

return 0;

}
OUTPUT:

Sorted array:
112 22 25 64
3) Insertion Sort:
Step 1 −Start the program and if it is the first element, it is already sorted.
Return 1;

Step 2 − Pick the next element

Step 3 − Compare with all elements in the sorted sub-list

Step 4 − Shift all the elements in the sorted sub-list that is greater than the
value to be sorted

Step 5 − Insert the value

Step 6 − Repeat until the list is

sorted

Step 7- Stop the program.

PROGRAM:

Insertion Sort:
#include <bits/stdc++.h>

using namespace std;

void insertionsort(int arr[], int n)

int i, key, j;

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

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key)

arr[j + 1] = arr[j];

j = j - 1;

arr[j + 1] = key;

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 };

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

insertionSort(arr, N);

printArray(arr, N);

return 0;

}
OUTPUT:

5 6 11 12 13
RESULT:
Thus, the program has been completed and verified successfully.
SKP ARTS & SCIENCE COLLEGE (Co-Ed)
(Affiliated to Thiruvalluvar University, Vellore)

DEPARTMENT OF COMPUTER SCIENCE

REGISTER NUMBER : _________________________________

STUDENT NAME : _________________________________

SEMESTER : _________________________________

YEAR : _________________________________

SUBJECT NAME : _________________________________

 SKP ARTS & SCIENCE COLLEGE (Co-Ed)
(Affiliated to Thiruvalluvar University, Vellore)

DEPARTMENT OF COMPUTER SCIENCE

CERTIFICATE
This is to certify that, this is a bonafide record work done by Mr. / Ms.

______________________________________ Register Number _________________________

Semester ________________ Year _________________________.

Staff In-Charge Head of the Department

Submitted to Thiruvalluvar University ______________________________________

Practical Examination held on _____________________.

Internal Examiner External Examiner