MERGE SORT

/* merge sort*/

#include<stdio.h>

#define MAX 20

int a[MAX];

void merge(int low,int mid,int high)

{

    int temp[MAX];

    int i=low;

    int j=mid+1;

    int k=low;

    while((i<=mid)&&(j<=high))

    {

        if(a[i]<=a[j])

            temp[k++]=a[i++];

        else

            temp[k++]=a[j++];

    }

    while(i<=mid)

        temp[k++]=a[i++];

    while(j<=high)

        temp[k++]=a[j++];

    for(i=low;i<=high;i++)

        a[i]=temp[i];

}

void merge_sort(int low,int high)

{

    int mid;

    if(low!=high)

    {

        mid=(low+high)/2;

        merge_sort(low,mid);

        merge_sort(mid+1,high);

        merge(low,mid,high);

    }

}

main()

{

    int i,n;

    printf("\nEnter the number of elements:");

    scanf("%d",&n);

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

    {

        printf("\nEnter element %d:",i+1);

        scanf("%d",&a[i]);

    }

    printf("\nUnsorted list is:\n ");

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

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

    merge_sort(0,n-1);

    printf("\nSorted list is:\n");

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

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

}

                             .......OUTPUT....

Enter the number of elements:5

Enter element 1:6

Enter element 2:3

Enter element 3:9

Enter element 4:4

Enter element 5:2

Unsorted list is:

 6      3       9       4       2

Sorted list is:

2       3       4       6       9

QUICK SORT

/* quick sort*/

#include<stdio.h>

int a[20],n;

void sort(int a[],int lb,int ub)

{

          int p;

          if(lb>=ub)

                   return;

          p=partetion(a,lb,ub);

          sort(a,lb,p-1);

          sort(a,p+1,ub);

}

int partetion(int a[],int lb,int ub)

{

          int down,up,key,t;

          down=lb;

          up=ub;

          key=a[lb];

          while(down<up)

          {

                   while((key>=a[down]) &&(down<up))

                             down++;

                   while(key<a[up])

                             up--;

                   if(down<up)

                   {

                             t=a[down];

                             a[down]=a[up];

                             a[up]=t;

                   }

          }

          a[lb]=a[up];

          a[up]=key;

          return up;

}

main()

{

          int i;

          printf("enter the number of elements:");

          scanf("%d",&n);

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

          {

                   printf("enter element %d:",i);

                   scanf("%d",&a[i]);

          }

          printf("unsorted list:");

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

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

          sort(a,1,n);

          printf("\nsorted list:\n");

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

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

}

                   .......OUTPUT.......

enter the number of elements:5

enter element 1:6

enter element 2:9

enter element 3:3

enter element 4:1

enter element 5:7

unsorted list:  6       9       3       1       7

sorted list:

1       3       6       7       9      

program to implement circular queue

#include<stdio.h>
#define MAX 10
int que[MAX];
int front=-1;
int rear=-1;
void insert();
void del();
void disp();
 main()
{
    int ch;
    while(1)
    {
    printf("\n..................MENU................\n");
    printf("select your choice\n");
    printf("1.insert\n");
    printf("2.delete\n");
    printf("3.display\n");
    printf("4.exit\n");
    printf("enter your choice:");
    scanf("%d",&ch);
    switch(ch)
    {

        case 1:
        insert();
        break;
        case 2:
        del();
        break;
        case 3:
        disp();
        break;
        case 4:
        exit(1);
        default :
        printf("invalid choice\n");

         }
    }
}
void insert()
{
    int val;
    if((front==0&&rear==MAX-1)||(front==rear+1))
    {
    printf("queue overflow\n");
    return;
    }
    if(front==-1)
    {
        front=0;
        rear=0;

    }
    else
        if(rear==MAX-1)
        {
            rear=0;
        }
        else
        rear=rear+1;
        printf("enter the element for insertion in queue:");
        scanf("%d",&val);
        que[rear]=val;

}
void del()
{
    if(front==-1)
    {
        printf("queue underflow\n");
        return;

    }
    printf("element deleted from queue is=%d",que[front]);
    if(front==rear)
    {
        front=-1;
        rear=-1;
    }
    else
        if(front==MAX-1)
        {
            front=0;
        }
        else
        front=front+1;

}
void disp()
{
    int f=front,r=rear;
    if(front==-1)
    {
        printf("queue is empty\n");
        return;

    }
    printf("queue elements:\n");
    if(f<=r)
    while(f<=r)
    {
        printf("%d\t",que[f]);
        f++;
    }
    else
    {
        while(f<=MAX-1)
        {
            printf("%d\t",que[f]);
            f++;

        }
        f=0;
        while(f<=r)
        {

            printf("%d\t",que[f]);
            f++;
        }
    }
}



                         OUTPUT

..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:1
enter the element for insertion in queue:1

..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:1
enter the element for insertion in queue:2

..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:1
enter the element for insertion in queue:3

..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:3
queue elements:
1       2       3
..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:2
element deleted from queue is=1
..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:2
element deleted from queue is=2
..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:2
element deleted from queue is=3
..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:1
enter the element for insertion in queue:8

..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:3
queue elements:
8
..................MENU................
select your choice
1.insert
2.delete
3.display
4.exit
enter your choice:4

Process returned 1 (0x1)   execution time : 53.552 s
Press any key to continue.

program to implement circular linkedlist

#include<malloc.h>
void disp();
void create(int data);
void insertbeg(int data);
void insertbet(int data,int pos);
void del(int data);
void count();
void search(int data);
struct node
{
    int info;
    struct node *link;

}*last=NULL;
main()
{
int m,pos,i,n,ch;
while(1)
{
printf("\n\n\n........MENU..........\n");
printf("\n1.create list\n");
printf("2.dispaly\n");
printf("3.insert at bigining\n");
printf("4.insert in between\n");
printf("5.delete\n");
printf("6.count\n");
printf("7.search\n");
printf("8.exit\n");
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)

{
    case 1:
    printf("how many nodes:");
    scanf("%d",&n);
    printf("enter the element:\n");
    for(i=0;i<n;i++)
    {

        scanf("%d",&m);
        create(m);
    }
    break;
    case 2:
    disp();
    break;
    case 3:
    printf("enter element:");
    scanf("%d",&m);
    insertbeg(m);
    break;
    case 4:
    printf("enter element:");
    scanf("%d",&m);
    printf("enter the position:");
    scanf("%d",&pos);
    insertbet(m,pos);
    break;
    case 5:
    printf("enter the element:");
    scanf("%d",&m);
    del(m);
    break;

    case 6:
    count();
    break;
    case 7:
    printf("enter the element you want to search:");
    scanf("%d",&m);
    search(m);
    break;
    case 8:
    exit(1);
}

}

}

void create(int data)
{
    struct node *q,*tmp;
    tmp=malloc(sizeof(struct node ));
    tmp->info=data;

    if(last==NULL)
    {
        last=tmp;
        tmp->link=last;

    }
    else
    {
        tmp->link=last->link;
        last->link=tmp;
        last=tmp;

    }
    return;
}
void disp()
{
    struct node *q;
    if(last==NULL)
    {
        printf("list is empty\n");
        return;

    }
    printf("the list is:\n");
    q=last->link;
    while(q!=last)
    {
        printf("%d-->",q->info);
        q=q->link;

    }printf("%d",last->info);
}
void insertbeg(int data)
{

    struct node *tmp;
    tmp=malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=last->link;
    last->link=tmp;

}
void insertbet(int data,int pos)
{
    struct node *q,*tmp;
    int i;
    q=last;
    for(i=0;i<pos-1;i++)
    {

        q=q->link;
        if(q->link==last)
         {
        printf("there is less than %d element\n",pos);
        return;
         }
    }
    tmp=malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=q->link;
    q->link=tmp;
}

void del(int data)
{

    struct node *tmp,*q;
    if((last->link==last)&&(last->info==data))
    {
        tmp=last;
        last=NULL;
        free(tmp);

    }
    q=last->link;
    if(q->info==data)
    {
        tmp=q;
        last->link=q->link;
        free(tmp);
        return;
    }
    q=last;
    while(q->link!=last)
    {
        if(q->link->info==data)
        {
            tmp=q->link;
            q->link=tmp->link;
            free(tmp);

        }
        q=q->link;

    }
    if(q->link->info==data)
    {
        tmp=q->link;
        q->link=last->link;
        free(tmp);
        last=q;
        return;
    }

}
void count()
{
    struct node *q;
    int cnt=0;
    if(last==NULL)
    printf("list is empty\n");
    else
    {
        q=last;
        do
        {

            cnt=cnt+1;
            q=q->link;
        }while(q!=last);
        printf("number of items=%d\n",cnt);

        }
    }


void search(int data)
{
    struct node *q;
    if(last==NULL)
    printf("list is empty\n");
    else
    {
        q=last;
        do
        {
            if(q->info==data)
            {
            printf("element is fount\n");
            return;
            }
            q=q->link;
    }while(q!=last);
printf("searched element is not found\n");
return;
}
}
#include<malloc.h>
void disp();
void create(int data);
void insertbeg(int data);
void insertbet(int data,int pos);
void del(int data);
void count();
void search(int data);
struct node
{
    int info;
    struct node *link;

}*last=NULL;
main()
{
int m,pos,i,n,ch;
while(1)
{
printf("\n\n\n........MENU..........\n");
printf("\n1.create list\n");
printf("2.dispaly\n");
printf("3.insert at bigining\n");
printf("4.insert in between\n");
printf("5.delete\n");
printf("6.count\n");
printf("7.search\n");
printf("8.exit\n");
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)

{
    case 1:
    printf("how many nodes:");
    scanf("%d",&n);
    printf("enter the element:\n");
    for(i=0;i<n;i++)
    {

        scanf("%d",&m);
        create(m);
    }
    break;
    case 2:
    disp();
    break;
    case 3:
    printf("enter element:");
    scanf("%d",&m);
    insertbeg(m);
    break;
    case 4:
    printf("enter element:");
    scanf("%d",&m);
    printf("enter the position:");
    scanf("%d",&pos);
    insertbet(m,pos);
    break;
    case 5:
    printf("enter the element:");
    scanf("%d",&m);
    del(m);
    break;

    case 6:
    count();
    break;
    case 7:
    printf("enter the element you want to search:");
    scanf("%d",&m);
    search(m);
    break;
    case 8:
    exit(1);
}

}

}

void create(int data)
{
    struct node *q,*tmp;
    tmp=malloc(sizeof(struct node ));
    tmp->info=data;

    if(last==NULL)
    {
        last=tmp;
        tmp->link=last;

    }
    else
    {
        tmp->link=last->link;
        last->link=tmp;
        last=tmp;

    }
    return;
}
void disp()
{
    struct node *q;
    if(last==NULL)
    {
        printf("list is empty\n");
        return;

    }
    printf("the list is:\n");
    q=last->link;
    while(q!=last)
    {
        printf("%d-->",q->info);
        q=q->link;

    }printf("%d",last->info);
}
void insertbeg(int data)
{

    struct node *tmp;
    tmp=malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=last->link;
    last->link=tmp;

}
void insertbet(int data,int pos)
{
    struct node *q,*tmp;
    int i;
    q=last;
    for(i=0;i<pos-1;i++)
    {

        q=q->link;
        if(q->link==last)
         {
        printf("there is less than %d element\n",pos);
        return;
         }
    }
    tmp=malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=q->link;
    q->link=tmp;
}

void del(int data)
{

    struct node *tmp,*q;
    if((last->link==last)&&(last->info==data))
    {
        tmp=last;
        last=NULL;
        free(tmp);

    }
    q=last->link;
    if(q->info==data)
    {
        tmp=q;
        last->link=q->link;
        free(tmp);
        return;
    }
    q=last;
    while(q->link!=last)
    {
        if(q->link->info==data)
        {
            tmp=q->link;
            q->link=tmp->link;
            free(tmp);

        }
        q=q->link;

    }
    if(q->link->info==data)
    {
        tmp=q->link;
        q->link=last->link;
        free(tmp);
        last=q;
        return;
    }

}
void count()
{
    struct node *q;
    int cnt=0;
    if(last==NULL)
    printf("list is empty\n");
    else
    {
        q=last;
        do
        {

            cnt=cnt+1;
            q=q->link;
        }while(q!=last);
        printf("number of items=%d\n",cnt);

        }
    }


void search(int data)
{
    struct node *q;
    if(last==NULL)
    printf("list is empty\n");
    else
    {
        q=last;
        do
        {
            if(q->info==data)
            {
            printf("element is fount\n");
            return;
            }
            q=q->link;
    }while(q!=last);
printf("searched element is not found\n");
return;
}
}

                                        OUTPUT

........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:1
how many nodes:5
enter the element:
1
2
3
4
5



........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:2
the list is:
1-->2-->3-->4-->5


........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:3
enter element:6



........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:2
the list is:
6-->1-->2-->3-->4-->5


........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:4
enter element:7
enter the position:5



........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:2
the list is:
6-->1-->2-->3-->7-->4-->5


........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:5
enter the element:7



........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:2
the list is:
6-->1-->2-->3-->4-->5


........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:6
number of items=6



........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:7
enter the element you want to search:8
searched element is not found



........MENU..........

1.create list
2.dispaly
3.insert at bigining
4.insert in between
5.delete
6.count
7.search
8.exit
enter your choice:8

Process returned 1 (0x1)   execution time : 94.079 s
Press any key to continue.

program to implement stack using linked list

#include<stdio.h>
#include<malloc.h>
void disp();
void push(int data);
void pop();
struct node
{
    int info;
    struct node *link;

}*top=NULL;
main()
{
int ch,i,m;
while(1)
{
printf("\n..............MENU...........\n");
printf("\n1.push element\n");
printf("2.pop element\n");
printf("3.display\n");
printf("4.exit\n");
printf("enter your choice:");
scanf("%d",&ch);
switch(ch)

{
    case 1:
      printf("\nenter the element:");
    scanf("%d",&m);
    push(m);
    break;
    case 2:
    pop();
    break;
    case 3:
    disp();
    break;
    case 4:
    exit(1);
}

}

}

void push(int data)
{
    struct node *tmp;

    tmp=malloc(sizeof(struct node));
    tmp->info=data;
    tmp->link=top;
    top=tmp;
}
void pop()
{
    struct node *tmp;
    tmp=malloc(sizeof(struct node));

    if(top==NULL)
    printf("stack is empty\n");
    else
    {
      tmp=top;
      printf("popped item=%d\n",tmp->info);
        top=top->link;
        tmp->link=NULL;
        free(tmp);
    }


}
void disp()
{

    struct node *tmp;
    tmp=top;
    if(top==NULL)
    printf("stack is empty\n");
    else
    {

      printf("stack elements\n");
      while(tmp!=NULL)
      {
          printf("%d\t",tmp->info);
          tmp=tmp->link;
      }
    }
}


                    OUTPUT


..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:1

enter the element:1

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:1

enter the element:2

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:1

enter the element:3

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:3
stack elements
3       2       1
..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:2
popped item=3

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:2
popped item=2

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:2
popped item=1

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:2
stack is empty

..............MENU...........

1.push element
2.pop element
3.display
4.exit
enter your choice:4

Process returned 1 (0x1)   execution time : 26.988 s
Press any key to continue.

program to implement stack using array

#include<stdio.h>
#define MAX 10
void push(int stack[MAX],int *top,int val);
void pop(int stack[MAX],int *top,int *val);
void tra(int stack[MAX],int *top);
main()
{
    int stack[MAX],top=-1,n,val,ch;
    while(1)
    {
    printf("\n..............MENU..............\n");
    printf("\nselect your choice\n");
    printf("1.push\n");
    printf("2.pop\n");
    printf("3.traverse\n");
    printf("4.exit\n");
    printf("enter your choice:");
    scanf("%d",&ch);
    switch(ch)
    {
        case 1:
        printf("enter the element to be pushed:");
        scanf("%d",&val);
        push(stack,&top,val);
        break;
        case 2:
        pop(stack,&top,&val);

        break;
        case 3:
        tra(stack,&top);
        break;
        case 4:
        exit(1);
        default :
        printf("invalid choice\n");

    }
}}

void push(int stack[MAX],int *top,int val)
{
    if(*top<MAX)
    {
        *top=*top+1;
        stack[*top]=val;
    }
    else
    {
        printf("the stack is full can not push a value\n");
        return;
    }
}
void pop(int stack[MAX],int *top,int *val)
{
    if(*top>=0)
    {
        *val=stack[*top];
        *top=*top-1;
        printf("the value poped is %d",*val);
    }
    else
    {
        printf("the stack is empty \n");
        return;
    }
}
void tra(int stack[MAX],int *top)
{
    int i;
    if(*top==-1)
    {
        printf("the stack is empty\n");
        return;
    }
    else
    {
        printf("the elements in the stack are\n");
        for(i=*top;i>=0;i--)
        printf("%d\t",stack[i]);
    }
}

                               OUTPUT

..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:1
enter the element to be pushed:1

..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:1
enter the element to be pushed:2

..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:1
enter the element to be pushed:3

..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:3
the elements in the stack are
3       2       1
..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:2
the value poped is 3
..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:2
the value poped is 2
..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:2
the value poped is 1
..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:2
the stack is empty

..............MENU..............

select your choice
1.push
2.pop
3.traverse
4.exit
enter your choice:4

Process returned 1 (0x1)   execution time : 32.152 s
Press any key to continue.