Write a program for merging two sorted arrays into third sorted array.

#include<stdio.h>

main()
{
int arr1[20],arr2[20],arr3[40];
int i,j,k;
int max1,max2;

printf("Enter the number of elements in list1 : ");
scanf("%d",&max1);
printf("Take the elements in sorted order :\n");
for(i=0;i<max1;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr1[i]);
}
printf("Enter the number of elements in list2 : ");
scanf("%d",&max2);
printf("Take the elements in sorted order :\n");
for(i=0;i<max2;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr2[i]);
}
/* Merging */
i=0;   /*Index for first array*/
j=0;   /*Index for second array*/
k=0;   /*Index for merged array*/

while( (i < max1) && (j < max2) )
{
if( arr1[i] < arr2[j] )
arr3[k++]=arr1[i++];
else
arr3[k++]=arr2[j++];
}/*End of while*/
/*Put remaining elements of arr1 into arr3*/
while( i < max1 )
arr3[k++]=arr1[i++];
/*Put remaining elements of arr2 into arr3*/
while( j < max2 )
arr3[k++]=arr2[j++];

/*Merging completed*/
printf("List 1 :  ");
for(i=0;i<max1;i++)
printf("%d ",arr1[i]);
printf("\nList 2 :  ");
for(i=0;i<max2;i++)
printf("%d ",arr2[i]);
printf("\nMerged list : ");
for(i=0;i<max1+max2;i++)
printf("%d ",arr3[i]);
printf("\n");
}/*End of main()*/

Write a program for insertion sort.

#include <stdio.h>
#define MAX 20

main()
{
int arr[MAX],i,j,k,n;
printf("Enter the number of elements : ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d", &arr[i]);
}
printf("Unsorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
/*Insertion sort*/
for(j=1;j<n;j++)
{
k=arr[j]; /*k is to be inserted at proper place*/
for(i=j-1;i>=0 && k<arr[i];i--)
arr[i+1]=arr[i];
arr[i+1]=k;
printf("Pass %d, Element inserted in proper place: %d\n",j,k);
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/

Write a program for bubble sort using arrays.

#include <stdio.h>
#define MAX 20
main()
{
int arr[MAX],i,j,k,temp,n,xchanges;
printf("Enter the number of elements : ");
scanf("%d",&n);
for (i = 0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Unsorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");

/* Bubble sort*/
for (i = 0; i < n-1 ; i++)
{
xchanges=0;
for (j = 0; j <n-1-i; j++)
{
if (arr[j] > arr[j+1])
{
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
xchanges++;
}/*End of if*/
}/*End of inner for loop*/
if(xchanges==0) /*If list is sorted*/
break;
printf("After Pass %d elements are :  ",i+1);
for (k = 0; k < n; k++)
printf("%d ", arr[k]);
printf("\n");
}/*End of outer for loop*/

printf("Sorted list is :\n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}/*End of main()*/

Write a program fo binary search.

#include <stdio.h>

main()
{
int arr[20],start,end,middle,n,i,item;

printf("How many elements you want to enter in the array : ");
scanf("%d",&n);
for(i=0; i < n; i++)
{
printf("Enter element %d : ",i+1);
scanf("%d",&arr[i]);
}
printf("Enter the element to be searched : ");
scanf("%d",&item);
start=0;
end=n-1;
middle=(start+end)/2;
while(item != arr[middle] && start <= end)
{
if(item > arr[middle])
start=middle+1;
else
end=middle-1;
middle=(start+end)/2;
}
if(item==arr[middle])
printf("%d found at position %d\n",item,middle+1);
if(start>end)
printf("%d not found in array\n",item);
}/*End of main()*/

WAP to implement the concept of sequential search.

# include<stdio.h>

main()
{
int arr[20],n,i,item;
printf("How many elements you want to enter in the array : ");
scanf("%d",&n);

for(i=0; i < n;i++)
{
printf("Enter element %d : ",i+1);
scanf("%d", &arr[i]);
}
printf("Enter the element to be searched : ");
scanf("%d",&item);
for(i=0;i < n;i++)
{
if(item == arr[i])
{
printf("%d found at position %d\n",item,i+1);
break;
}
}/*End of for*/
if(i == n)
printf("Item %d not found in array\n",item);

}

WAP to implement the concept of sorted linked list.

# include <stdio.h>
# include <malloc.h>

struct node
{
int info;
struct node *link;
}*start;

main()
{
int choice,n,m,i;
start=NULL;
while(1)
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display \n");
printf("4.Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to be inserted : ");
scanf("%d",&m);
insert(m);
break;
case 2:
printf("Enter the element to be deleted : ");
scanf("%d",&m);
del(m);
break;
case 3:
display();
break;
case 4:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
} /*end of main */

insert(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;

/*list empty or item to be added in begining */
if(start == NULL || num < start->info)
{
tmp->link=start;
start=tmp;
return;
}
else
{
q=start;
while(q->link != NULL && q->link->info < num)
q=q->link;
tmp->link=q->link;
q->link=tmp;
}
}/*End of insert()*/

del(int num)
{
struct node *tmp,*q;
if(start->info==num)
{
tmp=start;
start=start->link;  /*first element deleted*/
free(tmp);
return;
}
q=start;
while(q->link->link!=NULL)
{
if(q->link->info==num)     /*element deleted in between*/
{
tmp=q->link;
q->link=tmp->link;
free(tmp);
return;
}
q=q->link;
}/*End of while */
if(q->link->info==num)    /*last element deleted*/
{
tmp=q->link;
free(tmp);
q->link=NULL;
return;
}
printf("Element %d not found\n",num);
}/*End of del()*/

display()
{
struct node *q;
if(start == NULL)
{
printf("List is empty\n");
return;
}
q=start;
printf("List is :\n");
while(q != NULL)
{
printf("%d ", q->info);
q=q->link;
}
printf("\n");
}/*End of display() */

WAP to implement the concept of reversed linked list.

# include <stdio.h>
# include <malloc.h>

struct node
{
int info;
struct node *link;
}*start;

main()
{
int i,n,item;
start=NULL;

printf("How many nodes you want : ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter the item %d : ",i+1);
scanf("%d",&item);
create_list(item);
}
printf("Initially the linked list is :\n");
display();
reverse();
printf("Linked list after reversing is :\n");
display();
}/*End of main()*/

create_list(int num)
{
struct node *q,*tmp;
tmp= malloc(sizeof(struct node));
tmp->info=num;
tmp->link=NULL;

if(start==NULL)
start=tmp;
else
{
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}/*End of create_list() */

display()
{
struct node *q;
if(start == NULL)
{
printf("List is empty\n");
return;
}
q=start;
while(q!=NULL)
{
printf("%d ", q->info);
q=q->link;
}
printf("\n");
}/*End of display()*/

reverse()
{
struct node *p1,*p2,*p3;
if(start->link==NULL)    /*only one element*/
return;
p1=start;
p2=p1->link;
p3=p2->link;

p1->link=NULL;
p2->link=p1;

while(p3!=NULL)
{
p1=p2;
p2=p3;
p3=p3->link;
p2->link=p1;
}
start=p2;
}/*End of reverse() */