INDEX

[Link] DATE TITLE PAGE NO SIGNATURE

I. To implement the
1 List ADT using
Arrays.

II. To implement the

List ADT using
Linked Lists.

2 I. Stack ADT.
II. Queue ADT.

3 The expression to postfix

form and then evaluates
the postfix expression
(use stack ADT).

4 Write a program to
implement priority queue
ADT.

5 I. Insert an element
into a binary search tree
 II. Delete an element
from a binary search tree.

III. Search for a key element

in a binary search tree.

I. Insertion into an AVL-

6 tree.

II. Deletion from an AVL-

tree.

7 The implementation of BFS

and DFS for a given graph.

8 I. Linear search.

II. Binary search.

9 I. Bubble sort.

II. Selection sort.

III. Insertion sort.

IV. Radix sort.

[Link] : 1 Write a program to implement the List ADT using arrays and linked lists.

[Link] implement the List ADT using Arrays.

Aim :

To write a C program to implement the List ADT using arrays.

Algorithm :

Step 1 : Start the Program.

Step 2 : Declare the functions create(), insert(), delete(), search() and display()

Step 3 : Call the declared functions using the switch – case statements.

Step 4 : Under the create() function, have to enter the number of nodes and the list of
elements to be added.

Step 5 : Under the delete() function, have to enter the position of the element to get
deleted. If the position is not available then have to display it is invalid position.

Step 6 : Under the search() function, have to search the element with its position.

Step 7 : Under the insert() function, have to insert the new element by comparing the
maximum size of the list.

Step 8 : Inside display() function, have to display the List after completing all the
operations.

Step 9 : Execute the program.

Program:

#include<stdio.h>
#include<conio.h>
#define MAX 10
void create();
void insert();
void deletion();
void search();
void display();
int a,b[20], n, p, e, f, i, pos;

int main()
{
//clrscr();
int ch;
char g='y';

do
{
printf("\n main Menu");
printf("\n [Link] \n [Link] \n [Link] \n [Link] \n [Link] \n");
printf("\n Enter your Choice");
scanf("%d", &ch);

switch(ch)
{
case 1:
create();
break;

case 2:
deletion();
break;

case 3:
search();
break;

case 4:
insert();
break;

case 5:
display();
break;

default:
printf("\n Enter the correct choice:");
}
printf("\n Do u want to continue:::");
scanf("\n%c", &g);
}
while(g=='y'||g=='Y');
getch();
}

void create()
{
printf("\n Enter the number of nodes");
scanf("%d", &n);
for(i=0;i<n;i++)
{
printf("\n Enter the Element:",i+1);
scanf("%d", &b[i]);
}
}
void deletion()
{
printf("\n Enter the position u want to delete::");
scanf("%d", &pos);
if(pos>=n)
{
printf("\n Invalid Location::");
}
else
{
for(i=pos+1;i<n;i++)
{
b[i-1]=b[i];
}
n--;
}
printf("\n The Elements after deletion");
for(i=0;i<n;i++)
{
printf("\t%d", b[i]);
}
}

void search()
{
printf("\n Enter the Element to be searched:");
scanf("%d", &e);

for(i=0;i<n;i++)
{
if(b[i]==e)
{
printf("Value is in the %d Position", i);
}
else
{
printf("Value %d is not in the list::", e);
continue;
}
}
}
void insert()
{
printf("\n Enter the position u need to insert::");
scanf("%d", &pos);

if(pos>=n)
{
printf("\n invalid Location::");
}
else
{
for(i=MAX-1;i>=pos-1;i--)
{
b[i+1]=b[i];
}
printf("\n Enter the element to insert::\n");
scanf("%d",&p);
b[pos]=p;
n++;
}
printf("\n The list after insertion::\n");

display();
}
void display()
{
printf("\n The Elements of The list ADT are:");

for(i=0;i<n;i++)
{
printf("\n\n%d", b[i]);
}
}
Output:

main Menu
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

Enter your Choice1

Enter the number of nodes5

Enter the Element:2

Enter the Element:8

Enter the Element:9

Enter the Element:6

Enter the Element:4

Do u want to continue:::y

main Menu
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

Enter your Choice5

The Elements of The list ADT are:

4
Do u want to continue:::y
main Menu
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

Enter your Choice2

Enter the position u want to delete::4

The Elements after deletion 2 8 9 6

Do u want to continue:::y

main Menu
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

Enter your Choice3

Enter the Element to be searched:9

Value 9 is not in the list::Value 9 is not in the list::Value is in the 2 Positi
onValue 9 is not in the list::
Do u want to continue:::y

main Menu
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your Choice4
Enter the position u need to insert::2
Enter the element to insert::
8
The list after insertion::
The Elements of The list ADT are:

8
8

6
Do u want to continue:::y
main Menu
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

Enter your Choice6

Enter the correct choice:

Do u want to continue:::n

Result :

Thus the above program for implementing the List ADT using arrays has been
executed successful
 [Link] implement the List ADT using Linked Lists.

Aim :

To write a C program to implement the List ADT using Linked Lists.

Algorithm :

Step 1 : Start the program.

Step 2 : Define a Structure to declare the node and data to be inserted as Linked Lists
using struct keyword.

Step 3 : The functions create(), insert(), delete(), search() and display() are declared
using the defined structure.

Step 4 :Inside the create() function, have to create a new list by checking the size and t
the memory allocated using the sizeof operator.

Step 5 : The insert() function is used to insert the new node at the end of the list.

Step 6 : The display() function is used to display all the items in the list.

Step 7 : The freeList() function is used to free the occupied memory in the list.

Step 8 : Inside the main() function, all the declared functions has to be called by

passing the parameters.

Step 9 : Execute the program.

Program:

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

// Define a Node structure for the linked list

struct Node {
int data;
struct Node* next;
};

// Define a Stack structure

struct Stack {
struct Node* top;
};

// Function to create a new node with given data

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to initialize an empty stack

struct Stack* initializeStack() {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;
return stack;
}

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {
return (stack->top == NULL);
}

// Function to push an element onto the stack

void push(struct Stack* stack, int data) {
struct Node* newNode = createNode(data);
newNode->next = stack->top;
stack->top = newNode;
printf("%d pushed to the stack.\n", data);
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow. Cannot pop from an empty stack.\n");
return -1; // Return an indicator for an empty stack
}
 struct Node* temp = stack->top;
int poppedValue = temp->data;
stack->top = temp->next;
free(temp);

return poppedValue;
}

// Function to display the elements of the stack

void display(struct Stack* stack) {
struct Node* current = stack->top;
printf("Stack: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

// Main function to test the stack implementation

int main() {
struct Stack* stack = initializeStack();

push(stack, 10);
push(stack, 20);
push(stack, 30);

display(stack);

printf("Popped element: %d\n", pop(stack));

display(stack);

return 0;
}
Output:

10 pushed to the stack.

20 pushed to the stack.
30 pushed to the stack.
Stack: 30 20 10
Popped element: 30
Stack: 20 10

Result :

Thus the above program for implementing the List ADT using Linked Lists has been
executed successfully.
EX No: 2 Write a programs to implement the following using a singly linked list.

[Link] ADT.

Aim :

To write a C program to implement the Stack ADT using a Singly Linked List.

Algorithm :

Step 1 : Start the program.

Step 2 : Define a node and stack structure for the Linked list using the struct keyword.

Step 3 :Create a new node with the createNode() function by passing the data as an
argument.

Step 4 : Create a new empty stack by using the initializeStack() function and declare t
the stack value to NULL.

Step 5 : To check whether the stack is empty, declare the isEmpty() function and
return the NULL value if the stack is empty.

Step 6 : Insert the new element to the top of the Stack by using the push() function.

Step 7 : Delete an element from the non empty stack by using the pop() function and
return the deleted value.

Step 8 :The display() function is used to display the current elements of the stack.

Step 9 : Inside the main function, call all the declared functions by passing the
elements as an arguments.

Step 10 : Execute the program.

Program:

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

// Define a Node structure for the linked list

struct Node {
int data;
struct Node* next;
};

// Define a Stack structure

struct Stack {
struct Node* top;
};

// Function to create a new node with given data

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to initialize an empty stack

struct Stack* initializeStack() {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->top = NULL;
return stack;
}

// Function to check if the stack is empty

int isEmpty(struct Stack* stack) {
return (stack->top == NULL);
}

// Function to push an element onto the stack

void push(struct Stack* stack, int data) {
struct Node* newNode = createNode(data);
newNode->next = stack->top;
stack->top = newNode;
printf("%d pushed to the stack.\n", data);
}

// Function to pop an element from the stack

int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow. Cannot pop from an empty stack.\n");
return -1; // Return an indicator for an empty stack
}
 struct Node* temp = stack->top;
int poppedValue = temp->data;
stack->top = temp->next;
free(temp);

return poppedValue;
}

// Function to display the elements of the stack

void display(struct Stack* stack) {
struct Node* current = stack->top;
printf("Stack: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}

// Main function to test the stack implementation

int main() {
struct Stack* stack = initializeStack();

push(stack, 10);
push(stack, 20);
push(stack, 30);

display(stack);

printf("Popped element: %d\n", pop(stack));

display(stack);

return 0;
}
Output:

10 pushed to the stack.

20 pushed to the stack.
30 pushed to the stack.
Stack: 30 20 10
Popped element: 30
Stack: 20 10

Result :

Thus the above program for implementing the Stack ADT using a Singly Linked List
has been executed successfully.
 [Link] ADT.

Aim :

To write a C program to implement Queue ADT using a Singly Linked List.

Algorithm :

Step 1 : Start the program.

Step 2 :Define a node and queue structure for the Linked list using the struct keyword.

Step 3 :Create a new node with the createNode() function by passing the data as an
argument.

Step 4 : Create a new empty queue by using the initializeQueue() function and declare
the queue value to NULL.

Step 5 : To check whether the queue is empty, declare the isEmpty() function and
return the NULL value if the queue is empty.

Step 6 :Insert the new element to the Queue by using the enqueue() function.

Step 7 :Delete an element from the non emptyqueue by using the dequeue() function
and return the deleted value.

Step 8 : The front and rear are the key pointers to add and delete an element from the
queue.

Step 9 :The display() function is used to display the current elements of the queue.

Step 10 :Inside the main function, call all the declared functions by passing the
elements as an arguments.

Step 11 : Execute the program.

Program:

#include <stdio.h>
#include <stdlib.h>
// Define a Node structure for the linked list
struct Node {
int data;
struct Node* next;
};

// Define a Queue structure

struct Queue {
struct Node* front;
struct Node* rear;
};

// Function to create a new node with given data

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to initialize an empty queue

struct Queue* initializeQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = NULL;
queue->rear = NULL;
return queue;
}

// Function to check if the queue is empty

int isEmpty(struct Queue* queue) {
return (queue->front == NULL);
}

// Function to enqueue an element into the queue

void enqueue(struct Queue* queue, int data) {
struct Node* newNode = createNode(data);

if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
}

else
{
queue->rear->next = newNode;
queue->rear = newNode;
 }

printf("%d enqueued to the queue.\n", data);

}

// Function to dequeue an element from the queue

int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue underflow. Cannot dequeue from an empty queue.\n");
return -1; // Return an indicator for an empty queue
}

struct Node* temp = queue->front;

int dequeuedValue = temp->data;
queue->front = temp->next;

// If the queue becomes empty after dequeue, update rear

if (queue->front == NULL) {
queue->rear = NULL;
}

free(temp);
return dequeuedValue;
}
// Function to display the elements of the queue
void display(struct Queue* queue)
{
struct Node* current = queue->front;
printf("Queue: ");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// Main function to test the queue implementation
int main()
{
struct Queue* queue = initializeQueue();

enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);

display(queue);

printf("Dequeued element: %d\n", dequeue(queue));

display(queue);
return 0;
}
Output:

10 enqueued to the queue.

20 enqueued to the queue.
30 enqueued to the queue.
Queue: 10 20 30
Dequeued element: 10
Queue: 20 30

Result :

Thus the above program for implementing the Queue ADT using a Singly Linked List
has been executed successfully.
Ex. No : 3 Write a program that reads an infix expression, converts the
expression to postfix form and then evaluates the postfix
expression (use stack ADT).

Aim :

To write a C program to read an infix expression and converts into postfix and
evaluate the postfix expression using Stack ADT.

Algorithm :

Step 1 : Start the program.

Step 2 : The push() and pop() functions are used to insert and delete an element from t
the Stack.

Step 3 : The priority() function is used to check the priority of the operator that which
operator has to be performed first.

Step 4 :Check the priority of the operators using the ‘if’ condition.

Step 5 : Inside the main function, get the values in the runtime.

Step 6 : Evaluate the expression according to its priority using the ‘while’ condition.

Step 7 : Execute the program.

Program:

#include<stdio.h>
#include<ctype.h>
char stack[100];
int top = -1;

void push(char x)
{
stack[++top] = x;
}

char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}

int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return 0;
}

int main()
{
char exp[100];
char *e, x;

printf("Enter the expression : ");

scanf("%s",exp);
printf("\n");
e = exp;

while(*e != '\0')
{
if(isalnum(*e))
printf("%c ",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
 while((x = pop()) != '(')
printf("%c ", x);
}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c ",pop());
push(*e);
}
e++;
}

while(top != -1)
{
printf("%c ",pop());
}return 0;
}
Output:

Enter the expression : (a+b)*c+(d-a)

ab+c*da-+
--------------------------------
Process exited after 34.57 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program for converting an infix expression to postfix expression and
its evaluation using Stack ADT has been executed successfully.
Ex. No : 4 Write a program to implement priority queue ADT.

Aim :

To write a C program to implement the queue operations using the Priority Queue
ADT.

Algorithm :

Step 1 : Start the program.

Step 2 : Declare insert_by_priority() function to insert the elements into the Queue.

Step 3 : Declare delete_by_priority() function to delete an element from the Queue.

Step 4 :The create() function is used to create a priority queue.

Step 5 : The check() function is used to check the priority and place the element to be
inserted.

Step 6 : The display() function is used to display all the elements in the queue.

Step 7 : Execute the program.

Program:

#include <stdio.h>
#include <stdlib.h>
#define MAX 5
void insert_by_priority(int);
void delete_by_priority(int);
void create();
void check(int);
void display_pqueue();
int pri_que[MAX];
int front, rear;
void main()
{
int n, ch;
printf("\n1 - Insert an element into queue");
printf("\n2 - Delete an element from queue");
printf("\n3 - Display queue elements");
printf("\n4 - Exit");
create();
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);

switch (ch)
{
case 1:
printf("\nEnter value to be inserted : ");
scanf("%d",&n);
insert_by_priority(n);
break;
case 2:
printf("\nEnter value to delete : ");
scanf("%d",&n);
delete_by_priority(n);
break;
case 3:
display_pqueue();
break;

case 4:
exit(0);
default:
printf("\nChoice is incorrect, Enter a correct choice");
}
}
}
/* Function to create an empty priority queue */
void create()
{
front = rear = -1;
}

/* Function to insert value into priority queue */

void insert_by_priority(int data)
{
if (rear >= MAX - 1)
{
printf("\nQueue overflow no more elements can be inserted");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
pri_que[rear] = data;
return;
}
else
check(data);
rear++;
}

/* Function to check priority and place element */

void check(int data)
{
int i,j;

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

{
if (data >= pri_que[i])
{
for (j = rear + 1; j > i; j--)
{
pri_que[j] = pri_que[j - 1];
}
pri_que[i] = data;
return;
}
}
pri_que[i] = data;
}

/* Function to delete an element from queue */

void delete_by_priority(int data)
{
int i;
 if ((front==-1) && (rear==-1))
{
printf("\nQueue is empty no elements to delete");
return;
}

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

{
if (data == pri_que[i])
{
for (; i < rear; i++)
{
pri_que[i] = pri_que[i + 1];
}

pri_que[i] = -99;
rear--;

if (rear == -1)
front = -1;
return;
}
}
printf("\n%d not found in queue to delete", data);
}

/* Function to display queue elements */

void display_pqueue()
{
if ((front == -1) && (rear == -1))
{
printf("\nQueue is empty");
return;
}

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

{
printf(" %d ", pri_que[front]);
}

front = 0;
}
Output:

1 - Insert an element into queue

2 - Delete an element from queue
3 - Display queue elements
4 - Exit
Enter your choice : 1

Enter value to be inserted : 45

Enter your choice : 1

Enter value to be inserted : 56

Enter your choice : 1

Enter value to be inserted : 25

Enter your choice : 1

Enter value to be inserted : 65

Enter your choice : 1

Enter value to be inserted : 32

Enter your choice : 1

Enter value to be inserted : 89

Queue overflow no more elements can be inserted

Enter your choice : 2

Enter value to delete : 65

Enter your choice : 3

56 45 32 25
Enter your choice :

Result :

Thus the above program to implement the queue operations using the Priority Queue
ADT has been executed successfully.
Ex. No : 5 Write a program to perform the following operations.

I .Insert an element into a binary search tree.

Aim :

To write a C program to insert an element into a Binary Search Tree.

Algorithm :

Step 1 : Start the program.

Step 2 :Create a new Binary tree by using the newNode() function.

Step 3 : The inorder() function is used to traverse in the Binary search tree along with
their nodes.

Step 4 : The insert() function is used to insert the new element to the tree by checking
whether the tree is empty or not.

Step 5 : If the tree is empty, create the new tree otherwise add the elements to the tree
as its child nodes.

Step 6 : Inside the main() function, call the function along with its parameters.

Step 7 : Execute the program.

Program:

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

struct node {
int key;
struct node *left, *right;
};

// A utility function to create a new BST node

struct node *newNode(int item) {
struct node *temp = (struct node *) malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST

void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in BST */

struct node* insert(struct node* node, int key) {
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;

// Driver Program to test above functions

int main() {
struct node *root = NULL;
root = insert(root, 50);
 insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

// print inoder traversal of the BST

inorder(root);

return 0;
}
Output:

20 30 40 50 60 70 80
--------------------------------
Process exited after 0.03565 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program to insert an element into the Binary Search tree has been
executed successfully.
 [Link] an element from a binary search tree.

Aim :

To write a C program to delete an element from a Binary search tree.

Algorithm :

Step 1 : Start the program.

Step 2 :Create a new Binary tree by using the newNode() function.

Step 3 :The inorder() function is used to traverse in the Binary search tree along with
their nodes.

Step 4 :The insert() function is used to insert the new element to the tree by checking
whether the tree is empty or not.

Step 5 :If the tree is empty, create the new tree otherwise add the elements to the tree
as its child nodes.

Step 6 : The deleteNode() is used to delete the particular node from the

Binary search tree

Step 7 : The deleteNode() function has to be called recursively for deleting both the le
left and right nodes of the tree.

Step 8 : If both the left and right childs are empty, then return the root value.

Step 9 : Inside the main function, call all the functions along with its parameters.

Step 10 : Execute the program.

Program:

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

struct Node {
int key;
struct Node *left, *right;
};

// A utility function to create a new BST node

struct Node* newNode(int item)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST

void inorder(struct Node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in

* BST */
struct Node* insert(struct Node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;
}

/* Given a binary search tree and a key, this function

deletes the key and returns the new root */
struct Node* deleteNode(struct Node* root, int k)
{
// Base case
if (root == NULL)
return root;

// Recursive calls for ancestors of

// node to be deleted
if (root->key > k)
{
root->left = deleteNode(root->left, k);
return root;
}
else if (root->key < k)
{
root->right = deleteNode(root->right, k);
return root;
}

// We reach here when root is the node

// to be deleted.

// If one of the children is empty

if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// If both children exist

else

{
struct Node* succParent = root;

// Find successor
struct Node* succ = root->right;
while (succ->left != NULL)
{
succParent = succ;
succ = succ->left;
}

// Delete successor. Since successor

// is always left child of its parent
 // we can safely make successor's right
// right child as left of its parent.
// If there is no succ, then assign
// succ->right to succParent->right
if (succParent != root)
succParent->left = succ->right;
else
succParent->right = succ->right;

// Copy Successor Data to root

root->key = succ->key;

// Delete Successor and return root

free(succ);
return root;
}
}

// Driver Code
int main()
{

struct Node* root = NULL;

root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);

printf("Original BST: ");

inorder(root);

printf("\n\nDelete a Leaf Node: 20\n");

root = deleteNode(root, 20);
printf("Modified BST tree after deleting Leaf Node:\n");
inorder(root);

printf("\n\nDelete Node with single child: 70\n");

root = deleteNode(root, 70);
printf("Modified BST tree after deleting single child Node:\n");
inorder(root);

printf("\n\nDelete Node with both child: 50\n");

root = deleteNode(root, 50);
printf("Modified BST tree after deleting both child Node:\n");
inorder(root);

return 0;
}
Output:
Original BST: 20 30 40 50 60 70

Delete a Leaf Node: 20

Modified BST tree after deleting Leaf Node:
30 40 50 60 70

Delete Node with single child: 70

Modified BST tree after deleting single child Node:

30 40 50 60

Delete Node with both child: 50

Modified BST tree after deleting both child Node:
30 40 60
--------------------------------
Process exited after 0.03943 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program for deleting an element from the Binary search tree has been
executed successfully.
 III. Search for a key element in a binary search tree.

Aim :

To write a C program to search for a key element in a Binary Search Tree.

Algorithm :

Step 1 : Start the program.

Step 2 : Create a Binary Tree by declaring the TreeNode structure to declare both the r
root node and the child node.

Step 3 :The insertNode() function is used to insert the new elements to be added to the
Binary Search tree.

Step 4 :Initialise the root node value to NULL and add the elements to the tree by
using the ‘if’ condition.

Step 5 : The searchNode() function is used to search the particular element in the tree.

Step 6 : Inside the main function, get the choice has to be made in the runtime and
insertion and searching of elements functions can be performed using the
switch-case statements.

Step 7 : Execute the program.

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

struct TreeNode {
int data;
struct TreeNode *leftChildNode;
struct TreeNode *rightChildNode;
};
typedef struct TreeNode node;
node *rootNode = NULL;
/* Function to insert a node in a Binary search tree */
void insertNode(int i, node **n) {
if (*n == NULL) {
(*n) = (node*)malloc(sizeof(node));
(*n)->leftChildNode = NULL;
(*n)->rightChildNode = NULL;
(*n)->data = i;
}
else if ((*n)->data == i)
printf("\nThis value already exists in the tree!");
else if (i > (*n)->data)
insertNode(i, &((*n)->rightChildNode));
else
insertNode(i, &((*n)->leftChildNode));
}
/* End of insertNode() */

/* Function to search an element in a Binary search tree */

void searchNode(int i, node **n) {
if (*n == NULL)
printf("\nValue does not exist in tree!");
else if((*n)->data == i)
printf("\nValue found!");
else if(i > (*n)->data)
searchNode(i, &((*n)->rightChildNode));
else
searchNode(i, &((*n)->leftChildNode));
}

/* End of serachNode() */
/* The main() program begins */
int main()
{
int ch, num, num1;
do {
printf("\nSelect a choice from the menu below.");
printf("\n1. Insert a node.");
printf("\n2. Search for a node.");
printf("\nChoice: ");
 scanf("%d", &ch);
switch(ch) {
case 1:
printf("\nEnter an element: ");
scanf("%d", &num);
insertNode(num, &rootNode);
break;
case 2:
printf("\nEnter the element to be searched for: ");
scanf("%d", &num);
searchNode(num, &rootNode);
break;
default:
exit(0);
}
printf("\nIf you want to return to the menu, press 1.");
printf("\nChoice: ");
scanf("%d", &num);
} while(num == 1);
return 0;
}
Output:

Select a choice from the menu below.

1. Insert a node.
2. Search for a node.
Choice: 1

Enter an element: 45

If you want to return to the menu, press 1.

Choice: 1

Select a choice from the menu below.

1. Insert a node.
2. Search for a node.
Choice: 1

Enter an element: 24

If you want to return to the menu, press 1.

Choice: 1

Select a choice from the menu below.

1. Insert a node.
2. Search for a node.
Choice: 1

Enter an element: 85

If you want to return to the menu, press 1.

Choice: 1

Select a choice from the menu below.

1. Insert a node.
2. Search for a node.
Choice: 2

Enter the element to be searched for: 24

Value found!
If you want to return to the menu, press 1.
Choice:

Result :

Thus the above program to search for an element in a Binary search tree has been
excuted successfully.
Ex. No : 6 Write a program to perform the following operations.

[Link] into an AVL-tree.

Aim :

To write a C program to insert an element into an AVL tree.

Algorithm :

Step 1 : Start the program.

Step 2 :Create an AVL tree by using the node structure.

Step 3 : The height() function is used to get the height of the tree.

Step 4 : The max() function is used to get the maximum of two integers.

Step 5 : The newNode() function is used to allocate a new node with its left and right
pointers.

Step 6 : The rightRotate() and leftRotate() is used to rotate the tree and update the
height of the tree.

Step 7 : insert() function is used to insert a new element.

Step 8 :preOrder() is used to traverse along the tree.

Step 9 : Inside the main function, call all the functions.

Step 10 : Execute the program.

Program:

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

// An AVL tree node

struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};

// A utility function to get the height of the tree

int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum of two integers

int max(int a, int b)
{
return (a > b)? a : b;
}

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}

// A utility function to right rotate subtree rooted with y

// See the diagram given above.
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct 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;
}

// A utility function to left rotate subtree rooted with x

// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct 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 Balance factor of node N

int getBalance(struct Node *N)

{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

// Recursive function to insert a key in the subtree rooted

// with node and returns the new root of the subtree.
struct Node* insert(struct Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
 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 // Equal keys are not allowed in BST
return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then

// there are 4 cases

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

// A utility function to print preorder traversal

// of the tree.
// The function also prints height of every node
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

/* Driver program to test above function*/

int main()
{
struct Node *root = NULL;
/* Constructing tree given in the above figure */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

printf("Preorder traversal of the constructed AVL"

" tree is \n");
preOrder(root);

return 0;
}
Output:

Preorder traversal of the constructed AVL tree is

30 20 10 25 40 50
--------------------------------
Process exited after 0.01827 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program to insert an element into an AVL tree has been executed
successfully.
 [Link] from an AVL-tree.

Aim :

To write a C program to delete an element from an AVL tree.

Algorithm :

Step 1 : Start the program.

Step 2 :Create an AVL tree by using the node structure.

Step 3 :The height() function is used to get the height of the tree.

Step 4 :The max() function is used to get the maximum of two integers.

Step 5 :The newNode() function is used to allocate a new node with its left and right
pointers.

Step 6 :The rightRotate() and leftRotate() is used to rotate the tree and update the
height of the tree.

Step 7 :insert() function is used to insert a new element.

Step 8 :deleteNode() function is used to delete an element from the tree,

Step 9 : Check whether the nodes of the tree is balanced, using the getBalance()

function.

Step 10 : Inside the main() function, call all the values with its parameters.

Step 11 : Execute the program.

Program:

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

// An AVL tree node

struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};

// A utility function to get maximum of two integers

int max(int a, int b);

// A utility function to get height of the tree

int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get maximum of two integers

int max(int a, int b)
{
return (a > b)? a : b;
}

/* Helper function that allocates a new node with the given key and
NULL left and right pointers. */
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}

// A utility function to right rotate subtree rooted with y

// See the diagram given above.
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct 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;
}

// A utility function to left rotate subtree rooted with x

// See the diagram given above.
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct 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 Balance factor of node N

int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);

struct Node* insert(struct Node* node, int key)

{
/* 1. Perform the normal BST rotation */
if (node == NULL)
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 // Equal keys not allowed
return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),
height(node->right));

/* 3. Get the balance factor of this ancestor

node to check whether this node became
unbalanced */
int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

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

/* Given a non-empty binary search tree, return the

node with minimum key value found in that tree.
Note that the entire tree does not need to be
searched. */
struct Node * minValueNode(struct Node* node)
{
struct Node* current = node;
 /* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;

return current;
}

// Recursive function to delete a node with given key

// from subtree with given root. It returns root of
// the modified subtree.
struct Node* deleteNode(struct Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE

if (root == NULL)
return root;

// If the key to be deleted is smaller than the

// root's key, then it lies in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the

// root's key, then it lies in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is

// the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
{
struct Node *temp = root->left ? root->left :
root->right;

// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child

free(temp);
}
Else
 {
// node with two children: Get the inorder
// successor (smallest in the right subtree)
struct 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 then return

if (root == NULL)
return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE

root->height = 1 + max(height(root->left),
height(root->right));

// STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to

// check whether this node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

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

// A utility function to print preorder traversal of

// the tree.
// The function also prints height of every node

void preOrder(struct Node *root)

{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

/* Driver program to test above function*/

int main()
{
struct Node *root = NULL;

/* Constructing tree given in the above figure */

root = insert(root, 9);
root = insert(root, 5);
root = insert(root, 10);
root = insert(root, 0);
root = insert(root, 6);
root = insert(root, 11);
root = insert(root, -1);
root = insert(root, 1);
root = insert(root, 2);
printf("Preorder traversal of the constructed AVL " "tree is \n");
preOrder(root);
root = deleteNode(root, 10);
printf("\nPreorder traversal after deletion of 10 \n");
preOrder(root);
return 0;
}
Output:

Preorder traversal of the constructed AVL tree is

9 1 0 -1 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 9 5 2 6 11
--------------------------------
Process exited after 0.02419 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program for delete an element from the AVL tree has been executed
successful
Ex. No : 7 Write a programs for the implementation of BFS and DFS for a given
graph.

Aim :

To write a C program to implement the BFS and DFS for the graph.

Algorithm :

Step 1 : Start the program

Step 2 : Declare the functions like add(), bfs(), dfs(),push() and pop() to perform the
operations.

Step 3 : The bfs() function starts from the top node in the graph and travels down until
it reaches the root node.

Step 4 : The dfs() function starts from the top node and follows a path to reaches the e
end node of the path.

Step 5 : Execute the program.

Program:

#include<stdio.h>

int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int delete();
void add(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

void main()
{
int n,i,s,ch,j;
char c,dummy;
printf("ENTER THE NUMBER VERTICES ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("ENTER 1 IF %d HAS A NODE WITH %d ELSE 0 ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("THE ADJACENCY MATRIX IS\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n");
}

do
{
for(i=1;i<=n;i++)
vis[i]=0;
printf("\nMENU");
printf("\n1.B.F.S");
printf("\n2.D.F.S");
printf("\nENTER YOUR CHOICE");
scanf("%d",&ch);
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);
switch(ch)
{
case 1:bfs(s,n);
break;
case 2:
dfs(s,n);
break;
}
printf("DO U WANT TO CONTINUE(Y/N) ? ");
scanf("%c",&dummy);
scanf("%c",&c);
}while((c=='y')||(c=='Y'));
}
//**************BFS(breadth-first search) code**************//
void bfs(int s,int n)
{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf(" %d",p);
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}

p=delete();
if(p!=0)
printf(" %d ",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}
void add(int item)
{
if(rear==19)
printf("QUEUE FULL");
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}
int delete()
{
int k;
if((front>rear)||(front==-1))
return(0);
else
{
k=q[front++];
return(k);
}
}
//***************DFS(depth-first search) code******************//
void dfs(int s,int n)
{
int i,k;
push(s);
vis[s]=1;
k=pop();

if(k!=0)
printf(" %d ",k);
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0)&&(vis[i]==0))
{
push(i);
vis[i]=1;
}
k=pop();
if(k!=0)
printf(" %d ",k);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}
void push(int item)
{
if(top==19)
printf("Stack overflow ");
else
stack[++top]=item;
}
int pop()
{
int k;
if(top==-1)
return(0);
else
{
k=stack[top--];
return(k);
}
}
Output:

ENTER THE NUMBER VERTICES 3

ENTER 1 IF 1 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 1 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 1 HAS A NODE WITH 3 ELSE 0 0
ENTER 1 IF 2 HAS A NODE WITH 1 ELSE 0 1
ENTER 1 IF 2 HAS A NODE WITH 2 ELSE 0 0
ENTER 1 IF 2 HAS A NODE WITH 3 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 1 ELSE 0 0
ENTER 1 IF 3 HAS A NODE WITH 2 ELSE 0 1
ENTER 1 IF 3 HAS A NODE WITH 3 ELSE 0 1
THE ADJACENCY MATRIX IS
110
101
011

MENU
1.B.F.S
2.D.F.S
ENTER YOUR CHOICE1
ENTER THE SOURCE VERTEX :2
2 1 3 DO U WANT TO CONTINUE(Y/N) ? y

MENU
1.B.F.S
2.D.F.S
ENTER YOUR CHOICE2
ENTER THE SOURCE VERTEX :2
2 3 1 DO U WANT TO CONTINUE(Y/N) ?

Result :

Thus the above program for the implementation of BFS and DFS for the given graph
has been executed successfully.
Ex. No : 8 Write a programs for implementing the following searching methods.

[Link] search.

Aim :

To write a C program for implementing the Linear Search.

Algorithm :

Step 1 : Start the program.

Step 2 : Linear search is the approach to search for an element in a data set.

Step 3 : Enter the number of elements to be added.

Step 4 : Enter the elements using array.

Step 5 : Enter the element to be searched.

Step 6 : Find the element using the index position by checking using if condition.

Step 7 : Execute the program.

Program :

#include<stdio.h>
int main()
{
int a[20],i,x,n;
printf("How many elements?");
scanf("%d",&n);

printf("Enter array elements:n");

for(i=0;i<n;++i)
scanf("%d",&a[i]);

printf("nEnter element to search:");

scanf("%d",&x);

for(i=0;i<n;++i)
if(a[i]==x)
break;

if(i<n)
printf("Element found at index %d",i);
else
printf("Element not found");

return 0;
}
Output:

How many elements?10

Enter array elements:n21
23
25
24
28
47
56
54
20
28
nEnter element to search:47
Element found at index 5

Result :

Thus the above program for search the element using linear search approach has been
executed successfully.
 [Link] search.

Aim :

To write a C program for implementing the Binary Search.

Algorithm :

Step 1 : Start the program.

Step 2 : Binary Search finds the position of a target value within a sorted array.

Step 3 : Enter the number of elements to be added.

Step 4 : Enter the elements using array.

Step 5 : Enter the element to be searched.

Step 6 : Find the element using the mid value and key value.

Step 7 : Execute the program.

Program :

#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integer\n", n);
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("Enter value to find\n");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high) {
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key) {
printf("%d found at location %d\n", key, mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("Not found! %d isn't present in the list\n", key);
return 0;
}
Output:

Enter number of elements

5
Enter 5 integer
54
58
62
34
12
Enter value to find
62
62 found at location 3

Result :

Thus the above program for search the element using binary search approach has been
executed successfully.
Ex. No : 9 Write a programs for implementing the following sorting methods.

[Link] sort.

Aim :

To write a C program to arrange a string of numbers using bubble sort algorithm.

Algorithm :

Step 1 : Start the Program.

Step 2 : Enter the number of elements in the array.

Step 3 : Enter the values to be added in the array.

Step 4 : Bubble sort involves comparing and swapping two adjacent elements.

Step 5 : Using ‘for’ loop and ‘if’ loop, compare the numbers and arrange the numbers
in the correct order.

Step 6 : Execute the program.

Program :

#include <stdio.h>
int main(){
int arr[50], num, x, y, temp;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements: ");
for(x = 0; x < num; x++)
scanf("%d", &arr[x]);
for(x = 0; x < num - 1; x++){
for(y = 0; y < num - x - 1; y++){
if(arr[y] > arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
}
printf("Array after implementing bubble sort: ");
for(x = 0; x < num; x++){
printf("%d ", arr[x]);
}
return 0;
}
Output:

Please Enter the Number of Elements you want in the array: 5

Please Enter the Value of Elements: 2
9
3
-5
4
Array after implementing bubble sort: -5 2 3 4 9
--------------------------------
Process exited after 26 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program for implementing bubble sort has been executed successfully
 II. Selection sort.

Aim :

To write a C program to arrange a string of numbers using Selection sort algorithm.

Algorithm :

Step 1 : Start the Program.

Step 2 : Enter the number of elements in the array.

Step 3 : Enter the values to be added in the array.

Step 4 : Selection sort involves finding the smallest element in the list and swapping it
with the first element in the unsorted portion of the list.

Step 5 : Using ‘for’ loop and ‘if’ loop, compare the numbers and arrange the numbers
in the correct order.

Step 6 : Execute the program.

Program :

#include <stdio.h>
int main()
{
int array[100], n, c, d, position, t;

printf("Enter number of elements\n");

scanf("%d", &n);

printf("Enter %d integers\n", n);

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

scanf("%d", &array[c]);

for (c = 0; c < (n - 1); c++) // finding minimum element (n-1) times

{
position = c;

for (d = c + 1; d < n; d++)

{
if (array[position] > array[d])
position = d;
}
if (position != c)
{
t = array[c];
array[c] = array[position];
array[position] = t;
}
}

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

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

printf("%d\n", array[c]);

return 0;
}
Output:

Enter number of elements

10
Enter 10 integers
5
5
84
87
63
2
1
8
7
9
Sorted list in ascending order:
1
2
5
5
7
8
9
63
84
87

--------------------------------
Process exited after 22.11 seconds with return value 0
Press any key to continue .

Result :

Thus the above program for implementing selection sort has been executed
successfully.
 [Link] sort.

Aim :

To write a C program to arrange a string of numbers using insertion sort algorithm.

Algorithm :

Step 1 : Start the Program.

Step 2 : Enter the number of elements in the array.

Step 3 : Enter the values to be added in the array.

Step 4 : Insertion sort builds the final sorted list one item at a time by comparisons.

Step 5 : Using ‘for’ loop and ‘if’ loop, compare the numbers and arrange the numbers
in an ascending order.

Step 6 : Execute the program.

Program :

#include <stdio.h>

int main()
{
int n, array[1000], c, d, t, flag = 0;

printf("Enter number of elements\n");

scanf("%d", &n);

printf("Enter %d integers\n", n);

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

scanf("%d", &array[c]);

for (c = 1 ; c <= n - 1; c++) {

t = array[c];

for (d = c - 1 ; d >= 0; d--) {

if (array[d] > t) {
array[d+1] = array[d];
flag = 1;
}
else
break;
}
if (flag)
array[d+1] = t;
}

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

for (c = 0; c <= n - 1; c++) {

printf("%d\n", array[c]);
}

return 0;
}
Output:

Enter number of elements

10
Enter 10 integers
5
-2
6
8
4
9
6
1
5
7
Sorted list in ascending order:
-2
1
4
5
5
6
6
7
8
9

--------------------------------
Process exited after 14.83 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program for implementing insertion sort has been executed
successfully.
 [Link] sort.

Aim :

To write a C program to arrange a string of numbers using radix sort algorithm.

Algorithm :

Step 1 : Start the Program.

Step 2 : Radix sort that sorts data with integer keys by grouping the keys by individual
digits that share the significant position and value.

Step 3 : Inside the RadixSort() function, have to print the largest element and also to
display the elements both in ascending and descending order.

Step 4 : Inside the main() function, have to get the values.

Step 5 : The RadixSort() function along with its parameters have to be called inside
the main() function.

Step 6 : Execute the program.

Program :

#include<stdio.h>

// Function to find largest element

int largest(int a[], int n)
{
int large = a[0], i;
for(i = 1; i < n; i++)
{
if(large < a[i])
large = a[i];
}
return large;
}

// Function to perform sorting

void RadixSort(int a[], int n)
{
int bucket[10][10], bucket_count[10];
int i, j, k, remainder, NOP=0, divisor=1, large, pass;

large = largest(a, n);

printf("The large element %d\n",large);
while(large > 0)
{
NOP++;
large/=10;
}

for(pass = 0; pass < NOP; pass++)

{
for(i = 0; i < 10; i++)
{
bucket_count[i] = 0;
}
for(i = 0; i < n; i++)
{
remainder = (a[i] / divisor) % 10;
bucket[remainder][bucket_count[remainder]] = a[i];
bucket_count[remainder] += 1;
}

i = 0;
for(k = 0; k < 10; k++)
{
for(j = 0; j < bucket_count[k]; j++)
{
a[i] = bucket[k][j];
i++;
 }
}
divisor *= 10;

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

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

//program starts here

int main()
{
int i, n, a[10];
printf("Enter the number of elements :: ");
scanf("%d",&n);
printf("Enter the elements :: ");
for(i = 0; i < n; i++)
{
scanf("%d",&a[i]);
}
RadixSort(a,n);
printf("The sorted elements are :: ");
for(i = 0; i < n; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
Output:

Enter the number of elements :: 7

Enter the elements :: 21
32
11
58
98
45
21
The large element 98
21 11 21 32 45 58 98
11 21 21 32 45 58 98
The sorted elements are :: 11 21 21 32 45 58 98

--------------------------------
Process exited after 36.19 seconds with return value 0
Press any key to continue . . .

Result :

Thus the above program for implementing radix sort has been executed successfully.