Merge sort Algorithm and Program in C C++

The merge sort is a sorting algorithm that uses the divide and conquer strategy . in this method ,division is dynamically carried out .
Merge sort on an input array with n elements consists of three steps.
1) Divide : Partition array into two sublists s1 and s2 with n/2 elements each .
2) Conquer : Recursively sort s1 and s2 .
3) Combine : Merge s1 and s2 into a unique sorted group .
               The merge sort divides the given list into two sublists recursively until each sublist contains only one element .Then we apply the same merging process recursively as explained above to obtain the sorted list . If the single file or list contains N elements then it is divided into two sublists containing N/2 elements which are further divided into sublists containing N/4 elements and so on.
Also check : Program for Insertion sort 

Algorithm for Merge sort :

Mergingsortedsubarrays(a , lb , lr , rb , rr)
        Here a is a linear array , variables lb ,lr represents beginning and ending indices of the left sub array and variables rb ,rr represents beginning and ending indices of the right sub array .The algorithm merges these two sub arrays .It uses local variables na ,nb as counters to keep track of the elements of left and right sub array respectively which are candidates to go to temporary array c and nc as counter to keep track of the position in c , where the incoming elements will be stored .

Begin
    set na=lb, nb=rb and nc=lb
    while((na<=lr) and (nb<=rr)) do
        if(a[na]<b[nb]) then
            Set c[nc]=a[na]
            set na=na+1
        else
            set c[nc]=a[nb];
            set nb=nb+1;
        endif
            setnc=nc+1
    endwhile
    if(na>lr) then
        while(nb<=rr)then
        set c[nc]=b[nb];
        set nb=nb+1;
        set nc=nc+1;
        endwhile
    else
        while(na<=lr) then
            set c[nc]=b[na];
            set na=na+1;
            set nc=nc+1;
        endwhile
    endif
    for k=lb to rr by 1 do
        set a[k]=c[k]
    endfor
End

After the procedure for merging to halves is defined the various steps required for mergesort are summarized in the following algorithm ,

Algorithm : Mergesort(a , beg , end)

      Here a is a linear array with lower bound beg and upper bound end .The algorithm sorts the array using merge sort method .It uses variable mid to represent the index of the element at which array will be divided into two halves .

Begin
    if(beg<end) then
        set mid = (beg+end)/2;
        call mergesort(a,beg,mid);
        call mergesort(a,mid+1,end);
        call mergingsortedsubarray(a,beg,mid,mid+1,end)
    endif
End

Quicksort Program in C & C++ and Algorithm

Quicksort is a sorting algorithm that uses the divide and conquer strategy . In this method division is dynamically carried out . The Three steps of quicksort are as follows .
1) Divide :Rearrange the elements and split the array into two sub arrays and an element in between .Each element in the left sub array is less than or equal to the middle element and each element in the right sub array is greater than the middle element .
2) Conquer : Recursively sort the two sub arrays .
3) Combine : Combine all the sorted elements in a group to form a list if sorted elements .
Quicksort is a sorting algorithm that also,like merge sort .This algorithm finds the element called pivot , that partitions the array into two halves in such a way that the elements in the left sub array are less then and the elements in the right subarrays are sorted separately .This procedure is recursive in nature with the base criteria,the number of elements in the array are not more than 1. 
         The main task in quick sort is to find the element that partitions the array into two halves and to place it at its proper location in the array .Usually the procedure places the first element in the array at its appropriate location .

Also check : Depth First search Algorithm

         This task is performed as stated below ,
To begin with ,set the index of the first element of the array to 'loc' and 'left' variables and index of the last element of the array to right variable .
Then proceed as follows ,

• Beginning with the element pointed to by right ,the array is scanned from right to left ,comparing each element on the way with the element pointed to by loc , till either ,
• 1) Element smaller than the element pointed to by loc is found .In this case the elements are interchanged and procedure continues with step 2.
• 2) If the value if the right variable becomes equal to the value of loc, the procedure terminates here.This condition indicates that the element is placed at as appropriate position loc .
• Beginning with the element pointed to by left ,the array is scanned from left to right comparing each element on the way with the element pointed to by loc ,till either
• 1) Elements greater than the element pointed to by loc is found .In this case ,the elements are interchanged and procedure continues with step 1.
• 2) If the value of the left variable becomes equal to the value of loc , the procedure terminates here .This condition indicates that the element is placed in its final position loc .

As this procedure terminates ,the first element ,pivot ,of original array will be placed at loc,its appropriate location in the sorted array.The elements to left of it will be less than this element and elements to its right will be greater than this element .

Insertion sort Algorithm and Insertion Sort Program in C++

Insertion Sort :

Insertion sort algorithm is very popular with bridge players when they first sort their cards . In this procedure , we pick up a particular value and then insert it at the appropriate place in the sorted sub list , i.e during kth iteration the element a[k] is inserted in its proper place in the sorted sub array a[1] , a[2] , a[3].....a[k-1] . This task is accomplished by comparing a[k] with a[k-1] , a[k-2] , a[k-3] and so on until the first element a[j] such that a[j]<=a[k] is found . Then each of the elements a[k-1] , a[k-2] , .....,a[j+1] are moved one position up , and then element a[k] is inserted in (j+1)st position in the array .
        For more clarity , carefully examine the following steps,
Pass 1:a[1] is inserted either before or after a[0] so that a[0] and a[1] are sorted .
Pass 2:a[2] is inserted either before a[0] or between a[0] and a[1] or after a[1] so that the elements a[0] , a[1] , a[2] are sorted .
Pass 3:a[3] is inserted either before a[0] or between a[0] and a[1] or between a[1] and a[2] or after a[2] so that the elements a[0],a[1],a[2],a[3] are sorted .
.
.
.
Pass n-1:a[n-1] is inserted in proper place in the sorted subarray a[0],a[1],a[2],....,a[n-2] so that after insertion , the elements a[0],a[2],.....,a[n-1] are sorted .
Thus after (n-1) passes , the array will be sorted in ascending order . The various steps required to implement insertion sort are summarized in the algorithm given below ,

Also check : Algorithm for Depth First Search 

Algorithm for Insertion sort :

Insertionsort( a , n ) 

Begin
    for k=1 to (n-1) by 1 do
        Set temp=a[k]
        Set j=k-1
        while((temp<a and (j>=0)) do
            Set a[j+1]=a[j]
                Set j=j-1
        endwhile
            Set a[j+1]=temp
    endfor
End

          Here a is a linear array with n elements in memory . This algorithm sorts the elements in the ascending order . It uses a temporary variable temp to facilitate the exchange of two values and variable j and k are used as loop control and index variables .
The above algorithm moves the elements up by one position till the correct slot for the element is found and then inserts the element at that slot .

Also check : Algorithm and Program for Heap Sort

Example for Insertion Sort :

To Illustrate the working of the insertion sort method ,consider the following array a with 7 elements as 
35 , 20 , 40 , 100 , 3 , 10 , 15
Given array a ,

Pass 1

Pass 2 : Since a[1]<a[0], insert element a[1] before a[0] , giving the following array ,

Algorithm and Program for Depth First Search in C

Depth First Search is one of the standard ways to traverse a graph . Depth First Search traversal is used by most of the Graph algorithms .

Depth First Search :

The Depth First Search ( DFS ) , as its name implies , is to search deeper in the graph , whenever possible . The edgesare explored out of the most recently discovered vertex v that still has unexplored edges leaving it . When all of V's edges have been explored , the search backtracks to explore edges leaving the vertex from which v was discovered . This process continues until we have disocvered all the vertices that are reachable from the source vertex . This algorithm also works on both directed as well as on undirected graphs .
     To keep track of the progress , the DFS also uses the same coloring scheme as described for BFS . In addition the DFS makes uses of a stack structure to maintain the order in which the vertices are to be processed , instead of queue
The below algorithm summarizes various steps required to implement the DFS

Depth First Search Iterative (adj,n,s): 

Here adj is the adjacency list of the graph with n vertices , and vertex s is the source vertex . This algorithm uses a stack STACK , and linear array color of size n , to keep track of the progress of DFS . Its also uses local variables u and ptr .

Also check : Threaded Binary Tree Structures

Depth First Search (DFS) Algorithm :

 BEGIN
    for i=1 to n by 1 do
        set color[i]=WHITE
    endfor
    Set color[s]=GRAY
    CALL createstack(stack)
    Call push(stack,s)
    while(Stack is not empty) do
        Set u=peek(stack)
        Set ptr=adj[u]
        while(ptr!=NULL) do
            if(color[prt->info]=WHITE) then
                Set color[ptr->info]=GRAY
                Call push(&stack,ptr->info)
                Set u=ptr->info
                Set ptr=adj[u]
            else
                Set ptr=ptr->next
            endif
        endwhile
        Call pop(&stack,u)
        Print :u
        Set color[u]=BLACK
    endwhile
End

 

Threaded Binary Trees Structure,Types and Inorder Traversal

Threads :

In my previous post I discussed about preorder , postorder and inorder binary tree traversals used stacks and level order traversals used queues as an auxiliary data structure . I highly recommend to know the basic binary tree traversals from the last post . 
In this article I will discuss new traversal algorithms which do not need both stacks and queues and such traversal algorithms and called Threaded Binary Tree Traversals or stack/queue less traversals .

Issues with regular Binary Tree Traversals :

• The storage space required for stack and queue is large .
• The majority of pointers in any binary tree are NULL . For example a binary tree with n nodes has n+1 NULL pointers and these were wasted .
• It is difficult to find successor node ( preorder ,inorder and postorder successors ) for a given node  .

Motivation for Threaded Binary Trees :

To solve these problems , one idea is to store some useful information in NULL pointers . If we observe previous traversals carefully , stack/queue is required because we have to record the current position in order to move to right subtree after processing the left subtree . If we store the useful information in NULL pointers  then we don't have to store such information in stack / queue. The binary trees which store such information in NULL pointers are called Threaded Binary Trees .
The next question is what to store ?
The common convention is pust predecessor/successor information . That means , of we are dealing with preorder traversals then for a given node . NULL left pointer will contain preorder predecessor information and NULL right pointer will contain preorder successor information . These special Pointers are called Threads .

Classifying Threaded Binary Trees :

The classification is based on whether we are storing useful information in both NULL pointers or only on one of them ,

1. If we store predecessor information in NULL left pointers only then we call such binary trees as Left Threaded binary trees .
2. If we store successor information in NULL right pointers only then we call such binary trees as right threaded binary trees .
3. If we store predecessor information in NULL left pointers only then we call such binary trees as Fully threaded binary trees or simply threaded binary trees . 

Binary Tree Traversal and Tree Iterations | Data Structures

Tree Traversal :

In order to process trees , we need  a mechanism for traversing them and that forms the subject of this post . The process of visiting all the nodes of a tree is called Tree Traversal . Each of the nodes is processed only once but they may be visited more than once . As I had already discussed linear data structures ( like linked list , stacks , queues ,etc ) the elements are visited sequential order . But in three structures there are many different ways .
Tree traversal is like searching the tree except that in traversal the goal is to move through the tree in some particular order . In addition , all nodes are processed in the traversal but searching stops when the required node is found .
 
Also check : Program for Merging two Linkedlist in C++

Traversal Posssibilities :

Starting at the root binary tree there are three main steps that can be performed and the order in which they are performed defines the traversal type .These steps are performing an action on the current node , traversing to the left child node and traversing to the right child node . This process can be easily described through recursion. 

Classifying the Traversals :

The sequence in which these entities processed defines a particular traversal method . There are 3 Traversal methods :
1. Preorder Traversal 
2. Inorder Traversal
3. Post order Traversal 

Inorder Traversal :

In Inorder traversal the root is visited between the subtrees . Inorder traversal is defined as follows ,
1. Traverse the Left subtree in Inorder .
2. Visit the root.
3. Traverse the right subtree Inorder .

Time complexity : O(n)
Space complexity : O(n)
Example :
Inorder traversal : C B D A F E I H G 

Program:

void inorder(stuct binarytreenode *root)
{
    inorder(root->left);
    printf("%d",root->data);
    inorder(root->right);
}

Preorder Traversal :

In preorder traversal , each node is processed before ( pre) either of its sub trees . This is the simplest traversal to understand . However , even though each node is processes before the subtrees , it still requires that some information must be maintained while moving down the tree . In the example above , the 1 is processed first , then the left sub tree followed by the right subtree .Therefore , processing must return to the right sub tree after finishing the processing left sub tree we must maintain root information . The obvious ADT for such information is a stack .Because of its "Last in First Out " Structure it is possible to get the information about the right subtrees back in the reverse order .
Preorder traversal is defined as follows ,
1. Visit the root
2. Traverse to the left subtree in preorder
3. Traverse the right subtree in preorder

Time complexity :O(n)
Space complexity : O(n)
Program :

void preorder(struct binarytreenode *root)
{
    if(root)
    {
        printf("%d",root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

Program for Concatenating or Merging of Two Linked List in C++

Combining two sorted Linked List or two sorted Double Linked List into a one list . The condition required for the resultant list is it must also be in the sorted list . Here we will consider two sorted single Linked List and the same procedure can be extended to two double Linked List also. Here we are providing only the merge routine programme by assuming that two sorted Linked List . First and Second are already developed and the result will be stored in the third List .In this post I will be Discussing the program for Merging or concatenating two Linked List .

Also Check : Concept of Binary Tree

Binary Tree Concept and Abstract Data Type of Binary Tree

A binary tree is a finit set of nodes which is either empty or consisits of a root and two disjoint trees called left subtree and right subtree .
In Binary tree each node will have one data field and two pointer fields for reperesenting the sub-branches . The degree of each node on the binary tree will be at the most two .

Abstract Data Type of Binary tree 

ADT Binary Tree

Operations :

    buildBtree() : Creates a binary tree

    leftchild(t) : Returns the Left child of t

    rightchild(t): Returns the right child of t.

    empty()      : Returns true if the tree is empty false otherwise

    size()       : Returns the number of nodes in the tree

    preorder()   : Displays the binary tree in preorder

    inorder()    : Displays the binary tree in inorder

    postorder()  : Displays the binary tree in postorder

    levelorder() : Displays the binary tree in level order

Properties if Binary Trees

Property 1

A Binary Tree with n elements , has exactly n-1 edges where n>0
Proof :
Every node in a binary tree , except the root node , has exactly one parent . There will be exactly one edge between each child and its parent . So the number of edges of binary tree with n nodes is n-1 .

Property 2

A binary tree of height h , h>0 has minimum of h and maximum of 2^h -1 elements in it .

Property 3

If a binary tree has n nodes we can construct binary tree with maximum height of n and with minimum height of log(n+1) .

Array Representation of binary tree :

When the elements of a binary tree are represented in the form of an array , the representation is known as an formula based repesentation . The elements are represented or stored at the array locations relative to the numbers assigned to them.
          In the array approach the nodes are stored in an array and are not linked by references . The position of the node in the array corresponds to its position in the tree .The node at index 0 is the root the node at index 1 is the roots left child the node at index 2 is the roots right child and so on progressing from left to right along each level of the tree .

Program for Queue using Linked List in C++ and Implementation

Queue is an Abstract data type which follows "First In First Out" Principle . Queue is an ordered collection of homogeneous data elements like stack . It is a linear data Structure in which insertion , deletion operations takes place at two ends called REAR (R) and FRONT (F) of the queue . 
Elements are inserted at the rear end and elements are deleted at the front end of a queue . The first element entered into the queue is the first element that is removed from the queue .

Why To Implement Queues using Linked List ?

In one of my previous tutorial , I discussed about Program for Queues using arrays , where the size of the array need to be fixed to store the elements in the queue . But in Linked list We need not worry about size of the Queue . Size of the queue is under the supervision of the user . So Implementing Queues using Linked list will have more advantage than that of using arrays . 
In this program Linked list data structure is used . If you don't have any idea about Linked List I suggest to have a read of Excellent Linked list Data Structure .

Program for Doubly Linked Lists in C++ and Algorithm

A doubly Linked list is a special type of linked list where the nodes contain three fields i.e one data field and two link fields . The data Field contains the data element and the two link fields contains two pointers i.e prev and next . The pointer prev points to the previous node or points to a NULL value if it is the first node in the list . The pointer next points to the next node or points to a NULL value of it is the last node in the list .

Advantages of Doubly Linked List :

1. The Main advantage of using double linked list is that , the list can be traversed in forward as well as backward direction . 
2. Linked List can be easily reversed when compared to Single Linked List .
3. We can traverse to any node in a Doubly linked list But in Single Linkedlist previous node cannot be reached .

Also check : Program for Queue in C++

Disadvantages of Doubly Linked List :

1. It takes more space in Doubly Linked List than in Single Linked list because of an extra pointer .