# Complexity of merge sort

Merge sort is a devide and comquer algorithm, as outlined below.

list mergesort (list L,int n)
{
if(n==1)
return L
else
{
split L in to two halves L-1 and L-2.
return Merge( mergesort(L-1 ,n/2),mergesort(L-2,n/2) )
}
}

Let T(n) be the running time of merge sort on an input list of size n.
Then,
T(n) ≤ C1 if( n=1 ) ( C1 is a constant )
≤   2×T(n/2)                         +    C2×n  if(n > 1)
(for two recursive calls)          (cost of merging)
if n= 2^k for some k , it can be shown that
T(n) ≤ (2^k) ×T(1)  +  C2 × k× (2^k)
That is ,  T(n) is order of O(nlog(n) ).

## 3 thoughts on “Complexity of merge sort”

1. vijay says:

using System;
using System.Collections.Generic;
using System.Text;

{
class Node
{
public int rollNumber;
public string name;
public Node next;
}
class List
{
Node START;
public List()
{
START = null;
}

{
int rollNo;
string nm;
Console.Write(“\nEnter the roll number of the student:”);
Console.Write(“\nEnter the name of the student: “);
Node newnode = new Node();
newnode.rollNumber = rollNo;
newnode.name = nm;

if (START == null || rollNo = current.rollNumber))
{
if (rollNo == current.rollNumber)
{
Console.WriteLine(“\nDuplicate roll numbers not allowed\n”);
return;
}
previous = current;
current = current.next;
}
newnode.next = current;
previous.next = newnode;
}

public bool delNode(int rollNo)
{
Node previous, current;
previous = current = null;
if (Search(rollNo, ref previous, ref current) == false)
return false;
previous.next = current.next;
if (current == START)
START = START.next;
return true;
}

public bool Search(int rollNo, ref Node previous, ref Node current)
{
previous = START;
current = START;
while ((current != null) && (rollNo != current.rollNumber))
{
previous = current;
current = current.next;
}
if (current == null)
return (false);
else
return (true);
}

public void traverse()
{
if (listEmpty())
Console.WriteLine(“\nList is empty.\n”);
else
{
Console.WriteLine(“\nThe records in the list are:\n”);
Node currentNode;
for (currentNode = START; currentNode != null; currentNode = currentNode.next)
Console.Write(currentNode.rollNumber + ” ” + currentNode.name + “\n”);
Console.WriteLine();
}
}

public bool listEmpty()
{
if (START == null)
return true;
else
return false;
}

static void Main(string[] args)
{
List obj = new List();
while (true)
{
try
{
Console.WriteLine(“1. Add a record to the list”);
Console.WriteLine(“2. Delete a record from the list”);
Console.WriteLine(“3. View all the records in the list”);
Console.WriteLine(“4. Search for a record in the list”);
Console.WriteLine(“5. Exit”);
switch (ch)
{
case ‘1’:
{
}
break;
case ‘2’:
{
if (obj.listEmpty())
{
Console.WriteLine(“\nList is empty”);
break;
}
Console.Write(“\nEnter the roll number of the student whose record is to be deleted: “);
Console.WriteLine();
if (obj.delNode(rollNo) == false)
else
Console.WriteLine(“Record with roll number ” + rollNo + “deleted”);
}
break;
case ‘3’:
{
obj.traverse();
}
break;
case ‘4’:
{
if (obj.listEmpty() == true)
{
Console.WriteLine(“\nList is empty”);
break;
}
Node previous, current;
previous = current = null;
Console.Write(“\nEnter the roll number of the student whose record is to be searched: “);
if (obj.Search(num, ref previous, ref current) == false)
else
{
Console.WriteLine(“\nRecord found”);
Console.WriteLine(“\nRoll number: ” + current.rollNumber);
Console.WriteLine(“\nName: ” + current.name);
}
}
break;
case ‘5’:
return;
default:
{
Console.WriteLine(“\nInvalid option”);
break;
}
}
}
catch (Exception )
{
Console.WriteLine(“\nCheck for the value entered.”);
}
}
}
}
}

2. sagar says:

PROGRAMME FOR SELECTION SORT:

#include
int main()
{
int a[100],n,i,j,temp,loc,min;
printf(“\n\tHOW MANY ELEMENTS :”);
scanf(“%d”,&n);
printf(“\n\tENTER THE ELEMENT”);
for(i=0;i<=(n-1);i++)
{
scanf("%d",&a[i]);
}
min=a[0];
for(i=0;i<=(n-1);i++)
{
min=a[i];
loc=i;
for(j=i+1;j<=(n-1);j++)
{
if(a[j<min])
{
min=a[j];
loc=j;
}
}
if(loc!=i)
{
temp=a[i];
a[i]=a[loc];
a[loc]=temp;
}
}
printf("\n\tSORTING ELEMENT:");
for(i=0;i<=(n-1);i++)
{
printf("\n\t %d",a[i]);
}
}

OUTPUT:

[user@localhost ~]\$ vi selectionsort.c
[user@localhost ~]\$ gcc selectionsort.c
[user@localhost ~]\$ ./a.out

HOW MANY ELEMENTS 5

Enter element of array
1
6
5
4
3

Sorting elements are :
1
3
4
5
6
[user@localhost ~]\$

PROGRAMME FOR MERGE SORT:

#include
#define MAX 30
int main()
{

printf(“\n\t\t ****** ~:PROGRAM FOR MEARGE SORT :~ ******\n “);
int arr[MAX],temp[MAX],n,i,j,k,size,u1,l1,l2,u2;
printf(“\n Enter no of Element :”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf("Enter element %d :",i+1);
scanf("%d",&arr[i]);
}
printf("\n\n UNSORTED list is :");
for(i=0;i<n;i++)
printf("\t %d",arr[i]);
for(size=1;size<n;size=size*2)
{
l1=0;
k=0;
while(l1+size=n)
u2=n-1;
i=l1;
j=l2;
while(i<=u1 && j<=u2)
{
if(arr[i]<=arr[j])
temp[k++]=arr[i++];
else
temp[k++]=arr[j++];
}
while(i<=u1)
temp[k++]=arr[i++];
while(j<=u2)
temp[k++]=arr[j++];
l1=u2+1;
}
for(i=l1;k<n;i++)
temp[k++]=arr[i];
for(i=0;i<n;i++)
arr[i]=temp[i];
printf("\n\n pass=%d\n\n Elements are :",size);
for(i=0;i<n;i++)
printf("\t%d",arr[i]);
}
printf("\n\n Sorted list is :");
for(i=0;i<n;i++)
{
printf("\n\t\t%d",arr[i]);
printf("\n\n");
}
}

OUTPUT

[user@localhost ~]\$ gcc msort.c
[user@localhost ~]\$ ./a.out

Enter no of Element :5
Enter element 1 :22
Enter element 2 :77
Enter element 3 :33
Enter element 4 :55
Enter element 5 :11

UNSORTED list is : 22 77 33 55 11

pass=1

Elements are : 22 77 33 55 11

pass=2

Elements are : 22 33 55 77 11

pass=4

Elements are : 11 22 33 55 77

Sorted list is :
11

22

33

55

77

Programme for quick sort

#include
#define max 100
int a[max],n,i,l,h;
main()
{
void input(void);
input();
}
void input(void)
{
void quick_sort(int a[],int l,int h);
void output(int a[],int n);
printf(“\nHow many elements in array :”);
scanf(“%d”,&n);
printf(“\n\nEnter the elements:”);
for(i=0;ia[low])
{
low++;
}
while(key<a[high])
{
high–;
}
if(low<=high)
{
temp=a[low];
a[low++]=a[high];
a[high–]=temp;
}
}
while(low<=high);
if(l<high)
quick_sort(a,l,high);
if(low<h)
quick_sort(a,low,h);
}
void output(int a[],int n)
{
for(i=0;i<=n-1;i++)
{
printf("%d\n",a[i]);
}
}

OUTPUT:

[user@localhost ~]\$ gcc quicksort.c
[user@localhost ~]\$ ./a.out

how many elements in array : 3

Enter the elements : 1
5
4

SORTED ARRAYS: 1
4
5

#include
#define max 100
int a[max],n,i;
main()
{
void input (void);
input();
}
void input(void)
{
void output (int a[],int n);
printf(“\n HOW MANY ELEMENTS IN YOUR ARRAY:”);
scanf(“%d”,&n);
printf(“\n”);
printf(“\n enter the element”);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n sorted array is:\n");
output(a,n);
}
{
int bucket[10][5],buck[5],b[10];
int i,j,l,k,num,div,large,passes;
div=1;
num=0;
large=a[0];
for(i=0;ilarge)
large=a[i];
}
while(large>0)
{
num++;
large=large/10;
}
for(passes=0;passes<num;passes++)
{
for(k=0;k<10;k++)
buck[k]=0;
for(i=0;i<n;i++)
{
l=(a[i]/div)%10;
bucket[1][buck[1]++]=a[i];
}
i=0;
for(k=0;k<10;k++)
{
for(j=0;j<buck[k];k++)
a[i++]=bucket[k][j];
}
div*=10;
}
}
void output(int a[],int n)
{
for(i=0;i<n;i++)
{
printf("\n%d",a[i]);
}
}

output

[user@localhost ~]\$ ./a.out

HOW MANY ELEMENTS IN YOUR ARRAY:4

enter the element67
45
34
23

sorted array is:

67
45
34
23[

#include
#include
struct list
{
int item;
struct list *next;
};
typedef struct list list;
list *start=NULL,*last=NULL;
int main()
{
int ch;
while(1)
{
printf(“\n1.insert\n2.delete\n3.display\n4.exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;

}
}
}
list *getnode()
{
list *temp;
int value;
temp=(list *)malloc(sizeof(list));
scanf(“%d”,&value);
temp->item=value;
temp->next=NULL;
return temp;
}
insert()
{
list *current,*ptr,*prev;
current=getnode();
if(start==NULL)
{
start=last=current;
last->next=start;
}
else
{
for(prev=ptr=start;ptr!=last;prev=ptr,ptr=ptr->next);
ptr->next=current;
last=current;
last->next=start;
}
}
display()
{
list *prev,*ptr;
if(start==NULL)
{
printf(“\n enter list is empty”);
return;
}
else
{
for(ptr=start;ptr!=last;ptr=ptr->next)
{
printf(“\t %d”,ptr->item);
}
printf(“\t %d”,ptr->item);
}
}
del()
{
list *ptr,*prev;
int val;
printf(“\n enter the value that u want to delete:”);
scanf(“%d”,&val);
ptr=start;
if(start==NULL)
{
printf(“\n list is empty”);
return;
}
if(ptr->item==val)
{
start=ptr->next;
last->next=start;
printf(“\n value deleted=%d”,ptr->item);
free(ptr);
}
else
{
for(prev=ptr=start;ptr->item!=val;prev=ptr,ptr=ptr->next);
if(ptr->next==start)
{
printf(“\n value deleted=%d”,ptr->item);
prev->next=start;
last=prev;
}
else
{
prev->next=ptr->next;
printf(“\n value deleted=%d”,ptr->item);
free(ptr);
}
}
}

output

[user@localhost ~]\$ ./a.out
1.insert
2.delete
3.display
4.exit
1.insert
2.delete
3.display
4.exit
1.insert
2.delete
3.display
4.exit
1.insert
2.delete
3.display
4.exit
22 33 44
Program for DFS

#include
#include
#define true 1
#define false 0
#define max 8
struct node
{
int data;
struct node*next;
};
int visited[max];
void dfs(int v,struct node**p);
struct node* getnodewrite(int);
void del(struct node*n);
int main()
{
struct node*arr[max];
struct node*v1,*v2,*v3,*v4;
int i;
v1=getnodewrite(2);
arr[0]=v1;

v1->next=v2=getnodewrite(3);
v2->next=NULL;
v1=getnodewrite(1);
arr[1]=v1;

v1->next=v2=getnodewrite(4);
v1->next=v3=getnodewrite(5);
v3->next=NULL;
v1=getnodewrite(1);
arr[2]=v1;

v1->next=v2=getnodewrite(6);
v2->next=v3=getnodewrite(7);
v3->next=NULL;
v1=getnodewrite(2);
arr[3]=v1;

v3->next=NULL;
v1=getnodewrite(2);
arr[3]=v1;

v1->next=v2=getnodewrite(8);
v2->next=NULL;
v1=getnodewrite(2);
arr[4]=v1;

v1->next=v2=getnodewrite(8);
v2->next=NULL;
v1=getnodewrite(3);
arr[5]=v1;
v1->next=v2=getnodewrite(8);

v2->next=NULL;
v1=getnodewrite(3);
arr[6]=v1;

v1->next=v2=getnodewrite(8);
v2->next=NULL;
v1=getnodewrite(4);
arr[7]=v1;

v1->next=v2=getnodewrite(5);
v1->next=v2=getnodewrite(6);
v1->next=v2=getnodewrite(7);
v4->next=NULL;
dfs(1,arr);
for(i=0;idata-1]==false)
dfs(q->data,p);
else
q=q->next;
}
}
struct node* getnodewrite(int val)
{
struct node *newnode;
newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=val;
return newnode;
}
void del (struct node*n)
{
struct node*temp;
while(n!=NULL)
{
temp=n->next;
free(n);
n=temp;
}
}

Output

[user@localhost ~]\$ ./a.out
1 2 4 8 5 6 3 7

Programme for circular queue

#include
#define MAXSIZE 5
int cq[10];
int front=-1,rear=0;
int choice;
char ch;
int main()
{
do
{
printf(“\n1.insert\n2.delete\n3.display\n4.exit”);
printf(“\n enter ur choice”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:cqinsert();
break;
case 2:cqdelete();
break;
case 3:cqdisplay();
break;
case 4:return;
}
fflush(stdin);
}
while(choice!=4);
}
cqinsert()
{
int num;
if(front==(rear+1)%MAXSIZE)
{
printf(“\n queue is full”);
return;
}
else
{
printf(“\n element to be inserted”);
scanf(“%d”,&num);
if(front==-1)
front=rear=0;
else
rear=(rear+1)%MAXSIZE;
cq[rear]=num;
}
return;
}
int cqdelete()
{
int num;
if(front==-1)
{
printf(“\n queue is empty”);
return;
}
else
{
num=cq[front];
printf(“\n\t deleted element is %d”,cq[front]);
if(front==rear)
front=rear=-1;
else
front=(front+1)%MAXSIZE;
}
return(num);
}
cqdisplay()
{
int i;
if(front==-1)
{
printf(“\n queue is empty”);
return;
}
else
{
printf(“\n the status of queue”);
for(i=front;irear)
{
for(i=front;i<MAXSIZE;i++)
{
printf("%d",cq[i]);
}
for(i=0;i<=rear;i++)
{
printf("%d",cq[i]);
}
}
printf("\n");
}

output

[user@localhost untitled folder]\$ gcc cq.c
[user@localhost untitled folder]\$ ./a.out

1.insert
2.delete
3.display
4.exit
enter ur choice1

element to be inserted11

1.insert
2.delete
3.display
4.exit
enter ur choice1

element to be inserted22

1.insert
2.delete
3.display
4.exit
enter ur choice1

element to be inserted33

1.insert
2.delete
3.display
4.exit
enter ur choice3

the status of queue 11 22 33

1.insert
2.delete
3.display
4.exit
enter ur choice4
[user@localhost untitled folder]\$

PROGRAMME FOR INFIX TO POSTFIX

#include
#include
#define MAXSIZE 20
char infix[MAXSIZE];
char postfix[MAXSIZE];
int flag=1;
struct stack
{
char item [MAXSIZE];
int top;
};
typedef struct stack stack;
stack s;
int isoprt(char);
int prio(char);
void push(char,stack*);
char pop(stack*);
int main()
{
s.top==-1;
printf(“\n ENTER THE INFIX EXPRESSION”);
gets(infix);
strcat(infix,”)”);
convert(&s);
printf(“\n POSTFIX EXPRESSION=%s”,postfix);
}
void push(char input, stack *ps)
{
ps->top++;
ps->item[ps->top]=input;
}

char pop(stack*ps)
{
char value;
value=ps->item[ps->top];
ps->top–;
return value;
}

stack_empty(stack*ps)
{
if(ps->top==-1)
return 1;
else
return 0;
}
stack_full(stack*ps)
{
if(ps->top==MAXSIZE-1)
return 1;
else
return 0;
}
convert(stack *ps)
{
int i=0,j=0;
push(‘(‘,&s);
while(infix[i]!=”)
{
if(infix[i]=='(‘)
push(infix[i],&s);
if(isdigit(infix[i])||isalpha(infix[i]))
postfix[j++]=infix[i];
if(isoprt(infix[i]))
{
if(ps->top==0)
push(infix[i],&s);
while(prio(ps->item[ps->top]) >= prio(infix[i]))
{
postfix[j++]=pop(&s);
flag=2;
}
if(flag==1)
{
push(infix[i],&s);
}
}
if(infix[i]==’)’)
{
while(ps->item[ps->top]!='(‘)
{
postfix[j++]=pop(&s);
}
}
i++;
}
postfix[j]=”;
}
isoprt(char opt)
{
if(opt==’/’||opt==’*’||opt==’+’||opt==’-‘)
return 1;
else
return 0;
}
prio(char c)
{
switch(c)
{
case ‘/’:return 4;
case ‘*’:return 3;
case ‘+’:return 2;
case ‘-‘:return 1;
case ‘(‘:return 0;
}
}

OUTPUT

[user@localhost ~]\$ ./a.out
ENTER THE INFIX EXPRESSIONa+b
POSTFIX EXPRESSION=ab+

#include
#include
struct list
{
int item;
struct list *next;
};
typedef struct list list;
list *start=NULL;
int main()
{
int ch;
while(1)
{
printf(“\n1.insert \n2.delete \n3.display \n4.return”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
return;
break;
} }
}
list *getnode()
{
list *temp;
int value;
temp=(list *)malloc(sizeof (list));
scanf(“%d”,&value);
temp->item=value;
temp->next=NULL;
return temp;
}
insert()
{
list *current,*ptr,*prev;
current=getnode();
if(start==NULL)
{
start=current;
}
else
{
for(prev=ptr=start;ptr!=NULL;prev=ptr,ptr=ptr->next);
prev->next=current;
}
}
display()
{
list *prev,*ptr;
if(start==NULL)
{
printf(“\n list is empty”);
return;
}
else
{
for(ptr=start;ptr!=NULL;ptr=ptr->next)
{
printf(“\t %d”,ptr->item);
}
}
}
del()
{
list *ptr,*prev;
int val;
printf(“\n enter the value that u want to delete:”);
scanf(“%d”,&val);
ptr=start;
if(start==NULL)
{
printf(“\n list is empty”);
return;
}
if(ptr->item==val)
{
start=ptr->next;
free(ptr);
}
else
{
for(prev=ptr=start;ptr->item!=val;prev=ptr,ptr=ptr->next);
prev->next=ptr->next;
printf(“\n value deleted=%d”,ptr->item);
free(ptr);
} }

OUTPUT

[user@localhost ~]\$ gcc tree.c
[user@localhost ~]\$ ./a.out
1.insert
2.delete
3.display
4.return
1.insert
2.delete
3.display
4.return
1.insert
2.delete
3.display
4.return
Enter the value which you want to delete:22
Value deleted 22
1.insert
2.delete
3.display
4.return
11

/* Programme for evaluation of postfix */

#include
struct stack
{
int item[20];
int top;
};
typedef struct stack stack;
stack s;
char input [20];
main()
{
s.top==-1;
printf(“\n Please enter the postfix evaluation:”);
scanf(“%s”,&input);
eval(&s);
}
eval(stack *ps)
{
int op1,op2,result,i=0;
while(input[i]!=”)
{
if(isdigit(input[i]))
{
printf(“push the element:%c”,input[i]);
push(input[i]-‘0’,&s);
}
else
{
op1=pop(&s);
printf(“\n pop the top:%d”,op1);
op2=pop(&s);
printf(“\n popthe next to top:%d\n”,op2);
switch(input[i])
{
case ‘+’:
result=op1+op2;
break;

case ‘-‘:
result=op1-op2;
break;

case ‘*’:
result=op1*op2;
break;

case ‘/’:
result=op1/op2;
break;
}
push(result,&s);
printf(“\n for the operator %c push the result=%d\n”,input[i],result);
}
i++;
}
printf(“\n Evaluation of postfix :%d\n”,pop(&s));
}
push(int val,stack*ps)
{
ps->top++;
ps->item[ps->top]=val;
}
int pop(stack *ps)
{
int temp;
temp=ps->item[ps->top];
ps->top–;
return temp;
}
OUTPUT:

[user@localhost ~]\$ gcc conversionpostfix.c
[user@localhost ~]\$ ./a.out

postfix expression:AB+
[user@localhost ~]\$

PROGRAMME FOR QUEUE USING POINTER
#include
#include
struct queue
{
int no;
struct queue*next;
}
*start=NULL;
int dle();
void traverse();
main()
{
int ch;
char choice;
do
{
printf(“\n\t\t 2.dlete”);
printf(“\n\t\t 3.traverse”);
printf(“\n\t\t 4.exit”);
scanf(“%d”,&ch);
switch(ch)
{
break;
case 2:printf(“\n\n\t the dlete element is %d “,dle());
break;
case 3:
traverse();
break;
case 4:
return;
default:
printf(“\t\t\nWrong choice\n”);
}
fflush(stdin);
scanf(“%c”,&choice);
}
while(choice!=4);
}
{
struct queue*p,*temp;
temp=start;
p=(struct queue*)malloc(sizeof(struct queue));
printf(“\n\n\tEnter the data”);
scanf(“%d”,&p->no);
p->next=NULL;
if(start==NULL)
{
start=p;
}
else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=p;
}
}
int dle()
{
struct queue*temp;
int value;
if(start==NULL)
{
printf(“\t\t\nqueue is empty”);
return(0);
}
else
{
temp=start;
value=temp->no;
start=start->next;
free(temp);
}
return(value);
}
void traverse()
{
struct queue *temp;
temp=start;
while(temp->next!=NULL)
{
printf(“no=%d”,temp->no);
temp=temp->next;
}
printf(“no=%d”,temp->no);
}

OUTPUT

[user@localhost ~]\$ gcc queo.c
[user@localhost ~]\$ ./a.out
2.dlete
3.traverse
4.exit
Enter the data11
2.dlete
3.traverse
4.exit
Enter the data22
2.dlete
3.traverse
4.exit
Enter the data33
2.dlete
3.traverse
4.exit
no=11no=22no=33
2.dlete
3.traverse
4.exit
the dlete element is 11
2.dlete
3.traverse
4.exit
the dlete element is 22
2.dlete
3.traverse
4.exit
no=33
2.dlete
3.traverse
4.exit
PROGRAM:
#include

#include

#define MAXSIZE 10

void push();

int pop();

void traverse();

int stack[MAXSIZE];

int Top=-1;

main()

{

int choice;

char ch;

do

{

// clrscr();

printf(“\n1.PUSH”);

printf(“\n2.POP”);

printf(“\n3.TRAVERSE”);

printf(“\nEnter Ur Choice”);

scanf(“%d”,&choice);

switch(choice)

{

case 1: push();

break;

case 2: printf(“\nThe deleted element is %d”,pop());

break;

case 3: traverse();

break;

default: printf(“\nYou Entered Wrong choice”);

exit(0);

}

printf(“\nDo u Wish to Continue(y/n)”);

// fflush(stdin);

scanf(“%c”,&ch);

}

while(ch = ‘y’||ch == ‘Y’);

}

void push()

{

int item;

if(Top==MAXSIZE-1)

{

printf(“\nThe stack is full “);

// getch();

// exit(0);

}

else

{

printf(“Enter The element To be inserted”);

scanf(“%d”,&item);

Top=Top+1;

stack[Top]=item;

}

}

int pop()

{

int item;

if(Top==-1)

{

printf(“Stack is empty”);

// getch();

exit(0);

}

else

{

item=stack[Top];

Top=Top-1;

}

return(item);

}

void traverse()

{

int i;

if(Top==-1)

{

printf(“Stack is empty”);

// getch();

exit(0);

}

else

{

printf(“Traverse the element”);

for(i=Top;i>=0;i–)

{

printf(“\n%d”,stack[i]);

}

}

}

OUTPUT:

[user@localhost ~]\$ vi stack.c
[user@localhost ~]\$ gcc stack.c
[user@localhost ~]\$ ./a.out

1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice1
Enter The element To be inserted20

Do u Wish to Continue(y/n)
1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice1
Enter The element To be inserted56

Do u Wish to Continue(y/n)
1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice1
Enter The element To be inserted35

Do u Wish to Continue(y/n)
1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice3
Traverse the element
35
56
20
Do u Wish to Continue(y/n)
1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice2

The deleted element is 35
Do u Wish to Continue(y/n)
1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice3
Traverse the element
56
20
Do u Wish to Continue(y/n)
1.PUSH
2.POP
3.TRAVERSE
Enter Ur Choice

PROGRAMME FOR STACK AS LINK LIST

#include
#include
struct list
{
int item;
struct list *next;
};
typedef struct list list;
list *start=NULL,*top=NULL;
int main()
{
int ch;
while(1)
{
printf(“\n1.push \n2.pop \n3.display \n4.exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 4:
return;
}
}
}
list *getnode()
{
list *temp;
int value;
temp=(list *)malloc(sizeof(list));
scanf(“%d”,&value);
temp->item=value;
temp->next=NULL;
return temp;
}
insert()
{
list *current,*ptr,*prev;
current=getnode();
if(start==NULL)
{
start=top=current;
}
else
{
for(prev=ptr=start;ptr!=top;prev=ptr,ptr=ptr->next);
ptr->next=current;
top=current;
}
}
display()
{
list *prev,*ptr;
if(top==NULL)
{
printf(“\n STACK IS EMPTY”);
return;
}
else
{
for(ptr=start;ptr!=NULL;ptr=ptr->next)
{
printf(“\t %d”,ptr->item);
}
}
}
del()
{
list *ptr,*prev;
int val;
if(start==NULL)
{
printf(“\n STACK IS EMPTY”);
return;
}
if(start->next==NULL)
{
printf(“\n value deleted=%d”,start->item);
free(start);
start=top=NULL;
}
else
{
for(prev=ptr=start;ptr!=top;prev=ptr,ptr=ptr->next);
printf(“\n VALUE DELETED =%d”,ptr->item);
prev->next=NULL;
top=prev;
free(ptr);
}
}

Output

1.push
2.pop
3.display
4.exit

1.push
2.pop
3.display
4.exit

1.push
2.pop
3.display
4.exit

1.push
2.pop
3.display
4.exit
2 3 4

PROGRAMME FOR REVERSE STRING

#include
struct stack
{
char nm[30];
int top;
};
typedef struct stack stack;
stack s;
int main()
{
void push(char c,struct stack *ps);
s.top=-1;
int i;
char temp[30];
scanf(” %s”,&temp);
for(i=0;temp[i]!=”;i++)
{
push(temp[i],&s);
}
printf(“\n\tLENGTH OF GIVEN STRING IS=%d”,i);
printf(“\n\tREVERSED STRING IS:->”);
for(i=0;temp[i]!=”;i++)
{
pop(&s);
}
printf(“\n\tLENGTH OF REVERSED STRING IS %d”,i);
}
void push(char c,struct stack *ps)
{
++(ps->top);
ps->nm[ps->top]=c;
}
pop(struct stack *ps)
{
char a;
a=ps->nm[ps->top];
printf(“%c”,a);
ps->top–;
}

output

LENGTH OF GIVEN STRING IS=6
LENGTH OF REVERSED STRING IS 6

TREE
#include
#include
#include
struct tree
{
int item;
struct tree *left,*right;
};
typedef struct tree tree;
tree *gettree(int);
int main()
{
int choice,val;
tree* root=NULL;
printf(“enter data for root node\n”);
scanf(“%d”,&val);
root=gettree(val);
while(1)
{
printf(“\n1.insert \n2.inorder \n3.preorder \n4.postorder \n5.exit”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“enter the data”);
scanf(“%d”,&val);
insert(root,val);
break;
case 2:inorder(root);
break;
case 3:preorder(root);
break;
case 4:postorder(root);
break;
case 5:exit(0);
}
}
}

tree *gettree(int d)
{
tree *temp=(tree*)malloc(sizeof(tree));
temp->left=temp->right=NULL;
temp->item=d;
return temp;
}
insert(tree *r,int d)
{
tree *ptr,*prev;
ptr=prev=r;
while(ptr!=NULL)
{
prev=ptr;
if(ptr->item>d)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(prev->item>d)
prev->left=gettree(d);
else
prev->right=gettree(d);
}
inorder(tree *r)
{
if(r==NULL)
return;
inorder(r->left);
printf(“%d\t”,r->item);
inorder(r->right);
}
preorder(tree *r)
{
if(r==NULL)
return;
printf(“%d\t”,r->item);
preorder(r->left);
preorder(r->right);
}
postorder(tree *r)
{
if(r==NULL)
return;
postorder(r->left);
postorder(r->right);
printf(“%d”,r->item);
}

OUTPUT
[user@localhost ~]\$ gcc tree.c
[user@localhost ~]\$ ./a.out
enter data for root node
20

1.insert
2.inorder
3.preorder
4.postorder
5.exit 1
enter the data 15

1.insert
2.inorder
3.preorder
4.postorder
5.exit 1
enter the data 12

1.insert
2.inorder
3.preorder
4.postorder
5.exit 1
enter the data 43

1.insert
2.inorder
3.preorder
4.postorder
5.exit 2
12 15 20 43
1.insert
2.inorder
3.preorder
4.postorder
5.exit 3
20 15 12 43
1.insert
2.inorder
3.preorder
4.postorder
5.exit 4
12 15 43 20

PROGRAMME FOR MATRIX

#include
main()
{
int a[2][2],b[2][2],c[2][2],i,j,k,t,o;
printf(“\nENTER ELEMENTS FOR FIRST MATRIX”);
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("\nENTER ELEMENTS FOR SECOND MATRIX");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
scanf("%d",&b[i][j]);
}
}
do
{
scanf("%d",&o);
switch(o)
{
case 1:
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=a[i][j]+b[i][j];
printf("\t%d",c[i][j]);
}
printf("\n");
}
break;
case 2:
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=a[i][j]-b[i][j];
printf("\t%d",c[i][j]);
}
printf("\n");
}
break;
case 3:
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]=c[i][j]+(a[i][k]+b[k][j]);
}
}
}
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("\t%d",c[i][j]);
}
printf("\n");
}
break;
}
}
while(o<4);
}

output

[user@localhost ~]\$ gcc matrix.c
[user@localhost ~]\$ ./a.out

ENTER ELEMENTS FOR FIRST MATRIX
1 1 1 1
ENTER ELEMENTS FOR SECOND MATRIX
2 2 2 2
2.SUBSTRACTION
3.MULTIPLICATION

3 3
3 3

2.SUBSTRACTION
3.MULTIPLICATION

-1 -1
-1 -1

2.SUBSTRACTION
3.MULTIPLICATION

6 6
6 6

PROGRAMME FOR BFS

#include
#include
#define TRUE 1
#define FALSE 0
#define MAX 8
struct node
{
int data;
struct node *next;
};
int visited [MAX];
int q[8];
int front,rear;
void bfs(int,struct node**);
struct node* getnode_write(int);
int delqueue();
int isempty();
void del(struct node*);
main()
{
struct node*arr[MAX];
struct node*v1,*v2,*v3,*v4;
int i;
v1=getnode_write(2);
arr[0]=v1;
v1->next=v2=getnode_write(3);
v2->next=NULL;
v1=getnode_write(1);
arr[1]=v1;;
v1->next=v2=getnode_write(4);
v2->next=v3=getnode_write(5);
v3->next=NULL;
v1=getnode_write(1);
arr[2]=v1;
v1->next=v2=getnode_write(6);
v2->next=v3=getnode_write(7);
v3->next=NULL;
v1=getnode_write(2);
arr[3]=v1;
v1->next=v2=getnode_write(8);
v2->next=NULL;
v1=getnode_write(2);
arr[4]=v1;
v1->next=v2=getnode_write(8);
v2->next=NULL;
v1=getnode_write(3);
arr[5]=v1;
v1->next=v2=getnode_write(8);
v2->next=NULL;
v1=getnode_write(3);
arr[6]=v1;
v1->next=v2=getnode_write(8);
v2->next=NULL;
v1=getnode_write(4);
arr[7]=v1;
v1->next=v2=getnode_write(5);
v2->next=v3=getnode_write(6);
v3->next=v4=getnode_write(7);
v4->next=NULL;
front=rear=-1;
bfs(1,arr);
for(i=0;idata-1]==FALSE)
{
visited[u->data-1]=TRUE;
printf(“%d\t”,u->data);
}
u=u->next;
}
}
}
struct node* getnode_write(int val)
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=val;
return newnode;
}
{
q if(rear==MAX-1)
{
printf(“\n QUEUE IS FULL”);
return;
}
rear++;
q[rear]=vertex;
if(front==-1)
front=0;
}
int delqueue()
{
int data;
if(front==-1)
{
printf(“\n QUEUE IS EMPTY”);
return;
}
data=q[front];
if(front==rear)
front=rear=-1;
else
front++;
return data;
}
int isempty()
{
if(front==-1)
return TRUE;
return FALSE;
}
void del (struct node*n)
{
struct node *temp;
while(n!=NULL)
{
temp=n->next;
free(n);
n=temp;
}
}
OUTPUT

[user@localhost ~]\$ gcc bfs.c
[user@localhost ~]\$ ./a.out
1 2 3 4 5 6 7 8

#include
#include
#define getnode() (que *)malloc(sizeof(que))
typedef struct que
{
int info;
struct que *next;
}que;
que *insert(que *e);
que *del(que *e);
void disp(que *e);

que e;
main()
{
que *q=NULL;

int o;

do
{
scanf(“%d”,&o);

switch(o)
{
case 1:
q=insert(q);
break;

case 2:
q=del(q);
break;

case 3:
disp(q);
break;

}
}
while(oinfo);
n->next=NULL;
if(e)
{
p=e;
while(e->next!=NULL)
{
e=e->next;
}
e->next=n;

}
else
p=n;
return p;
}

que *del(que *e)
{
que *p;
if(e)
{
p=e;
e=e->next;
printf(“THE DELETED ELEMENT IS %d”,p->info);
free(p);
}
else
printf(“\nQUE IS EMPTY”);
return e;
}

void disp(que *e)
{
if(e)
{
while(e!=NULL)
{
printf(“\n%d”,e->info);
e=e->next;
}
}
}

OUTPUT
[user@localhost ~]\$ ./a.out
1.INSERT
2.DELETE
3.DISPLAY
ENTER ELEMENT11
1.INSERT
2.DELETE
3.DISPLAY
ENTER ELEMENT22
1.INSERT
2.DELETE
3.DISPLAY
11 22

3. Program for Merge Sort
———————-
#include
#include

void merge(int *,int,int,int);

void mergesort(int *data,int first,int last)
{
int mid;
if(first < last) //If more than one element
{
mid = (first + last) / 2; //Find mid
mergesort(data,first,mid); //Sort Left Subarray
mergesort(data,mid + 1,last); //Sort Right Subarray
merge(data,first,mid,last); //Merge Left and Right Subarray
}
}

void merge(int *data,int first,int mid,int last)
{
int i,j,k;
i = first;
j = mid + 1;
k = 0;
int *temp = new int[last – first + 2];
while(i <= mid && j <= last) //While the end of Left or Right Subarray
{
//Compare data and save to temporary array
if(data[i] < data[j])
temp[k++] = data[i++];
else
temp[k++] = data[j++];
}

if(i <= mid) //If more items in Left Subarray
for(j = i;j <= mid;j++) //Copy items to temp
temp[k++] = data[j];
else //more items in Right Subarray
for(i = j;i <= last;i++)
temp[k++] = data[i];

k = 0;
for(i = first;i <= last;i++) //Copy items from temporary array to original array
data[i] = temp[k++];
}

int main()
{
int n,*arr;
clrscr();
cout <> n;
arr = new int[n];
cout << "\nEnter Elements : ";
for(int i = 0;i > arr[i];

mergesort(arr,0,n – 1); //Sort
cout << endl << "\nSorted : ";
for(int i = 0;i < n;i++)
cout << arr[i] << ' ';

getch();
return 0;
}

Program for Quick Sort
———————-
#include
#include

void swap(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}

int partition(int a[],int p,int q)
{
int i = p;
for(int j = p + 1;j <= q;j++) //from Second element to Last
if(a[j] <= a[p]) //assign smaller element to Left of pivot
{
i++;
swap(a[i],a[j]);
}

swap(a[p],a[i]); //set Pivot
return i;
}

void QuickSort(int *a,int p,int q)
{
if(p < q)
{
int r = partition(a,p,q); //Find Pivot
QuickSort(a,p,r – 1); //sort Left Subarray
QuickSort(a,r + 1,q); //sort Right Subarray
}
}

int main()
{
int num[50],n;
cout <> n;
cout << "\nEnter " << n << " Numbers\n";
for(int i = 0;i > num[i];

QuickSort(num,0,n – 1); //call function QuickSort with pivot at First position

cout << endl;
for(int i = 0;i < n;i++)
cout << num[i] << ' ';

getch();
return 0;
}