c2java: Data Structures

Introduction

For every computer application, it is mandatory to maintain the data.
While storing data, if we arrange the data in a particular structure, that can be processed efficiently at later time.
To structure the data Number of Algorithms proposed and functions defined to access the data.

The algorithms of type

Linear data structure
Non-linear data structure.

Linear : In Linear data structures, the data will be arranged sequentially and one element is connected to only one element.
    1) Array
    2) Stack
    3) Queue
    4) Linked List

Non-linear : In Non-linear data structure, data will be UN-structured, and one element is connected to more than one element.
    1) Trees
    2) Graphs

                                   Stack

Linear data structure.
Based on the rule LIFO(Last In First Out).
Implementing either by using static arrays or dynamic arrays.
In stack data structure, inserting the data as well as retrieving the data is possible only from one end that is, "top"
static stack fixed in size.
dynamic stack grows in nature depends on insertion of elements.

/*Implementation of stack using static arrays*/

#include<stdio.h>
#define MAX 5
void push(void);
void pop(void);
void traverse(void);
int stack[MAX], top = -1;
void main()
{
    int ch;
    while(1)
    {
       printf("1.push\n");
       printf("2.pop\n");
       printf("3.traverse\n");
       printf("4.exit\n");

       printf("Enter ur choice : ");
       scanf("%d",&ch);

       switch(ch)
       {
           case 1 :   push();
                       break;
           case 2 :   pop();
                       break;
           case 3 :   traverse();
                       break;
           case 4 :   exit(1);
           default :   printf("invalid choice\n");
       }
    }
}
void push(void)
{
    int ele;
    if(top == MAX-1)
    {
       printf("stack is overflow\n");
       return;
    }
    printf("Enter element to be pushed : ");
    scanf("%d",&ele);
    top++;
    stack[top]=ele;
}

void pop(void)
{
    int ele;
    if(top==-1)
    {
       printf("stack is underflow\n");
    }
    else
    {
       ele = stack[top];
       printf("deleted element : %d\n",ele);
       top--;
    }
}

void traverse(void)
{
    int i;
    if(top==-1)
    {
       printf("stack is underflow\n");
    }
    else
    {
       for(i=top ; i>=0 ; i--)
       {
           printf("%d\t",stack[i]);
       }
       printf("\n");
    }
}

Stack implementation using Dynamic Arrays

Allocating memory dynamically to array variable :
    stdlib.h header file contains pre-defined functions to allocate and De-allocate the memory.

    void* calloc(size_t n, size_t size);

size_t represent unsigned integer value in most of the compilers.
first argument specifies number of elements in the array.
second argument specifies size of each element.
calloc() function allocates n*size bytes memory block and returns first byte address.
All the memory locations are initialized with zero.
On success, it returns pointer to that allocated block.
On failure, it returns NULL.

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int *ptr, n, *i;
    printf("Enter size of array : ");
    scanf("%d",&n);

    ptr = (int*)calloc(n,sizeof(int));
    if(ptr == NULL)
    {
       printf("Out of memory\n");
       exit(1);
    }

    printf("Enter %d elements\n",n);
    for(i=ptr ; i<ptr+n ; i++)
    {
       scanf("%d",i);
    }

    printf("Elements are\n",n);
    for(i=ptr ; i<=ptr+n ; i++)
    {
       printf("%d\n",*i);
    }
    return 0;
}

realloc () :

The drawback of calloc() function is that once the memory has been allocated, that cannot be increased or decreased.
To avoid that problem, they introduced realloc() function.
It is used to increase or decrease the size of memory block which has already allocated to another variable.
It will re-aquire the memory while modifying the block.

prototype :
void* realloc(void* ptr, size_t size);

first argument specifies, the block address from where it has re-aquire the space.
second argument specifies, size of new block.

#include<stdio.h>
#include<stdlib.h>
#define CAPACITY 5
void push(void);
void pop(void);
void traverse(void);
int *stack, n=0, *j, *top;
int main()
{
int ch;
stack = (int*)calloc(CAPACITY,sizeof(int));
top = stack;
while(1)
{
printf("1.push\n");
printf("2.pop\n");
printf("3.traverse\n");
printf("4.exit\n");

printf("Enter ur choice : ");
scanf("%d",&ch);

switch(ch)
{
case 1 : push();
break;
case 2 : pop();
break;
case 3 : traverse();
break;
case 4 : exit(1);
default : printf("invalid choice\n");
}//end of switch
}//end of while
return 0;
}

void push(void)
{
++n;
if(n<=CAPACITY)
{
printf("Enter element to be pushed : ");
scanf("%d",top++);
}
else
{
stack = (int*)realloc(stack , n*sizeof(int));
printf("Enter element to be pushed : ");
scanf("%d",top++);
}
}

void traverse(void)
{
if(n==0)
{
printf("stack is empty\n");
return;
}
for(j=stack ; j<stack+n ; j++)
{
printf("%d\n",*j);
}
}

void pop(void)
{
if(n==0)
{
printf("stack is empty\n");
return;
}
--n;
printf("deleted item is : %d\n",*(--top));
stack = (int*)realloc(stack , n*sizeof(int));

}

Single Linked List Operations

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *link;
}*root=NULL;
int count=0,ch;
void append();
void addatbegin();
void addatafter();
void display();
void delete();
void reverse();
void swapadjecency();
void swapnodes();
void sort();
int main()
{
    printf("SINGLE LINKED LIST OPERATIONS\n");
    while(1)
    {
        printf("1.Append node\n");
        printf("2.Add at begin\n");
        printf("3.Add after node\n");
        printf("4.Delete\n");
        printf("5.Display\n");
        printf("6.Reverse list\n");
        printf("7.Swap adjecency\n");
        printf("8.Swap nodes\n");
        printf("9.Sort list\n");
        printf("10.Exit\n");

        printf("Enter ur choice :");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1    :    append();
                        break;
            case 2    :    addatbegin();
                        break;
            case 3    :    addatafter();
                        break;
            case 4    :    delete();
                        break;
            case 5    :    display();
                        break;
            case 6    :    reverse();
                        break;
            case 7    :    swapadjecency();
                        break;
            case 8    :    swapnodes();
                        break;
            case 9    :    sort();
                        break;
            case 10    :    exit(0);
            default    :    printf("Invalid choice\n");
        }
    }
}

void append()
{
    struct node *temp,*p;
    p=(struct node *)malloc(sizeof(struct node));
    printf("Enter the data :");
    scanf("%d",&p->data);
    p->link=NULL;
    count++;
    if(root==NULL)
    {
        root=p;
    }
    else
    {
        temp=root;
        while(temp->link!=NULL)
        {
            temp=temp->link;
        }
        temp->link=p;
    }
}

void addatbegin()
{
    struct node *p;
    p=(struct node *)malloc(sizeof(struct node));
    printf("Enter data :\n");
    scanf("%d",&p->data);
    count++;
    p->link=root;
    root=p;
}

void addatafter()
{
    struct node *temp,*p;
    int loc,i=1;
    printf("Enter location :");
    scanf("%d",&loc);
    if(loc>count)
    {
        printf("invalid location\n");
        printf("currently list having %d nodes\n",count);
        return;
    }
    p=(struct node *)malloc(sizeof(struct node));
    printf("Enter data :\n");
    scanf("%d",&p->data);
    count++;
    temp=root;
    while(i<loc)
    {
        temp=temp->link;
        i++;
    }
    p->link=temp->link;
    temp->link=p;
}
void delete()
{
    struct node *temp,*p;
    int i=1,loc;
    printf("Enter location :");
    scanf("%d",&loc);
    if(loc>count)
    {
        printf("invalid location\n");
        printf("currently list having %d nodes\n",count);
        return;
    }
    temp=root;
    if(loc==1)
    {
        root=temp->link;
        temp->link=NULL;
        free(temp);
        count--;
    }
    else
    {
        temp = root;
        while(i<loc-1)
        {
            temp=temp->link;
            i++;
        }
        p=temp->link;
        temp->link=p->link;
        p->link=NULL;
        free(p);
        count--;
    }
}
void display()
{
    struct node *temp;
    temp=root;
    if(temp==NULL)
    {
        printf("No nodes in the list\n");
        return;
    }
    printf("List elements are :\t");
    while(temp!=NULL)
    {
        printf("%d->",temp->data);
        temp=temp->link;
     }
     printf("\n\n");
}

void reverse()
{
    int i,j,k,temp;
    struct node *p,*q;
    i=1;
    j=count;
    p=root;
    while(i<j)
    {
        q=root;
        k=1;
        while(k<j)
        {
            q=q->link;
            k++;
        }
        i++;
        j--;
        temp = p->data;
        p->data = q->data;
        q->data = temp;
        p = p->link;
    }
}
void swapadjecency()
{
    struct node *p,*q;
    int i=1,loc,temp;
    printf("Enter location :");
    scanf("%d",&loc);
    if(loc>count)
    {
        printf("invalid input\n");
        printf("currently list having %d nodes\n",count);
        return;
    }
    else if(loc==count)
    {
        printf("no adjecency for last node\n");
        return;
    }
    p=root;
    while(i<loc)
    {
        p=p->link;
        i++;
    }
    q = p->link;
    temp = p->data;
    p->data = q->data;
    q->data = temp;

}
void swapnodes()
{
    struct node *p,*q;
    int i=1,j=1,loc1,loc2,temp;

    printf("Enter loc1 :");
    scanf("%d",&loc1);

    printf("Enter loc2 :");
    scanf("%d",&loc2);

    if(loc1>count || loc2>count)
    {
        printf("invalid locations\n");
        printf("currently list having %d nodes\n",count);
        return;
    }
    p=root;
    q=root;
    while(i<loc1)
    {
        p=p->link;
        i++;
    }
    while(j<loc2)
    {
        q = q->link;
        j++;
    }
    temp = p->data;
    p->data = q->data;
    q->data = temp;

}
void sort()
{
    int i,j,k,temp,n;
    struct node *p, *q ;
    n=count;
    for(i=0 ; i<n-1 ; i++)
    {
        p = root ;
        q = p->link ;

        for(j=0 ; j<n-1-i ; j++)
        {
            if(p->data > q->data)
            {
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            p=p->link;
            q=q->link;
        }
    }
}

Stack Implementation using Single Linked List

#include<stdio.h>
struct node
{
   int data;
   struct node *link;
}*top = NULL;
void push(void);
void pop(void);
void traverse(void);
void main()
{
   int ch;
   while(1)
   {
       printf("1.push\n");
       printf("2.pop\n");
       printf("3.traverse\n");
       printf("4.exit\n");

       printf("Enter ur choice : ");
       scanf("%d",&ch);

       switch(ch)
       {
           case 1 :   push();
                       break;
           case 2 :   pop();
                       break;
           case 3 :   traverse();
                       break;
           case 4 :   exit(1);
           default :   printf("invalid choice\n");
       }
   }
}
void push(void)
{
   struct node *temp;
   temp = (struct node *)malloc(sizeof(struct node));
   printf("Enter element to push : ");
   scanf("%d",&temp->data);
   temp->link = top;
   top = temp;
}

void pop(void)
{
   struct node *temp;
   if(top == NULL)
   {
       printf("stack is underflow\n");
       return;
   }
   temp = top;
   printf("deleted element is : %d\n",temp->data);
   top = top->link;
   temp->link = NULL;
   free(temp);
}

void traverse(void)
{
   struct node *temp;
   if(top == NULL)
   {
       printf("stack is empty\n");
       return;
   }
   temp = top;
   while(temp!=NULL)
   {
       printf("%d\n",temp->data);
       temp = temp->link;
   }
}

   Conversions and Evaluation of Expression

How to convert an expression from one notation to another?
How to evaluate Algebraic Expressions using computers?

We will be using the concepts of Stacks and Binary Trees to convert and evaluate the expressions, so the reader is required to be clear with the fundamentals of these concepts

Algebraic Expressions Introduction:

An algebraic expression is a legal combination of operands and operators.
Operand is the quantity (unit of data) on which a mathematical operation is performed.
Operand may be a variable like x, y, z or a constant like 5, 4,0,9,1 etc.
Operator is a symbol which signifies a mathematical or logical operation between the operands. Examples of familiar operators include +,-,*, / etc.
Considering these definitions of operands and operators now we can write an example of expression as x+y*z.
Note the phrase "LEGAL combination" in the definition of an Algebraic Expression.
Take another example +xyz*, in this expression operators and operands do not make any LEGAL combination. This expression is not a valid algebraic expression.
An Algebraic Expression can be represented using three different notations:

INFIX : we have been familiar with the expressions in which operators surrounded by operands.
   e.g. x+y

PREFIX : Prefix notation also Known as Polish notation, is a symbolic logic invented by Polish mathematician Jan Lukas in the 1920's. In the prefix notation as the name only suggests operator preceeded by operands.
   e.g. +xy, *+xyz etc.

POSTFIX : Postfix notation is also known as Reverse Polish notation. They are different from the infix and prefix notations in the sense that in the postfix notation, the operator followed by operands.
   e.g. xy+, xyz+* etc.

Why looking for PREFIX and POSTFIX notations when we have a sweet and simple INFIX notation?

To our surprise INFIX notations are not as simple as they seem specially while evaluating them. To evaluate an infix expression we need to consider Operators' Priority and Associativity.
For example, will expression 3+5*4 evaluate to 32 i.e. (3+5)*4 or to 23 i.e. 3+(5*4).
To solve this problem Precedence or Priority of the operators were defined.
Operator precedence governs evaluation order.
An operator with higher precedence is applied before an operator with lower precedence.
Operator Associativity governs the evaluation order of the operators of same priority.
For an operator with left-Associativity, evaluation is from left to right and for an operator with right-Associativity; evaluation is from right to left. for example *, /, +, - have left Associativity.
Due to the above mentioned problem of considering operators' Priority and Associativity while evaluating an expression using infix notation, we use prefix and postfix notations.
Both prefix and postfix notations have an advantage over infix that while evaluating an expression in prefix or postfix form we need not consider the Priority and Associativity of the operators.
E.g. x/y*z becomes */xyz in prefix and xy/z* in postfix.
Both prefix and postfix notations make Expression Evaluation a lot easier. But it is not easy to remember and manually write expressions in prefix or postfix form e.g. which one of following equations is easy to remember?
(x+y)/z*a (Infix) (or) xy+z/a* (Postfix)
So, what is actually done is that the expression is scanned from the user in infix form; it is converted into prefix or postfix form and then evaluated without considering the parenthesis and priority of the operators.

Now let us move on the programming part, How to convert an expression from one notation to another? Well there are two ways to convert expression from one notation to another. First one uses Stack and second method uses Expression trees.

As there are 3 notations namely prefix, infix and postfix , there are a total of 6 conversions that can be done ,i.e.
          infix -> prefix,
       infix -> postfix,
       prefix -> infix,
       prefix -> postfix,
       postfix -> prefix,
       postfix -> infix.

For the first 2 conversions we will be using stacks and for remaining 4 conversions we will be using Binary Expression Trees.
To convert an expression from infix to prefix and postfix, we are going to use stacks.
Those who do not know what a stack is, here are a few words about it.
A stack is a special type of data structure in which items are removed in reverse order from which they are added.
Stack follows Last in First out (LIFO) pattern.
Adding an element to a stack is called PUSH and removing an item from a stack is called POP.

Converting Expression from Infix to Postfix using STACK
   To convert an expression from infix to postfix, we are going to use a stack.

Algorithm :
1) Examine the next element in the input.
2) If it is an operand, output it.
3) If it is opening parenthesis, push it on stack.
4) If it is an operator, then
   i) If stack is empty, push operator on stack.
   ii) If the top of the stack is opening parenthesis, push operator on stack.
   iii) If the operator has higher priority than the top of stack, push operator on stack or else pop the operator from the stack and output it, repeat step 4.
5) If it is a closing parenthesis, pop operators from the stack and output them until an opening parenthesis is encountered. pop and discard the opening parenthesis.
6) If there is more input go to step 1
7) If there is no more input, unstack the remaining operators to output.

Implementation :
#include<stdio.h>
#include<string.h>
#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40
#define LPP 0
#define AP 1
#define SP AP
#define MP 2
#define DP MP
#define REMP 2
#define NONE 9
char infix[50],stack[50],postfix[50];
int top;
void infixtopostfix(void);
int gettype(char);
void push(char);
char pop(void);
int getprec(char);
int main()
{
    char ch;
    printf("*******INFIX TO PREFIX CONVERSION*******\n");
    do
    {
        top=-1;
        printf("\n\nEnter an infix expression : ");
        gets(infix);
        infixtopostfix();
        printf("infix expression = %s\n",infix);
        printf("postfix expression = %s\n",postfix);
        printf("Do you wish to continue (y/n) : ");
        ch=getche();
    }while(ch=='Y' || ch=='y');
    return 0;
}
void infixtopostfix(void)
{
    int i,p,l,type,prec;
    char next;
    i=p=0;
    l=strlen(infix);
    while(i<l)
    {
        type=gettype(infix[i]);
        switch(type)
        {
            case LP    :    push(infix[i]);
                        break;
            case RP    :
                        while((next=pop())!='(')
                        {
                              postfix[p++]=next;
                           }
                        break;
            case OPERAND    :
                        postfix[p++]=infix[i];
                            break;
               case OPERATOR    :
                        prec=getprec(infix[i]);
                        while((top>-1)&&(prec<=getprec(stack[top])))
                        {
                            postfix[p++]=pop();
                        }
                        push(infix[i]);
                        break;
        }
        i++;
    }
    while(top>-1)
    {
        postfix[p++]=pop();
    }
    postfix[p]='\0';
}
int gettype(char sym)
{
    switch(sym)
    {
        case '('    :    return(LP);
        case ')'    :    return(RP);
        case '+'    :
        case '-'    :
        case '*'    :
        case '/'    :
        case '%'    :    return(OPERATOR);
        default     :    return(OPERAND);
    }
}
void push(char sym)
{
     stack[++top]=sym;
}
char pop(void)
{
    return(stack[top--]);
}
int getprec(char sym)
{
    switch(sym)
    {
        case '('    :    return(LPP);
        case '+'    :     return(AP);
        case '-'    :    return(SP);
        case '*'    :    return(MP);
        case '/'    :    return(DP);
        case '%'    :    return(REMP);
    }
}

          Sorting Algorithms in C

Sorting in general refers to various functions which can arrange the things ordered.
In Computer Science, due to obvious reasons, Sorting (of data) is required.

Bubble Sort

Bubble Sort is the straight-forward sorting algorithm.
Bubble Sort works by comparing each element of the list with the element next to it and swapping them if required.
With each pass, the largest element of the list is "bubbled" to the end of the list.

#include<stdio.h>
void BubbleSort(int[],int);
void main()
{
    int a[50],i,n;
    printf("enter number of elements : ");
    scanf("%d",&n);
    printf("enter %d elements into array :\n",n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("before sorting:\t");
    for(i=0;i<n;i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
    BubbleSort(a,n);
    printf("after sorting:\t");
    for(i=0;i<n;i++)
    {
        printf("%d\t",a[i]);
    }
}

void BubbleSort(int a[], int n)
{
     int i, j, temp;
     for (i=0 ; i<n-1 ; ++i)
     {
          for(j=0 ; j<n-1-i ; ++j)
          {
               if (a[j]>a[j+1])
               {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
               }
          }
     }

}

                         Selection Sort

The idea of Selection Sort is rather simple.
It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where it is supposed to be.
The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list.

#include<stdio.h>
void SelectionSort(int[],int);
void main()
{
    int a[50],i,n;
    printf("enter number of elements : ");
    scanf("%d",&n);
    printf("enter %d elements into array :\n5",n);
    for(i=0 ; i<n ; i++)
    {
        scanf("%d",&a[i]);
    }
    printf("before sorting:\t");
    for(i=0 ; i<n ; i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
    SelectionSort(a,n);
    printf("after sorting:\t");
    for(i=0 ; i<n ; i++)
    {
        printf("%d\t",a[i]);
    }
}

void SelectionSort(int a[], int n)
{
     int i;
     for (i=0 ; i<n-1 ; ++i)
     {
          int j, min, temp;
          min = i;
          for (j=i+1 ; j<n ; ++j)
          {
               if (a[j] < a[min])
                    min = j;
          }

          temp = a[i];
          a[i] = a[min];
          a[min] = temp;
     }
}

                          Insertion Sort

Sorting takes place by inserting a particular element at the appropriate position, that’s why the name insertion sorting.
In the First iteration, second element, is compared with the first element.
In the second iteration third element is compared with first and second element.
In general, in every iteration an element is compared with all the elements before it.
While comparing if it is found that the element can be inserted at a suitable position, then space is created in the place of shifted element, and comparison continue with remaining elements, and the created space filled with another element when comparision completed.
This procedure is repeated for all the elements in the list.

#include<stdio.h>
void main()
{
    int a[20], n, temp, i, j;
    printf("Enter number of elements : ");
    scanf("%d", &n);
    printf("Enter %d elements in array :",n);
    for(i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    for(i=1; i<n; i++)
    {
        temp = a[i];
        j = i-1;
        while(temp<a[j] && j>=0)
        {
            a[j+1] = a[j];
            j = j-1;
        }
        a[j+1] = temp;
    }
    printf("Sorted elements are :\n");
    for(i=0; i<n; i++)
        printf("%d\t", a[i]);
}


                               Heap Sort

Heap sort algorithm is a comparison-based sorting algorithm.
The heap sort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array.
After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the sorted array.
This is repeated until there are no items left in the heap and the sorted array is full.
Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.

Heap sort uses two heap operations :

Insertion
Root deletion.

#include<stdio.h>
void HeapTree(int[],int);
void DeleteMax(int[],int,int);
void main()
{
        int a[20],n,i,j,k;
        printf("Enter the Number of elements : ");
        scanf("%d",&n);
        printf("Enter the elements : ");
        for(i=1;i<=n;i++)
       {
                scanf("%d",&a[i]);
                HeapTree(a,i);
        }
        j=n;
        for(i=1;i<=j;i++)
        {
                int temp;
                temp=a[1];
                a[1]=a[n];
                a[n]=temp;
                n--;
                DeleteMax(a,1,n);
        }
        n=j;
        printf("Here the elements....\n");
        for(i=1;i<=n;i++)
                printf("%d\t",a[i]);
                printf("\n");
}
void HeapTree(int a[],int i)
{
        int v=a[i];
        while((i>1)&&(a[i/2]<v))
        {
                a[i]=a[i/2];
                i=i/2;
        }
        a[i]=v;
}
void DeleteMax(int a[],int i,int n)
{
        int v=a[i];
        int j=i*2;
        while(j<=n)
        {
                if((j<n)&&(a[j]<a[j+1]))
                        j++;
                if(a[j]<a[j/2])
                       break;

                a[j/2]=a[j];
                j=j*2;
        }
        a[j/2]=v;
}

                            Quick Sort

The basic concept is to pick one of the elements in the array as a pivot value around which the other elements will be rearranged.
Everything less than the pivot is moved left of the pivot (into the left partition).
Similarly, everything greater than the pivot goes into the right partition.
At this point each partition is recursively quick sorted.
The Quick sort algorithm is fastest when the median of the array is chosen as the pivot value.
That is because the resulting partitions are of very similar size.
Each partition splits itself in two and thus the base case is reached very quickly.

#include<stdio.h>
void read(int[],int);
void print(int[],int);
void main()
{
    int a[50],n;
    printf("Enter number of elements : ");
    scanf("%d",&n);

    printf("Enter %d elments :\n",n);
    read(a,n);

    printf("\nBefore sort :\t");
    print(a,n);

    Qsort(a,0,n);

    printf("\nAfter sort :\t");
    print(a,n);
}

void read(int a[],int n)
{
    int i;
    for(i=0 ; i<n ; i++)
    {
        scanf("%d",&a[i]);
    }
}

void print(int a[],int n)
{
    int i;
    for(i=0 ; i<n ; i++)
    {
        printf("%d\t",a[i]);
    }
}

int Qsort(int data[], int left, int right)
{
    int mid,tmp,i,j;
    i = left;
    j = right;
    mid = data[(left+right)/2];
    do
    {
        while(data[i]<mid)
            i++;
        while(mid<data[j])
            j--;
        if (i <= j)
        {
            tmp = data[i];
            data[i] = data[j];
            data[j] = tmp;
            i++;
            j--;
        }
    }while(i<=j);
    if (left < j)
        Qsort(data,left,j);
    if (i < right)
        Qsort(data,i,right);
}

                         Merge Sort

The sorting algorithm Merge sort produces a sorted sequence by sorting its two halves and merging them.
The Merge sort algorithm is based on a divide and conquer strategy .
First, the sequence to be sorted is decomposed into two halves (Divide).
Each half is sorted independently (Conquer).
Finally two sorted halves are merged to a sorted sequence (Combine)

#include<stdio.h>
void read(int[],int);
void print(int[],int);
void sort(int[],int,int,int);
void partition(int[],int,int);
void main()
{
    int a[50],n;
    printf("Enter number of elements : ");
    scanf("%d",&n);

    printf("Enter %d elments :\n",n);
    read(a,n);

    printf("\nBefore sort :\t");
    print(a,n);

    partition(a,0,n-1);

    printf("\nAfter sort :\t");
    print(a,n);
}

void read(int a[],int n)
{
    int i;
    for(i=0 ; i<n ; i++)
    {
        scanf("%d",&a[i]);
    }
}

void print(int a[],int n)
{
    int i;
    for(i=0 ; i<n ; i++)
    {
        printf("%d\t",a[i]);
    }
}

void sort(int arr[],int low,int mid,int high)
{
     int i,j,k,l,b[20];
     l=low;
     i=low;
     j=mid+1;
     while((l<=mid)&&(j<=high))
       {
        if(arr[l]<=arr[j])
          {
               b[i]=arr[l];
               l++;
          }
        else
          {
               b[i]=arr[j];
               j++;
          }
        i++;
       }
     if(l>mid)
       {
        for(k=j;k<=high;k++)
           {
            b[i]=arr[k];
            i++;
       }
   }
     else
       {
        for(k=l;k<=mid;k++)
           {
            b[i]=arr[k];
                i++;
           }
       }
     for(k=low;k<=high;k++)
    {
         arr[k]=b[k];
    }
}

void partition(int arr[],int low,int high)
{
     int mid;
     if(low<high)
       {
        mid=(low+high)/2;
        partition(arr,low,mid);
        partition(arr,mid+1,high);
        sort(arr,low,mid,high);
       }
}

c2java

Pages

Data Structures

No comments:

Post a Comment