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) ).

About these ads

3 thoughts on “Complexity of merge sort”

  1. Simgly Linked list
    using System;
    using System.Collections.Generic;
    using System.Text;

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

    public void addNode()
    {
    int rollNo;
    string nm;
    Console.Write(“\nEnter the roll number of the student:”);
    rollNo = Convert.ToInt32(Console.ReadLine());
    Console.Write(“\nEnter the name of the student: “);
    nm = Console.ReadLine();
    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(“\nMenu”);
    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”);
    Console.Write(“\nEnter your choice(1-5):”);
    char ch = Convert.ToChar(Console.ReadLine());
    switch (ch)
    {
    case ’1′:
    {
    obj.addNode();
    }
    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: “);
    int rollNo = Convert.ToInt32(Console.ReadLine());
    Console.WriteLine();
    if (obj.delNode(rollNo) == false)
    Console.WriteLine(“\nRecord not found.”);
    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: “);
    int num = Convert.ToInt32(Console.ReadLine());
    if (obj.Search(num, ref previous, ref current) == false)
    Console.WriteLine(“\nRecord not found.”);
    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. 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


    PROGRAMME FOR RADIX SORT

    #include
    #define max 100
    int a[max],n,i;
    main()
    {
    void input (void);
    input();
    }
    void input(void)
    {
    void output (int a[],int n);
    void radix_sort (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]);
    }
    radix_sort(a,n);
    printf("\n sorted array is:\n");
    output(a,n);
    }
    void radix_sort (int a[],int 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[


    Progrmme for circulink list

    #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”);
    printf(“\n enter your choice:”);
    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));
    printf(“\n please insert item:”);
    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 ~]$ gcc circulink.c
    [user@localhost ~]$ ./a.out
    1.insert
    2.delete
    3.display
    4.exit
    enter your choice:1
    please insert item:22
    1.insert
    2.delete
    3.display
    4.exit
    enter your choice:1
    please insert item:33
    1.insert
    2.delete
    3.display
    4.exit
    enter your choice:1
    please insert item:44
    1.insert
    2.delete
    3.display
    4.exit
    enter your choice:3
    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+

    LINKED LIST
    #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”);
    printf(“\n enter your choice:”);
    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));
    printf(“\n please insert item:”);
    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
    Enter your choice: 1
    Please insert item: 11
    1.insert
    2.delete
    3.display
    4.return
    Enter your choice: 1
    Please insert item: 2
    1.insert
    2.delete
    3.display
    4.return
    Enter your choice: 2
    Enter the value which you want to delete:22
    Value deleted 22
    1.insert
    2.delete
    3.display
    4.return
    Enter your choice: 3
    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
    Enter your expression A+B

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


    PROGRAMME FOR QUEUE USING POINTER
    #include
    #include
    struct queue
    {
    int no;
    struct queue*next;
    }
    *start=NULL;
    void add();
    int dle();
    void traverse();
    main()
    {
    int ch;
    char choice;
    do
    {
    printf(“\n\t\t 1.add”);
    printf(“\n\t\t 2.dlete”);
    printf(“\n\t\t 3.traverse”);
    printf(“\n\t\t 4.exit”);
    printf(“\n\t Enter your choice “);
    scanf(“%d”,&ch);
    switch(ch)
    {
    case 1:add();
    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);
    }
    void add()
    {
    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
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 1
    Enter the data11
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 1
    Enter the data22
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 1
    Enter the data33
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 3
    no=11no=22no=33
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 2
    the dlete element is 11
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 2
    the dlete element is 22
    1.add
    2.dlete
    3.traverse
    4.exit
    Enter your choice 3
    no=33
    1.add
    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”);
    printf(“\n ENTER YOUR CHOICE:”);
    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));
    printf(“\n PLEASE ENTER ITEM:”);
    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
    ENTER YOUR CHOICE:1

    PLEASE ENTER ITEM:2

    1.push
    2.pop
    3.display
    4.exit
    ENTER YOUR CHOICE:1

    PLEASE ENTER ITEM:3

    1.push
    2.pop
    3.display
    4.exit
    ENTER YOUR CHOICE:1

    PLEASE ENTER ITEM:4

    1.push
    2.pop
    3.display
    4.exit
    ENTER YOUR CHOICE:3
    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];
    printf(“\n\tENTER YOUR STRING:”);
    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

    ENTER YOUR STRING:ADARSH
    LENGTH OF GIVEN STRING IS=6
    REVERSED STRING IS:->HSRADA
    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
    {
    printf("\n1.ADDITION\n2.SUBSTRACTION\n3.MULTIPLICATION\n\nENTER YOUR OPTION");
    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
    1.ADDITION
    2.SUBSTRACTION
    3.MULTIPLICATION

    ENTER YOUR OPTION1
    3 3
    3 3

    1.ADDITION
    2.SUBSTRACTION
    3.MULTIPLICATION

    ENTER YOUR OPTION2
    -1 -1
    -1 -1

    1.ADDITION
    2.SUBSTRACTION
    3.MULTIPLICATION

    ENTER YOUR OPTION3
    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);
    void addqueue(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)
    {
    addqueue(u->data);
    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;
    }
    void addqueue(int vertex)
    {
    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  
    PROGRAMME FOR QUEUE AS LINKLIST

    #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
    {
    printf(“\n1.INSERT\n2.DELETE\n3.DISPLAY\n\nENTER YOUR OPTION”);
    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 YOUR OPTION1
    ENTER ELEMENT11
    1.INSERT
    2.DELETE
    3.DISPLAY
    ENTER YOUR OPTION 1
    ENTER ELEMENT22
    1.INSERT
    2.DELETE
    3.DISPLAY
    ENTER YOUR OPTION3
    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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s