BHAGWANT INSTITUTE OF TECHNOLOGY

17th Milestone Bijnor- Delhi highway, Distt- Muzaffarnagar

Data Structures Lab (0327002)– ODD Sem 2024-25

Department : CSE & CA
Lecture Topic
No.
1 Write a C program to find the sum of all elements in an
array

2
Write a C program to find the largest element in an array

3 C program to implement conversion of infix to postfix

4 C Program to Perform Singly Linked List Operations
5
C Program to Implement Circular Doubly Linked List

6 C program to implement to create binary search tree

7 C program to implement preorder,postorder,inorder
8 C program to implement heapsort
9 C program to implement bubble sort
10 C program to implement insertion sort
11 C program to implement quick sort
12 C program to implement merge sort
13 C program to implement selection sort
14 C program to implement linear search
1) Write a C program to find the sum of all elements in an array
2) #include<stdio.h>
3) // Main function
4) intmain()
5) {
6) int a[100];// Declare an array of size 100 to store integer
values
7) inti, n, sum =0;// Declare variables to store array size, loop
counter, and sum
8) // Display a message to the user about the program's purpose
9) printf("\n\nFind sum of all elements of array:\n");
10) printf("--------------------------------------\n");
11) // Prompt the user to input the number of elements to be
stored in the array
12) printf("Input the number of elements to be stored in the
array :");
13) scanf("%d",&n);
14) // Prompt the user to input n elements into the array
15) printf("Input %d elements in the array :\n", n);
16) for(i=0;i< n;i++)
17) {
18) printf("element - %d : ",i);
19) scanf("%d",&a[i]);// Read the input and store it in the
array
20) }
21)
22) // Calculate the sum of all elements in the array using a
for loop
23) for(i=0;i< n;i++)
24) {
25) sum += a[i];// Add each element to the sum
26) }
27) // Display the sum of all elements stored in the array
28) printf("Sum of all elements stored in the array is :
%d\n\n", sum);
29) return0;
30) }
Write a C program to find the largest element in an array
#include <stdio.h>
 int main() {
int array[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
int loop, largest;

largest = array[0];

for(loop = 1; loop < 10; loop++) {

if( largest < array[loop] )
largest = array[loop];
}

printf("Largest element of array is %d", largest);

return 0;
}

2)Write a C program to find the smallest element in an array

31) #include<stdio.h>
32)
33) int main(){
34) int array[10]={1,2,3,4,5,6,7,8,9,0};
35) int loop, smallest;
36)
37) smallest = array[0];
38)
39) for(loop =1; loop <10; loop++){
40) if( smallest > array[loop])
41) smallest = array[loop];
42) }
43)
44) printf("Smallest element of array is %d", smallest);
45)
46) return0;
47) }
48)

3) C program to implement conversion of infix to postfix

Solution:
1. #include <limits.h>
2. #include <stdio.h>
3. #include <stdlib.h>
4. #define MAX 20
5.
6. char stk[20];
7. int top = -1;
8.
9. int isEmpty()
10. {
11. return top == -1;
12. }
13. int isFull()
14. {
15. return top == MAX - 1;
16. }
17.
18. char peek()
19. {
20. return stk[top];
21. }
22.
23. char pop()
24. {
25. if(isEmpty())
26. return -1;
27.
28. char ch = stk[top];
29. top--;
30. return(ch);
31. }
32.
33. void push(char oper)
34. {
35. if(isFull())
36. printf("Stack Full!!!!");
37.
38. else{
39. top++;
40. stk[top] = oper;
41. }
42. }
43.
44. int checkIfOperand(char ch)
45. {
46. return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
47. }
48.
49. int precedence(char ch)
50. {
51. switch (ch)
52. {
53. case '+':
54. case '-':
55. return 1;
56.
57. case '*':
58. case '/':
59. return 2;
60.
61. case '^':
62. return 3;
63. }
64. return -1;
65. }
66.
67. int covertInfixToPostfix(char* expression)
68. {
69. int i, j;
70.
71. for (i = 0, j = -1; expression[i]; ++i)
72. {
73. if (checkIfOperand(expression[i]))
74. expression[++j] = expression[i];
75.
76. else if (expression[i] == '(')
77. push(expression[i]);
78.
79. else if (expression[i] == ')')
80. {
81. while (!isEmpty() && peek() != '(')
82. expression[++j] = pop();
83. if (!isEmpty() && peek() != '(')
84. return -1;
85. else
86. pop();
87. }
88. else
89. {
90. while (!isEmpty() && precedence(expression[i]) <= precedence(p
eek()))
91. expression[++j] = pop();
92. push(expression[i]);
93. }
94.
95. }
96.
97. while (!isEmpty())
98. expression[++j] = pop();
99.
100. expression[++j] = '\0';
101. printf( "%s", expression);
102. }
103.
104. int main()
105. {
106. char expression[] = "((x+(y*z))-w)";
107. covertInfixToPostfix(expression);
108. return 0;
109. }
 12)C Program to Perform Singly Linked List Operations

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

// Linked List Node

structnode {
intinfo;
structnode* link;
};
structnode* start = NULL;

// Function to create list with n nodes initially

voidcreateList()
{
if(start == NULL) {
intn;
printf("\nEnter the number of nodes: ");
scanf("%d", &n);
if(n != 0) {
intdata;
structnode* newnode;
structnode* temp;
newnode = malloc(sizeof(structnode));
start = newnode;
temp = start;
printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);
start->info = data;

for(inti = 2; i<= n; i++) {

newnode = malloc(sizeof(structnode));
temp->link = newnode;
printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);
newnode->info = data;
temp = temp->link;
}
}
 printf("\nThe list is created\n");
}
else
printf("\nThe list is already created\n");
}

// Function to traverse the linked list

voidtraverse()
{
structnode* temp;

// List is empty
if(start == NULL)
printf("\nList is empty\n");

// Else print the LL

else{
temp = start;
while(temp != NULL) {
printf("Data = %d\n", temp->info);
temp = temp->link;
}
}
}

// Function to insert at the front

// of the linked list
voidinsertAtFront()
{
intdata;
structnode* temp;
temp = malloc(sizeof(structnode));
printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);
temp->info = data;

// Pointer of temp will be

// assigned to start
temp->link = start;
start = temp;
}
// Function to insert at the end of
// the linked list
voidinsertAtEnd()
{
intdata;
structnode *temp, *head;
temp = malloc(sizeof(structnode));

// Enter the number

printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);

// Changes links
temp->link = 0;
temp->info = data;
head = start;
while(head->link != NULL) {
head = head->link;
}
head->link = temp;
}

// Function to insert at any specified

// position in the linked list
voidinsertAtPosition()
{
structnode *temp, *newnode;
intpos, data, i = 1;
newnode = malloc(sizeof(structnode));

// Enter the position and data

printf("\nEnter position and data :");
scanf("%d %d", &pos, &data);

// Change Links
temp = start;
newnode->info = data;
newnode->link = 0;
while(i< pos - 1) {
temp = temp->link;
i++;
}
 newnode->link = temp->link;
temp->link = newnode;
}

// Function to delete from the front

// of the linked list
voiddeleteFirst()
{
structnode* temp;
if(start == NULL)
printf("\nList is empty\n");
else{
temp = start;
start = start->link;
free(temp);
}
}

// Function to delete from the end

// of the linked list
voiddeleteEnd()
{
structnode *temp, *prevnode;
if(start == NULL)
printf("\nList is Empty\n");
else{
temp = start;
while(temp->link != 0) {
prevnode = temp;
temp = temp->link;
}
free(temp);
prevnode->link = 0;
}
}

// Function to delete from any specified

// position from the linked list
voiddeletePosition()
{
structnode *temp, *position;
inti = 1, pos;
 // If LL is empty
if(start == NULL)
printf("\nList is empty\n");

// Otherwise
else{
printf("\nEnter index : ");

// Position to be deleted
scanf("%d", &pos);
position = malloc(sizeof(structnode));
temp = start;

// Traverse till position

while(i< pos - 1) {
temp = temp->link;
i++;
}

// Change Links
position = temp->link;
temp->link = position->link;

// Free memory
free(position);
}
}

// Function to find the maximum element

// in the linked list
voidmaximum()
{
inta[10];
inti;
structnode* temp;

// If LL is empty
if(start == NULL)
printf("\nList is empty\n");

// Otherwise
else{
temp = start;
 intmax = temp->info;

// Traverse LL and update the

// maximum element
while(temp != NULL) {

// Update the maximum

// element
if(max < temp->info)
max = temp->info;
temp = temp->link;
}
printf("\nMaximum number "
"is : %d ",
max);
}
}

// Function to find the mean of the

// elements in the linked list
voidmean()
{
inta[10];
inti;
structnode* temp;

// If LL is empty
if(start == NULL)
printf("\nList is empty\n");

// Otherwise
else{
temp = start;

// Stores the sum and count of

// element in the LL
intsum = 0, count = 0;
floatm;

// Traverse the LL
while(temp != NULL) {

// Update the sum

 sum = sum + temp->info;
temp = temp->link;
count++;
}

// Find the mean

m = sum / count;

// Print the mean value

printf("\nMean is %f ", m);
}
}

// Function to sort the linked list

// in ascending order
voidsort()
{
structnode* current = start;
structnode* index = NULL;
inttemp;

// If LL is empty
if(start == NULL) {
return;
}

// Else
else{

// Traverse the LL
while(current != NULL) {
index = current->link;

// Traverse the LL nestedly

// and find the minimum
// element
while(index != NULL) {

// Swap with it the value

// at current
if(current->info > index->info) {
temp = current->info;
current->info = index->info;
 index->info = temp;
}
index = index->link;
}

// Update the current

current = current->link;
}
}
}

// Function to reverse the linked list

voidreverseLL()
{
structnode *t1, *t2, *temp;
t1 = t2 = NULL;

// If LL is empty
if(start == NULL)
printf("List is empty\n");

// Else
else{

// Traverse the LL
while(start != NULL) {

// reversing of points
t2 = start->link;
start->link = t1;
t1 = start;
start = t2;
}
start = t1;

// New head Node

temp = start;

printf("Reversed linked "

"list is : ");

// Print the LL
while(temp != NULL) {
 printf("%d ", temp->info);
temp = temp->link;
}
}
}

// Function to search an element in linked list

voidsearch()
{
intfound = -1;
// creating node to traverse
structnode* tr = start;

// first checking if the list is empty or not

if(start == NULL) {
printf("Linked list is empty\n");
}
else{
printf("\nEnter the element you want to search: ");
intkey;
scanf("%d", &key);

// checking by traversing
while(tr != NULL) {
// checking for key
if(tr->info == key) {
found = 1;
break;
}
// moving forward if not at this position
else{
tr = tr->link;
}
}

// printing found or not

if(found == 1) {
printf(
"Yes, %d is present in the linked list.\n",
key);
}
else{
printf("No, %d is not present in the linked "
 "list.\n",
key);
}
}
}

// Driver Code
intmain()
{
createList();
intchoice;
while(1) {

printf("\n\t1 To see list\n");

printf("\t2 For insertion at"
" starting\n");
printf("\t3 For insertion at"
" end\n");
printf("\t4 For insertion at "
"any position\n");
printf("\t5 For deletion of "
"first element\n");
printf("\t6 For deletion of "
"last element\n");
printf("\t7 For deletion of "
"element at any position\n");
printf("\t8 To find maximum among"
" the elements\n");
printf("\t9 To find mean of "
"the elements\n");
printf("\t10 To sort element\n");
printf("\t11 To reverse the "
"linked list\n");
printf("\t12 Search an element in linked list\n");
printf("\t13 To exit\n");
printf("\nEnter Choice :\n");
scanf("%d", &choice);

switch(choice) {
case1:
traverse();
break;
case2:
 insertAtFront();
break;
case3:
insertAtEnd();
break;
case4:
insertAtPosition();
break;
case5:
deleteFirst();
break;
case6:
deleteEnd();
break;
case7:
deletePosition();
break;
case8:
maximum();
break;
case9:
mean();
break;
case10:
sort();
break;
case11:
reverseLL();
break;
case12:
search();
break;
case13:
exit(1);
break;
default:
printf("Incorrect Choice\n");
}
}
return0;
}
 13)C Program to Implement Circular Doubly Linked List
Solution:
#include<stdio.h>
#include<stdlib.h>

// structure of the node

struct node
{
struct node*prev;
int data;
struct node* next;
};

// global declaration of head node

struct node* head = NULL;

// function prototyping
struct node* create(int);
voidinsert_begin(int);
voidinsert_end(int);
voidinsert_mid(int,int);
voiddelete_begin();
voiddelete_end();
voiddelete_mid();
int search(int);
void update(int,int);
void sort();
intlist_size();
void display();
voiddisplay_reverse(struct node*);
intget_data();
intget_position();

int main()
{
charuser_active='Y';
intuser_choice;
int data, position;

while(user_active=='Y'||user_active=='y')
{
printf("\n\n------ Circular Doubly Linked List -------\n");
printf("\n1. Insert a node at beginning");
printf("\n2. Insert a node at end");
printf("\n3. Insert a node at given position");
printf("\n\n4. Delete a node from beginning");
printf("\n5. Delete a node from end");
printf("\n6. Delete a node from given position");
printf("\n\n7. Print list from beginning");
printf("\n8. Print list from end");
printf("\n9. Search a node data");
printf("\n10. Update a node data");
printf("\n11. Sort the list");
printf("\n12. Exit");
printf("\n\n------------------------------\n");

printf("\nEnter your choice: ");

scanf("%d",&user_choice);

printf("\n------------------------------\n");
switch(user_choice)
{
case1:
printf("\nInserting a node at beginning");
data =get_data();
insert_begin(data);
break;

case2:
printf("\nInserting a node at end");
data =get_data();
insert_end(data);
break;

case3:
printf("\nInserting a node at the given position");
data =get_data();
position =get_position();
insert_mid(position, data);
break;

case4:
printf("\nDeleting a node from beginning\n");
delete_begin();
break;

case5:
printf("\nDeleting a node from end\n");
delete_end();
break;

case6:
printf("\nDelete a node from given position\n");
position =get_position();
delete_mid(position);
break;

case7:
printf("\nPrinting the list from beginning\n\n");
display();
break;

case8:
printf("\nPrinting the list from end\n\n");
if(head == NULL)
{
printf("\n\tList is Empty!\n");
}else{
display_reverse(head);
}
break;

case9:
printf("\nSearching the node data");
data =get_data();
if(search(data)==1){
printf("\n\tNode Found\n");
}else{
printf("\n\tNode Not Found\n");
}
break;
case10:
printf("\nUpdating the node data");
data =get_data();
position =get_position();
update(position, data);
break;

case11:
sort();
printf("\nList was sorted\n");
break;
case12:
printf("\nProgram was terminated\n\n");
return0;

default:
printf("\n\tInvalid Choice\n");
}

printf("\n...............................\n");
printf("\nDo you want to continue? (Y/N) : ");
fflush(stdin);
scanf(" %c",&user_active);
}

return0;
}

// creates a new node

struct node* create(int data)
{
struct node*new_node=(struct node*)malloc(sizeof(struct node));

if(new_node== NULL)
{
printf("\nMemory can't be allocated\n");
return NULL;
}

new_node->data = data;
new_node->next = NULL;
new_node->prev= NULL;
returnnew_node;
}

// insert a new node at the beginning of the list

voidinsert_begin(int data)
{
struct node*new_node= create(data);

if(new_node)
{
// if list is empty
if(head == NULL)
{
new_node->next =new_node;
new_node->prev=new_node;
head =new_node;
return;
}
head->prev->next =new_node;
new_node->prev= head->prev;
new_node->next = head;
head->prev=new_node;
head =new_node;
}
}

// inserts a new node at the end

voidinsert_end(int data)
{
struct node*new_node= create(data);

if(new_node)
{
if(head == NULL)
{
new_node->next =new_node;
new_node->prev=new_node;
head =new_node;
return;
}
head->prev->next =new_node;
new_node->prev= head->prev;
new_node->next = head;
head->prev=new_node;
}
}

// inserts node at the given position

voidinsert_mid(int position,int data)
{
// checking if the position is valid or not
if(position <=0)
{
printf("\nInvalid Position\n");
}elseif(head == NULL && position >1){
printf("\nInvalid Position\n");
}elseif(head != NULL && position >list_size()){
printf("\nInvalid Position\n");
}elseif(position ==1){
insert_begin(data);
}else{
struct node *new_node= create(data);

if(new_node!= NULL){
struct node *temp = head,*prev= NULL;
inti=1;

// traverse the list to the given position

while(++i<= position){
prev= temp;
temp = temp->next;
}

// update the prev node to the new noe

prev->next =new_node;

// update the new node to the temp (position node)

new_node->next = temp;
}
}
}

voiddelete_begin()
{
if(head == NULL){
printf("\nList is Empty\n");
return;
}elseif(head->next == head){
free(head);
head = NULL;
return;
}

struct node* temp = head;

head->prev->next = head->next;
head->next->prev= head->prev;
head = head->next;

free(temp);
temp = NULL;
}

// deletes the node from the end of the list

voiddelete_end()
{
if(head == NULL){
printf("\nList is Empty\n");
return;
}elseif(head->next == head){
free(head);
head = NULL;
return;
}

struct node*last_node= head->prev;

last_node->prev->next = head;
head->prev=last_node->prev;

free(last_node);
last_node= NULL;
}

// deletes the node from the given position

voiddelete_mid(int position)
{
if(position <=0){
printf("\n Invalid Position \n");
}
elseif(position >list_size()){
printf("\n Invalid position \n");
}
elseif(position ==1){
delete_begin();
}
elseif(position ==list_size()){
delete_end();
}
else{
struct node *temp = head;
struct node *prev= NULL;
inti=1;

while(i< position){
prev= temp;
temp = temp->next;
i+=1;
}
prev->next = temp->next;
temp->next->prev=prev;
free(temp);
temp = NULL;
}
}

// search the node with the given key item

int search(int key)
{
if(head == NULL){
printf("\n Not Found \n");
return0;
}

struct node* temp = head;

do
{
if(temp->data == key){
return1;
}
temp = temp->next;
}while(temp != head);
return0;
}

// updates the data of the given node position

void update(int position,intnew_value)
{
if(head == NULL){
printf("\n List is Empty \n");
return;
}elseif(position <=0|| position >list_size()){
printf("\nInvalid position\n");
return;
}

struct node* temp = head;

inti=0;

while(++i< position){
temp = temp->next;
}
temp->data =new_value;
}

// sorts the linked list data using insertion sort

void sort()
{
if(head == NULL){
printf("\nList is Empty\n");
return;
}
struct node* temp1 = head;
struct node* temp2 = head;
int key =0, value;

do{
temp2 = temp1->next;

while(temp2 != head)
{
if(temp1->data > temp2->data)
{
 value = temp1->data;
temp1->data = temp2->data;
temp2->data = value;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}while(temp1->next != head);

// display the list

void display()
{
if(head == NULL){
printf("\nList is empty!\n");
return;
}

struct node* temp = head;

do{
printf("%d ", temp->data);
temp = temp->next;
}while(temp != head);
}

// display the list from end to start

voiddisplay_reverse(struct node* temp)
{
if(temp->next == head){
printf("%d ", temp->data);
return;
}

display_reverse(temp->next);
printf("%d ", temp->data);
}

// calculate the size of the list

intlist_size()
{
if(head == NULL){
return0;
}

struct node* temp = head;

int count =0;

do{
count +=1;
temp = temp->next;
}while(temp != head);

return count;
}

intget_data()
{
int data;
printf("\n\nEnter Data: ");
scanf("%d",&data);

return data;
}

intget_position()
{
int position;
printf("\n\nEnter Position: ");
scanf("%d",&position);

return position;
}
Solution:
#include<stdio.h>
#include<stdlib.h>
structnode
{
intdata;
node*left;
node*right;
};
structnode*root;
structnode*insert(structnode*r,intdatatonode)
{
if(r=NULL)
{
r= (structnode*)malloc (sizeof(structnode));
r->data=datatonode;
r->left=NULL;
r->right=NULL;
}
elseif(datatonode<r->data)
r->left=insert(r->left,datatovalue);
else
r->rigth=insert(r->right,datatovalue);
returnr;
}
voidinOrder(structnode*r)
{
if(r!=NULL)
{
inOrder(r->left);
printf("%d",r->data);
inOrder(r->right);
}
}
voidpreOrder(structnode*r)
{
if(r!=NULL)
 {
printf("%d",r->data);
preOrder(r->left);
preOrder(r->right);
}
}
voidpostOrder(structnode*r)
{
if(r!=NULL)
{
postOrder(r->left);
postOrder(r->right);
printf("%d",r->data);
}
}

intmain()
{
root=NULL;
intnumber,value;
printf("entre the number of element to be inserted ?\n");
scanf("%d",&number);
for(inti=0;i<n;i++)
{
printf("Data no %d is",i+1);
scanf("%d",&value);
root=insert(root,value);
}
printf("========INRODER
TARVERSAL===========");
inOrder(root);
printf("\n");
printf("=======PREORDER
TRAVERSAL===========");
preOrder(root);
printf("\n");
printf("=======POSTORDRER
TRAVERSAL=========");
postOrder(root);
printf("\n");
getch();
return0;
}
26) C program to implement bubble sort
1. Solution: #include <stdio.h>
2.
3. void bubble_sort(int arr[], int n) {
4. int i, j;
5. for (i = 0; i < n - 1; i++) {
6. for (j = 0; j < n - i - 1; j++) {
7. if (arr[j] > arr[j + 1]) {
8. int temp = arr[j];
9. arr[j] = arr[j + 1];
10. arr[j + 1] = temp;
11. }
12. }
13. }
14. }
15. int main() {
16. int arr[] = {64, 34, 25, 12, 22, 11, 90};
17. int n = sizeof(arr) / sizeof(arr[0]);
18. bubble_sort(arr, n);
19. printf("Sorted array: ");
20. for (int i = 0; i < n; i++) {
21. printf("%d ", arr[i]);
22. }
23. return 0;
24. }

27) C program to implement insertion sort

Solution:
#include <math.h>
#include <stdio.h>

/* Function to sort an array

using insertion sort*/
voidinsertionSort(intarr[], intn)
{
inti, 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
voidprintArray(intarr[], intn)
{
inti;
for(i = 0; i< n; i++)
printf("%d ", arr[i]);
printf("\n");
}

// Driver code
intmain()
{
intarr[] = {12, 11, 13, 5, 6};
intn = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return0;
}
28) C program to implement quick sort
Solution:
#include <stdio.h>

// Function to swap two elements

voidswap(int* a, int* b)
{
intt = *a;
*a = *b;
*b = t;
}

// Partition the array using the last element as the pivot

intpartition(intarr[], intlow, inthigh)
{
// Choosing the pivot
intpivot = arr[high];

// Index of smaller element and indicates

// the right position of pivot found so far
inti = (low - 1);

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

// If current element is smaller than the pivot

if(arr[j] < pivot) {

// Increment index of smaller element

i++;
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
voidquickSort(intarr[], intlow, inthigh)
{
if(low < high) {

// pi is partitioning index, arr[p]

// is now at right place
intpi = partition(arr, low, high);

// Separately sort elements before

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

// Driver code
intmain()
{
intarr[] = { 10, 7, 8, 9, 1, 5 };
intN = sizeof(arr) / sizeof(arr[0]);

// Function call
quickSort(arr, 0, N - 1);
printf("Sorted array: \n");
for(inti = 0; i< N; i++)
printf("%d ", arr[i]);
return0;
}

29) C program to implement merge sort

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

// Merges two subarrays of arr[].

// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
voidmerge(intarr[], intl, intm, intr)
{
inti, j, k;
intn1 = m - l + 1;
intn2 = r - m;
// Create temp arrays
intL[n1], R[n2];

// Copy data to temp arrays

// L[] and R[]
for(i = 0; i< n1; i++)
L[i] = arr[l + i];
for(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
i = 0;

// Initial index of second subarray

j = 0;

// Initial index of merged subarray

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
voidmergeSort(intarr[], intl, intr)
{
if(l < r) {
// Same as (l+r)/2, but avoids
// overflow for large l and h
intm = l + (r - l) / 2;

// Sort first and second halves

mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);

merge(arr, l, m, r);
}
}

// UTILITY FUNCTIONS
// Function to print an array
voidprintArray(intA[], intsize)
{
inti;
for(i = 0; i< size; i++)
printf("%d ", A[i]);
printf("\n");
}

// Driver code
intmain()
{
intarr[] = { 12, 11, 13, 5, 6, 7 };
intarr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");

printArray(arr, arr_size);
 mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");

printArray(arr, arr_size);
return0;
}

30) C program to implement selection sort

Solution:#include<stdio.h>
int main(){
intarr[10]={6,12,0,18,11,99,55,45,34,2};
int n=10;
inti, j, position, swap;
for(i=0;i<(n -1);i++){
position =i;
for(j =i+1; j < n;j++){
if(arr[position]>arr[j])
position = j;
}
if(position !=i){
swap =arr[i];
arr[i]=arr[position];
arr[position]= swap;
}
}
for(i=0;i< n;i++)
printf("%d\t",arr[i]);
return0;
}

32) C program to implement linear search

Solution:
#include <stdio.h>
intmain()
{
int a[10],i,item,n;
printf("\nEnter number of elements of an array:\n");
scanf("%d",&n);
printf("\nEnter elements: \n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter item to search: ");
scanf("%d",&item);
for(i=0;i<=9;i++)
if(item == a[i])
{
printf("\nItem found at location %d", i+1);
break;
}
if(i>9)
printf("\nItem does not exist.");
return0;
}

15) C program to implement binary search

Solution: #include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];

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]);

printf("Enter value to find\n");

scanf("%d", &search);

first = 0;
last = n - 1;
middle = (first+last)/2;
 while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last)/2;

}
if (first > last)
printf("Not found! %d isn't present in the list.\n", search);

return 0;
}