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 . 

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 .

Program for Polynomial Addition Using Linkedlist in C++

Polynomial addition is one of the application of the Linkedlist data Structure . Polynomial addition can be implemented with arrays as well . A computer cannot understand the polynomial and how to add two polynomials . The main variables to be declared for polynomial addition are :
1. Cofficient
2. power
3. address of the next term

Thus the required memory declaration for representation of a polynomial with integer coefficients are :

 class node
{
public :
    int coeff;
    int power;
    node *next;
};
class polynomial
{
private :
    node *head;
public :
    polynomial()
    {
        head=NULL;
    }
    ~polynomial();
    void read();
    void display();
};

with these declarations we can write a program for polynomial addition using Linkedlist in C++

Program for Heap Sort in C++ with Heap sort Algorithm

Heap Trees are binary trees as well as complete Binary Trees . Sorting is a major application of heap trees . Similar to other data Structures Insertion , Deletion and Display operations can be performed in Heap trees . The Timing complexity of Heap tree for insertion , deletion operations is O(logn) . There are 2 types of heap trees :

1. Max Heap Tree

2. Min Heap Tree

Max Heap :

According to Max heap Child nodes should have a value less when compared to parent node element . Simply parent element should have large value than its children . Root node contains the maximum value from the entire tree .

Min Heap :

According to Min Heap child node should contains value more than the parent values . The leaf node contains Max value in the entire tree and root node element has the minimum value from the Heap Tree .

image credits : wikipedia.org

Applications of Heap Tree :

1. Priority Queues which are widely used in the CPU scheduling algorithms in operating systems are generally implemented using Max heaps .

2. Heap sort one of the best sorting techniques is implemented using either Max heap or Min heap trees .

In this tutorial I will be using Max Tree to implement all the operations such as Insertion , Deletion , Sorting . Of course these operations can be implemented using Min heap trees as well .

Also check : Program for Linked list in c++

Program for Single Linked List Data Structure in C++ and Algorithm

Linked list is linear data structure which contains a group of nodes and are sequentially arranged . Nodes are composed of data and address of the next node or reference of the next node . These nodes are sequentially or Linearly array that is why the Linked list is a Linear data structure . In Linked List we start with a node and create nodes and link to starting node in order and sequentially . Also the address Pointer field of the Last node must be assigned to NULL . There are single Linked List , Double Linked list , circular Linked list and so on . In this Post I will be discussing about Single Linked List .
Inserting an element and deleting an element into linkedlist takes O(1) order of 1 unit of time . Elements can be inserted any where in the linkedlist and any node can be deleted . Similar to Stacks and Queue's Insertion and deletion are the operations performed to insert an element and to delete an element from the linked list .

Also check : Program for Stack Data Structurein C++

Program for Queue Data Structure in c++ | Queue Implementation

Queue is an abstract data type and a common data structure similar to stack . Queue is an ordered list in which insertions (Push) , deletion (Pop) operations are done at different ends . The end at which insertion is performed is known as rear end . The end at which deletion (Pop) operation is performed is known as front end .
Queue follows "First in First Out Principle" which implies that the element which is inserted first is deleted first from the queue . Queue can be implemented using arrays and linkedlists . 
for example : Let 1,2,3,4,5 be the five elements inserted and the first element inserted is 1 and next element to be inserted is 2 and soon . To delete an element from the Queue , the first element to be deleted is 1 which follows First In First Out principle .

image credits : wikipedia.org

 Also check : Implementation of Stacks using c++

Program and Implementation of Stack Data Structure in C++ Using Arrays

Stack is an Abstract Data Type and common Data Structure . Stack is an ordered list which is used in performing the the operations such as Insertion (Push) , Deletion (Pop) , Top can be performed easily.
Stack refers to "Last In First Out" Principle (LIFO)

Applications of Stack :

As there are many applications in the field of computer science . Here I will list few major applications of the stack .

1. Stack Data structures is mainly used in Evaluating the Expressions and Syntax parsing .     
2. Stack Data Type is used in conversion of Decimal number to Binary number.
3. Stack is used in the application of the Quick Sort to sort a given array or List . Quick sort is one of the efficient sorting techniques which is based on Divide and conquer algorithm .
4. BackTracking is other major applications of stack . In the maze problems backtracking helps to trace the previous path and each path is stored in the form of stack data structure .

Image credits:my.opera.com

Program for Binary Search in C++ and its Algorithm Efficiency

Binary search Algorithm is one of the most efficient algorithm after Linear search algorithm for Searching an element . Binary search Algorithm mainly involves dividing the list into two halves with their index values and finding the key value of middle element . In each step of the algorithm the middle key value is compared with the search key value . Then there arises 3 situations .

1. If search key value is equal to middle element key value : In this case Search element is found and the process is stopped . The algorithm returns the index where search key is found .
2. If search key value is less than the middle element key value : In this case you need to perform the search towards the Left of the middle element key value .

3. If search key value is greater than the middle element key value : In this case the search need to be performed towards the Right of the middle element key value .
In this Tutorial I will be discussing about Program for Binary Search in C++ and also it Efficiency when compared to linear search algorithm .

Output for below code:

Complete Binary Tree Implementation and Program in C++

In my Last post I discussed about Algorithm for searching an element or node in Binary Search Tree . Binary Tree is a non-linear Data Structure which helps in traversing and improving timing complexity when compared to other Data Structures .
In this post I will discuss about Implementation of Complete Binary Tree and Program for Complete Binary tree in C++ .

Also check : Program for Linear search in C++

Algorithm for Searching a Node in Binary Search Tree

Binary Search Tree is a Binary Tree which satisfy following rules 

• Left child or node has a value or data less than the root node value .
• Right child has a value grater then root node value or data .

The following Binary Search tree which satisfies above two rules . Let the data entered be 8 , 3 , 10 ,1 , 6 , 14 , 4 ,7 , 13  .

Root node data is 8 . All the nodes in the left sub tree of the root have a value less than 8 . Similarly all the nodes in the right of the sub tree of the root node have values greater than 8 . The same holds for all other subtrees as well .

Also check : Program for Linear search in C++