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

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

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

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

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

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

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

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

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

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