Category: data Structures Algorithms

Data Structures and Types ”; Previous Next Data structures are introduced in order to store, organize and manipulate data in programming languages. They are designed in a way that makes accessing and processing of the data a little easier and simpler. These data structures are not confined to one particular programming language; they are just pieces of code that structure data in the memory. Data types are often confused as a type of data structures, but it is not precisely correct even though they are referred to as Abstract Data Types. Data types represent the nature of the data while data structures are just a collection of similar or different data types in one. There are usually just two types of data structures − Linear Non-Linear Linear Data Structures The data is stored in linear data structures sequentially. These are rudimentary structures since the elements are stored one after the other without applying any mathematical operations. Linear data structures are usually easy to implement but since the memory allocation might become complicated, time and space complexities increase. Few examples of linear data structures include − Arrays Linked Lists Stacks Queues Based on the data storage methods, these linear data structures are divided into two sub-types. They are − static and dynamic data structures. Static Linear Data Structures In Static Linear Data Structures, the memory allocation is not scalable. Once the entire memory is used, no more space can be retrieved to store more data. Hence, the memory is required to be reserved based on the size of the program. This will also act as a drawback since reserving more memory than required can cause a wastage of memory blocks. The best example for static linear data structures is an array. Dynamic Linear Data Structures In Dynamic linear data structures, the memory allocation can be done dynamically when required. These data structures are efficient considering the space complexity of the program. Few examples of dynamic linear data structures include: linked lists, stacks and queues. Non-Linear Data Structures Non-Linear data structures store the data in the form of a hierarchy. Therefore, in contrast to the linear data structures, the data can be found in multiple levels and are difficult to traverse through. However, they are designed to overcome the issues and limitations of linear data structures. For instance, the main disadvantage of linear data structures is the memory allocation. Since the data is allocated sequentially in linear data structures, each element in these data structures uses one whole memory block. However, if the data uses less memory than the assigned block can hold, the extra memory space in the block is wasted. Therefore, non-linear data structures are introduced. They decrease the space complexity and use the memory optimally. Few types of non-linear data structures are − Graphs Trees Tries Maps Print Page Previous Next Advertisements ”;

Data Structures & Algorithms – Overview ”; Previous Next What is Data Structure? Data Structure is a systematic way to organize data in order to use it efficiently. Following terms are the foundation terms of a data structure. Interface − Each data structure has an interface. Interface represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations. Implementation − Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure. Types of Data Structures Here are different type of data structures which we are going to learn in this tutorial: Array Data Structure String Data Structure Linked List Data Structure Double Linked List Data Structure Circular Linked List Data Structure Stack Data Structure Queue Data Structure Heap Data Structure Hash Data Structure Matrix/Grid Data Structure Graph Data Structure Tree Data Structure What is Algorithm? Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. Types of Algorithms Here are different type of algorithms which we are going to learn in this tutorial: DSA – Searching Algorithms DSA – Sorting Algorithms DSA – Approximation Algorithms DSA – Divide and Conquer Algorithms DSA – Greedy Algorithms DSA – Recursion Algorithm DSA – Backtracking Algorithm DSA – Randomized Algorithms DSA – Dynamic Programming DSA – Pattern Searching DSA – Mathematical Algorithms DSA – Geometric Algorithms DSA – Bitwise Algorithms DSA – Branch and Bound Algorithm Characteristics of a Data Structure Correctness − Data structure implementation should implement its interface correctly. Time Complexity − Running time or the execution time of operations of data structure must be as small as possible. Space Complexity − Memory usage of a data structure operation should be as little as possible. Execution Time Cases There are three cases which are usually used to compare various data structure”s execution time in a relative manner. Worst Case − This is the scenario where a particular data structure operation takes maximum time it can take. If an operation”s worst case time is ƒ(n) then this operation will not take more than ƒ(n) time where ƒ(n) represents function of n. Average Case − This is the scenario depicting the average execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then m operations will take mƒ(n) time. Best Case − This is the scenario depicting the least possible execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n). Basic DSA Terminologies Data − Data are values or set of values. Data Item − Data item refers to single unit of values. Group Items − Data items that are divided into sub items are called as Group Items. Elementary Items − Data items that cannot be divided are called as Elementary Items. Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned values. Entity Set − Entities of similar attributes form an entity set. Field − Field is a single elementary unit of information representing an attribute of an entity. Record − Record is a collection of field values of a given entity. File − File is a collection of records of the entities in a given entity set. Print Page Previous Next Advertisements ”;

Tree Data Structure Table of content Tree Data Structrue Important Terms Types of Trees General Trees Binary Trees Binary Search Trees ”; Previous Next Tree Data Structrue A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of nodes (where the data is stored) that are connected via links. The tree data structure stems from a single node called a root node and has subtrees connected to the root. Important Terms Following are the important terms with respect to tree. Path − Path refers to the sequence of nodes along the edges of a tree. Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node. Parent − Any node except the root node has one edge upward to a node called parent. Child − The node below a given node connected by its edge downward is called its child node. Leaf − The node which does not have any child node is called the leaf node. Subtree − Subtree represents the descendants of a node. Visiting − Visiting refers to checking the value of a node when control is on the node. Traversing − Traversing means passing through nodes in a specific order. Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on. Keys − Key represents a value of a node based on which a search operation is to be carried out for a node. Types of Trees There are three types of trees − General Trees Binary Trees Binary Search Trees General Trees General trees are unordered tree data structures where the root node has minimum 0 or maximum ‘n’ subtrees. The General trees have no constraint placed on their hierarchy. The root node thus acts like the superset of all the other subtrees. Binary Trees Binary Trees are general trees in which the root node can only hold up to maximum 2 subtrees: left subtree and right subtree. Based on the number of children, binary trees are divided into three types. Full Binary Tree A full binary tree is a binary tree type where every node has either 0 or 2 child nodes. Complete Binary Tree A complete binary tree is a binary tree type where all the leaf nodes must be on the same level. However, root and internal nodes in a complete binary tree can either have 0, 1 or 2 child nodes. Perfect Binary Tree A perfect binary tree is a binary tree type where all the leaf nodes are on the same level and every node except leaf nodes have 2 children. Binary Search Trees Binary Search Trees possess all the properties of Binary Trees including some extra properties of their own, based on some constraints, making them more efficient than binary trees. The data in the Binary Search Trees (BST) is always stored in such a way that the values in the left subtree are always less than the values in the root node and the values in the right subtree are always greater than the values in the root node, i.e. left subtree < root node ≤ right subtree. Advantages of BST Binary Search Trees are more efficient than Binary Trees since time complexity for performing various operations reduces. Since the order of keys is based on just the parent node, searching operation becomes simpler. The alignment of BST also favors Range Queries, which are executed to find values existing between two keys. This helps in the Database Management System. Disadvantages of BST The main disadvantage of Binary Search Trees is that if all elements in nodes are either greater than or lesser than the root node, the tree becomes skewed. Simply put, the tree becomes slanted to one side completely. This skewness will make the tree a linked list rather than a BST, since the worst case time complexity for searching operation becomes O(n). To overcome this issue of skewness in the Binary Search Trees, the concept of Balanced Binary Search Trees was introduced. Balanced Binary Search Trees Consider a Binary Search Tree with ‘m’ as the height of the left subtree and ‘n’ as the height of the right subtree. If the value of (m-n) is equal to 0,1 or -1, the tree is said to be a Balanced Binary Search Tree. The trees are designed in a way that they self-balance once the height difference exceeds 1. Binary Search Trees use rotations as self-balancing algorithms. There are four different types of rotations: Left Left, Right Right, Left Right, Right Left. There are various types of self-balancing binary search trees − AVL Trees Red Black Trees B Trees B+ Trees Splay Trees Priority Search Trees Print Page Previous Next Advertisements ”;

Data Structures – Algorithms Basics Table of content Characteristics of an Algorithm How to Write an Algorithm? Algorithm Analysis Algorithm Complexity Space Complexity Time Complexity ”; Previous Next Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. From the data structure point of view, following are some important categories of algorithms − Search − Algorithm to search an item in a data structure. Sort − Algorithm to sort items in a certain order. Insert − Algorithm to insert item in a data structure. Update − Algorithm to update an existing item in a data structure. Delete − Algorithm to delete an existing item from a data structure. Characteristics of an Algorithm Not all procedures can be called an algorithm. An algorithm should have the following characteristics − Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. Input − An algorithm should have 0 or more well-defined inputs. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output. Finiteness − Algorithms must terminate after a finite number of steps. Feasibility − Should be feasible with the available resources. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code. How to Write an Algorithm? There are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code. As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm. We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution. Example Let”s try to learn algorithm-writing by using an example. Problem − Design an algorithm to add two numbers and display the result. Step 1 − START Step 2 − declare three integers a, b & c Step 3 − define values of a & b Step 4 − add values of a & b Step 5 − store output of step 4 to c Step 6 − print c Step 7 − STOP Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be written as − Step 1 − START ADD Step 2 − get values of a & b Step 3 − c ← a &plus; b Step 4 − display c Step 5 − STOP In design and analysis of algorithms, usually the second method is used to describe an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can observe what operations are being used and how the process is flowing. Writing step numbers, is optional. We design an algorithm to get a solution of a given problem. A problem can be solved in more than one ways. Hence, many solution algorithms can be derived for a given problem. The next step is to analyze those proposed solution algorithms and implement the best suitable solution. Algorithm Analysis Efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following − A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation. A Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected. We shall learn about a priori algorithm analysis. Algorithm analysis deals with the execution or running time of various operations involved. The running time of an operation can be defined as the number of computer instructions executed per operation. Algorithm Complexity Suppose X is an algorithm and n is the size of input data, the time and space used by the algorithm X are the two main factors, which decide the efficiency of X. Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting algorithm. Space Factor − Space is measured by counting the maximum memory space required by the algorithm. The complexity of an algorithm f(n) gives the running time and/or the storage space required by the algorithm in terms of n as the size of input data. Space Complexity Space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following two components − A fixed part that is a space required to store certain data and variables, that are independent of the size of the problem. For example, simple variables and constants used, program size, etc. A variable part is a space required by variables, whose size depends on the size of the problem. For example, dynamic memory allocation, recursion stack space, etc. Space complexity S(P) of any algorithm P is S(P) = C &plus; SP(I), where C is the fixed part and S(I) is the variable part of the algorithm, which depends on instance characteristic I. Following is a simple example that tries to explain the concept − Algorithm: SUM(A, B) Step 1 − START Step 2 − C ← A &plus; B &plus; 10 Step 3 − Stop Here we have three variables A, B, and C and one constant. Hence S(P) = 1 &plus;

Tree Traversal Table of content In-order Traversal Pre-order Traversal Post-order Traversal Complete Implementation ”; Previous Next Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges (links) we always start from the root (head) node. That is, we cannot randomly access a node in a tree. There are three ways which we use to traverse a tree − In-order Traversal Pre-order Traversal Post-order Traversal Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains. In-order Traversal In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. We should always remember that every node may represent a subtree itself. If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order. We start from A, and following in-order traversal, we move to its left subtree B.B is also traversed in-order. The process goes on until all the nodes are visited. The output of in-order traversal of this tree will be − D → B → E → A → F → C → G Algorithm Until all nodes are traversed − Step 1 − Recursively traverse left subtree. Step 2 − Visit root node. Step 3 − Recursively traverse right subtree. Example Following are the implementations of this operation in various programming languages − C C++ Java Python #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *leftChild; struct node *rightChild; }; struct node *root = NULL; void insert(int data){ struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data < parent->data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } void inorder_traversal(struct node* root){ if(root != NULL) { inorder_traversal(root->leftChild); printf(“%d “,root->data); inorder_traversal(root->rightChild); } } int main(){ int i; int array[7] = { 27, 14, 35, 10, 19, 31, 42 }; for(i = 0; i < 7; i++) insert(array[i]); printf(“Inorder traversal: “); inorder_traversal(root); return 0; } Output Inorder traversal: 10 14 19 27 31 35 42 #include <iostream> struct node { int data; struct node *leftChild; struct node *rightChild; }; struct node *root = NULL; void insert(int data){ struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data < parent->data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } void inorder_traversal(struct node* root){ if(root != NULL) { inorder_traversal(root->leftChild); printf(“%d “,root->data); inorder_traversal(root->rightChild); } } int main(){ int i; int array[7] = { 27, 14, 35, 10, 19, 31, 42 }; for(i = 0; i < 7; i++) insert(array[i]); printf(“Inorder traversal: “); inorder_traversal(root); return 0; } Output Inorder traversal: 10 14 19 27 31 35 42 class Node { int data; Node leftChild; Node rightChild; public Node(int key) { data = key; leftChild = rightChild = null; } } public class TreeDataStructure { Node root = null; void inorder_traversal(Node node) { if(node != null) { inorder_traversal(node.leftChild); System.out.print(node.data + ” “); inorder_traversal(node.rightChild); } } public static void main(String args[]) { TreeDataStructure tree = new TreeDataStructure(); tree.root = new Node(27); tree.root.leftChild = new Node(12); tree.root.rightChild = new Node(3); tree.root.leftChild.leftChild = new Node(44); tree.root.leftChild.rightChild = new Node(17); tree.root.rightChild.leftChild = new Node(56); System.out.println(“Inorder traversal: “); tree.inorder_traversal(tree.root); } } Output Inorder traversal: 44 12 17 27 56 3 class Node: def __init__(self, key): self.leftChild = None self.rightChild = None self.data = key # Create a function to perform inorder tree traversal def InorderTraversal(root): if root: InorderTraversal(root.leftChild) print(root.data) InorderTraversal(root.rightChild) # Main class if __name__ == “__main__”: root = Node(3) root.leftChild = Node(26) root.rightChild = Node(42) root.leftChild.leftChild = Node(54) root.leftChild.rightChild = Node(65) root.rightChild.leftChild = Node(12) # Function call print(“Inorder traversal of binary tree is”) InorderTraversal(root) Output Inorder traversal of binary tree is 54 26 65 3 12 42 Pre-order Traversal In this traversal method, the root node is visited first, then the left subtree and finally the right subtree. We start from A, and following pre-order traversal, we first visit A itself and then move to its left subtree B. B is also traversed pre-order. The process goes on until all the nodes are visited. The output of pre-order traversal of this tree will be − A → B → D → E → C → F → G Algorithm Until all nodes are traversed − Step 1 − Visit root node. Step 2 − Recursively traverse left subtree. Step 3 − Recursively traverse right subtree. Example Following are the implementations of this operation in various programming languages −

AVL Trees Table of content Basic Operations of AVL Trees Insertion operation Deletion operation ”; Previous Next The first type of self-balancing binary search tree to be invented is the AVL tree. The name AVL tree is coined after its inventor”s names − Adelson-Velsky and Landis. In AVL trees, the difference between the heights of left and right subtrees, known as the Balance Factor, must be at most one. Once the difference exceeds one, the tree automatically executes the balancing algorithm until the difference becomes one again. BALANCE FACTOR = HEIGHT(LEFT SUBTREE) − HEIGHT(RIGHT SUBTREE) There are usually four cases of rotation in the balancing algorithm of AVL trees: LL, RR, LR, RL. LL Rotations LL rotation is performed when the node is inserted into the right subtree leading to an unbalanced tree. This is a single left rotation to make the tree balanced again − Fig : LL Rotation The node where the unbalance occurs becomes the left child and the newly added node becomes the right child with the middle node as the parent node. RR Rotations RR rotation is performed when the node is inserted into the left subtree leading to an unbalanced tree. This is a single right rotation to make the tree balanced again − Fig : RR Rotation The node where the unbalance occurs becomes the right child and the newly added node becomes the left child with the middle node as the parent node. LR Rotations LR rotation is the extended version of the previous single rotations, also called a double rotation. It is performed when a node is inserted into the right subtree of the left subtree. The LR rotation is a combination of the left rotation followed by the right rotation. There are multiple steps to be followed to carry this out. Consider an example with “A” as the root node, “B” as the left child of “A” and “C” as the right child of “B”. Since the unbalance occurs at A, a left rotation is applied on the child nodes of A, i.e. B and C. After the rotation, the C node becomes the left child of A and B becomes the left child of C. The unbalance still persists, therefore a right rotation is applied at the root node A and the left child C. After the final right rotation, C becomes the root node, A becomes the right child and B is the left child. Fig : LR Rotation RL Rotations RL rotation is also the extended version of the previous single rotations, hence it is called a double rotation and it is performed if a node is inserted into the left subtree of the right subtree. The RL rotation is a combination of the right rotation followed by the left rotation. There are multiple steps to be followed to carry this out. Consider an example with “A” as the root node, “B” as the right child of “A” and “C” as the left child of “B”. Since the unbalance occurs at A, a right rotation is applied on the child nodes of A, i.e. B and C. After the rotation, the C node becomes the right child of A and B becomes the right child of C. The unbalance still persists, therefore a left rotation is applied at the root node A and the right child C. After the final left rotation, C becomes the root node, A becomes the left child and B is the right child. Fig : RL Rotation Basic Operations of AVL Trees The basic operations performed on the AVL Tree structures include all the operations performed on a binary search tree, since the AVL Tree at its core is actually just a binary search tree holding all its properties. Therefore, basic operations performed on an AVL Tree are − Insertion and Deletion. Insertion operation The data is inserted into the AVL Tree by following the Binary Search Tree property of insertion, i.e. the left subtree must contain elements less than the root value and right subtree must contain all the greater elements. However, in AVL Trees, after the insertion of each element, the balance factor of the tree is checked; if it does not exceed 1, the tree is left as it is. But if the balance factor exceeds 1, a balancing algorithm is applied to readjust the tree such that balance factor becomes less than or equal to 1 again. Algorithm The following steps are involved in performing the insertion operation of an AVL Tree − Step 1 − Create a node Step 2 − Check if the tree is empty Step 3 − If the tree is empty, the new node created will become the root node of the AVL Tree. Step 4 − If the tree is not empty, we perform the Binary Search Tree insertion operation and check the balancing factor of the node in the tree. Step 5 − Suppose the balancing factor exceeds ±1, we apply suitable rotations on the said node and resume the insertion from Step 4. Let us understand the insertion operation by constructing an example AVL tree with 1 to 7 integers. Starting with the first element 1, we create a node and measure the balance, i.e., 0. Since both the binary search property and the balance factor are satisfied, we insert another element into the tree. The balance factor for the two nodes are calculated and is found to be -1 (Height of left subtree is 0 and height of the right subtree is 1). Since it does

Spanning Tree ”; Previous Next What is Spanning Tree? A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.. By this definition, we can draw a conclusion that every connected and undirected Graph G has at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices. We found three spanning trees off one complete graph. A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number of nodes. In the above addressed example, n is 3, hence 33−2 = 3 spanning trees are possible. General Properties of Spanning Tree We now understand that one graph can have more than one spanning tree. Following are a few properties of the spanning tree connected to graph G − A connected graph G can have more than one spanning tree. All possible spanning trees of graph G, have the same number of edges and vertices. The spanning tree does not have any cycle (loops). Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning tree is minimally connected. Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is maximally acyclic. Mathematical Properties of Spanning Tree Spanning tree has n-1 edges, where n is the number of nodes (vertices). From a complete graph, by removing maximum e – n &plus; 1 edges, we can construct a spanning tree. A complete graph can have maximum nn-2 number of spanning trees. Thus, we can conclude that spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree. Application of Spanning Tree Spanning tree is basically used to find a minimum path to connect all nodes in a graph. Common application of spanning trees are − Civil Network Planning Computer Network Routing Protocol Cluster Analysis Let us understand this through a small example. Consider, city network as a huge graph and now plans to deploy telephone lines in such a way that in minimum lines we can connect to all city nodes. This is where the spanning tree comes into picture. Minimum Spanning Tree (MST) In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph. In real-world situations, this weight can be measured as distance, congestion, traffic load or any arbitrary value denoted to the edges. Minimum Spanning-Tree Algorithm We shall learn about two most important spanning tree algorithms here − Kruskal”s Algorithm Prim”s Algorithm These two algorithms are Greedy algorithms. Print Page Previous Next Advertisements ”;

Insertion Sort Algorithm Table of content Insertion Sort Algorithm Implementation ”; Previous Next Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game. This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be ”inserted” in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort. The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2), where n is the number of items. Insertion Sort Algorithm Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by which we can achieve insertion sort. Step 1 − If it is the first element, it is already sorted. return 1; Step 2 − Pick next element Step 3 − Compare with all elements in the sorted sub-list Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted Step 5 − Insert the value Step 6 − Repeat until list is sorted Pseudocode Algorithm: Insertion-Sort(A) for j = 2 to A.length key = A[j] i = j – 1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i -1 A[i + 1] = key Analysis Run time of this algorithm is very much dependent on the given input. If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n2) time. Example We take an unsorted array for our example. Insertion sort compares the first two elements. It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list. Insertion sort moves ahead and compares 33 with 27. And finds that 33 is not in the correct position. It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping. By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10. These values are not in a sorted order. So they are swapped. However, swapping makes 27 and 10 unsorted. Hence, we swap them too. Again we find 14 and 10 in an unsorted order. We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items. This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see some programming aspects of insertion sort. Implementation Since insertion sort is an in-place sorting algorithm, the algorithm is implemented in a way where the key element – which is iteratively chosen as every element in the array – is compared with it consequent elements to check its position. If the key element is less than its successive element, the swapping is not done. Otherwise, the two elements compared will be swapped and the next element is chosen as the key element. Insertion sort is implemented in four programming languages, C, C++, Java, and Python − C C++ Java Python #include <stdio.h> void insertionSort(int array[], int size){ int key, j; for(int i = 1; i<size; i++) { key = array[i];//take value j = i; while(j > 0 && array[j-1]>key) { array[j] = array[j-1]; j–; } array[j] = key; //insert in right place } } int main(){ int n; n = 5; int arr[5] = {67, 44, 82, 17, 20}; // initialize the array printf(“Array before Sorting: “); for(int i = 0; i<n; i++) printf(“%d “,arr[i]); printf(“n”); insertionSort(arr, n); printf(“Array after Sorting: “); for(int i = 0; i<n; i++) printf(“%d “, arr[i]); printf(“n”); } Output Array before Sorting: 67 44 82 17 20 Array after Sorting: 17 20 44 67 82 #include<iostream> using namespace std; void insertionSort(int *array, int size){ int key, j; for(int i = 1; i<size; i++) { key = array[i];//take value j = i; while(j > 0 && array[j-1]>key) { array[j] = array[j-1]; j–; } array[j] = key; //insert in right place } } int main(){ int n; n = 5; int arr[5] = {67, 44, 82, 17, 20}; // initialize the array cout << “Array before Sorting: “; for(int i = 0; i<n; i++) cout << arr[i] << ” “; cout << endl; insertionSort(arr, n); cout << “Array after Sorting: “; for(int i = 0; i<n; i++) cout << arr[i] << ” “; cout << endl; } Output Array before Sorting: 67 44 82 17 20 Array after Sorting: 17 20 44 67 82 import java.io.*; public class InsertionSort { public static void main(String args[]) { int n = 5; int[] arr = {67, 44, 82, 17, 20}; //initialize an array System.out.print(“Array before Sorting: “); for(int i = 0; i<n; i++) System.out.print(arr[i] + ” “); System.out.println(); for(int i = 1; i<n; i++) { int key = arr[i];//take value int j = i; while(j > 0 && arr[j-1]>key) { arr[j]

Bucket Sort Algorithm Table of content Bucket Sort Algorithm Implementation ”; Previous Next The Bucket Sort algorithm is similar to the Counting Sort algorithm, as it is just the generalized form of the counting sort. Bucket sort assumes that the input elements are drawn from a uniform distribution over the interval [0, 1). Hence, the bucket sort algorithm divides the interval [0, 1) into ‘n’ equal parts, and the input elements are added to indexed buckets where the indices based on the lower bound of the (n × element) value. Since the algorithm assumes the values as the independent numbers evenly distributed over a small range, not many elements fall into one bucket only. For example, let us look at an input list of elements, 0.08, 0.01, 0.19, 0.89, 0.34, 0.07, 0.30, 0.82, 0.39, 0.45, 0.36. The bucket sort would look like − Bucket Sort Algorithm Let us look at how this algorithm would proceed further below − Step 1 − Divide the interval in ‘n’ equal parts, each part being referred to as a bucket. Say if n is 10, then there are 10 buckets; otherwise more. Step 2 − Take the input elements from the input array A and add them to these output buckets B based on the computation formula, B[i]= $lfloor$n.A[i]$rfloor$ Step 3 − If there are any elements being added to the already occupied buckets, created a linked list through the corresponding bucket. Step 4 − Then we apply insertion sort to sort all the elements in each bucket. Step 5 − These buckets are concatenated together which in turn is obtained as the output. Pseudocode BUCKET-SORT(A) let B[0 … n – 1] be a new array n = A.length for i = 0 to n – 1 make B[i] an empty list for i = 1 to n insert A[i] into list B[$lfloor$𝑛.𝐴[𝑖]$rfloor$] for i = 0 to n – 1 sort list B[i] with insertion sort concatenate the lists B[0], B[1]; ………… ; B[n – 1] together in order Analysis The bucket sort algorithm assumes the identity of the input, therefore, the average case time complexity of the algorithm is Θ(n) Example Consider, an input list of elements, 0.78, 0.17, 0.93, 0.39, 0.26, 0.72, 0.21, 0.12, 0.33, 0.28, to sort these elements using bucket sort − Solution Step 1 Linearly insert all the elements from the index ‘0’ of the input array. That is, we insert 0.78 first followed by other elements sequentially. The position to insert the element is obtained using the formula − B[i]= $lfloor$n.A[i]$rfloor$, i.e, $lfloor$10 ×0.78$rfloor$=7 Now, we insert 0.17 at index $lfloor$10 ×0.17$rfloor$=1 Step 3 Inserting the next element, 0.93 into the output buckets at $lfloor$10 ×0.93$rfloor$=9 Step 4 Insert 0.39 at index 3 using the formula $lfloor$10 ×0.39$rfloor$=3 Step 5 Inserting the next element in the input array, 0.26, at position $lfloor$10 ×0.26$rfloor$=2 Step 6 Here is where it gets tricky. Now, the next element in the input list is 0.72 which needs to be inserted at index ‘7’ using the formula $lfloor$10 ×0.72$rfloor$=7. But there’s already a number in the 7th bucket. So, a link is created from the 7th index to store the new number like a linked list, as shown below − Step 7 Add the remaining numbers to the buckets in the similar manner by creating linked lists from the desired buckets. But while inserting these elements as lists, we apply insertion sort, i.e., compare the two elements and add the minimum value at the front as shown below − Step 8 Now, to achieve the output, concatenate all the buckets together. 0.12, 0.17, 0.21, 0.26, 0.28, 0.33, 0.39, 0.72, 0.78, 0.93 Implementation The implementation of the bucket sort algorithm first retrieves the maximum element of the array and decides the bucket size of the output. The elements are inserted into these buckets based on few computations. In this tutorial, we execute bucket sort in four programming languages. C C++ Java Python #include <stdio.h> void bucketsort(int a[], int n){ // function to implement bucket sort int max = a[0]; // get the maximum element in the array for (int i = 1; i < n; i++) if (a[i] > max) max = a[i]; int b[max], i; for (int i = 0; i <= max; i++) { b[i] = 0; } for (int i = 0; i < n; i++) { b[a[i]]++; } for (int i = 0, j = 0; i <= max; i++) { while (b[i] > 0) { a[j++] = i; b[i]–; } } } int main(){ int a[] = {12, 45, 33, 87, 56, 9, 11, 7, 67}; int n = sizeof(a) / sizeof(a[0]); // n is the size of array printf(“Before sorting array elements are: n”); for (int i = 0; i < n; ++i) printf(“%d “, a[i]); bucketsort(a, n); printf(“nAfter sorting array elements are: n”); for (int i = 0; i < n; ++i) printf(“%d “, a[i]); } Output Before sorting array elements are: 12 45 33 87 56 9 11 7 67 After sorting array elements are: 7 9 11 12 33 45 56 67 87 #include <iostream> using namespace std; void bucketsort(int a[], int n){ // function to implement bucket sort int max = a[0]; // get the maximum element in the array for (int i = 1; i < n; i++) if (a[i] > max) max = a[i]; int b[max], i; for (int i = 0; i <= max; i++) { b[i] = 0; } for (int i = 0; i < n; i++) { b[a[i]]++; }

Data Structures – Sorting Techniques ”; Previous Next Sorting refers to arranging data in a particular format. Sorting algorithm specifies the way to arrange data in a particular order. Most common orders are in numerical or lexicographical order. The importance of sorting lies in the fact that data searching can be optimized to a very high level, if data is stored in a sorted manner. Sorting is also used to represent data in more readable formats. Following are some of the examples of sorting in real-life scenarios − Telephone Directory − The telephone directory stores the telephone numbers of people sorted by their names, so that the names can be searched easily. Dictionary − The dictionary stores words in an alphabetical order so that searching of any word becomes easy. In-place Sorting and Not-in-place Sorting Sorting algorithms may require some extra space for comparison and temporary storage of few data elements. These algorithms do not require any extra space and sorting is said to happen in-place, or for example, within the array itself. This is called in-place sorting. Bubble sort is an example of in-place sorting. However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting. Stable and Not Stable Sorting If a sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear, it is called stable sorting. If a sorting algorithm, after sorting the contents, changes the sequence of similar content in which they appear, it is called unstable sorting. Stability of an algorithm matters when we wish to maintain the sequence of original elements, like in a tuple for example. Adaptive and Non-Adaptive Sorting Algorithm A sorting algorithm is said to be adaptive, if it takes advantage of already ”sorted” elements in the list that is to be sorted. That is, while sorting if the source list has some element already sorted, adaptive algorithms will take this into account and will try not to re-order them. A non-adaptive algorithm is one which does not take into account the elements which are already sorted. They try to force every single element to be re-ordered to confirm their sorted ness. Important Terms Some terms are generally coined while discussing sorting techniques, here is a brief introduction to them − Increasing Order A sequence of values is said to be in increasing order, if the successive element is greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element is greater than the previous element. Decreasing Order A sequence of values is said to be in decreasing order, if the successive element is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element is less than the previous element. Non-Increasing Order A sequence of values is said to be in non-increasing order, if the successive element is less than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as every next element is less than or equal to (in case of 3) but not greater than any previous element. Non-Decreasing Order A sequence of values is said to be in non-decreasing order, if the successive element is greater than or equal to its previous element in the sequence. This order occurs when the sequence contains duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing order, as every next element is greater than or equal to (in case of 3) but not less than the previous one. There are several sorting techniques available to sort the contents of various data structures. Following are some of those − Bubble Sort Insertion Sort Selection Sort Merge Sort Shell Sort Heap Sort Bucket Sort Algorithm Counting Sort Algorithm Radix Sort Algorithm Quick Sort Print Page Previous Next Advertisements ”;