CU-BCA-SEM-III-DATA STRUCTURES- Second Draft-converted

• B-trees are balance M-way trees, which are well suited for disks 13.6 KEYWORDS • BST: Binary Search Tree • AVL tree: AVL tree is a height balance binary search tree • B-Tree: B-trees are balance M-way tree 13.7 LEARNING ACTIVITY Write the functions to perform the double rotation without the inefficiency of doing two single rotations. A binary search tree presupposes that searching is based on only one key per record. suppose we would like to be able to perform searching based on either of two keys key1 or key2. 1. One method is to build two separate binary search trees. How many extra pointers does this require? ___________________________________________________________________________ ___________________________________________________________________ 2. Write an efficient procedure that prints all records in the tree that simultaneously satisfy the constraints low1 <= key1 <= high1 and low2 <= key2 <= high2 ___________________________________________________________________________ ____________________________________________________________________ 13.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define binary search tree. Why it is preferred rather than the sorted linear array and linked list? 2. Give the difference between binary tree and binary search tree? 3. List out the steps involved in deleting a node from a binary search tree 4. Define B tree 5. Define single rotation on AVL tree Long Questions 1. Explain binary search tree ADT in detail 201 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Define a BST. Give the analysis of insertion and deletion operations of nodes in binary search tree 3. Define AVL Trees. Explain its rotation operations with example. 4. Write down an algorithm to insert a given element in a binary search tree and AVL structure 5. Write routines for ADT operation of AVL tree B. Multiple choice Questions 1. Which of the following is false about a binary search tree? a. The left child is always lesser than its parent b. The right child is always greater than its parent c. The left and right sub-trees should also be binary search trees d. In order sequence gives decreasing order of elements 2. What is the speciality about the in-order traversal of a binary search tree? a. It traverses in a non-increasing order b. It traverses in an increasing order c. It traverses in a random fashion d. It traverses based on priority of the node 3. What does the following piece of code do? 202 public void func(Tree root) { func(root.left()); func(root.right()); System.out.println(root.data()); } a. Preorder traversal b. Inorder traversal c. Postorder traversal d. Level order traversal CU IDOL SELF LEARNING MATERIAL (SLM)

4. What does the following piece of code do? public void func(Tree root) { System.out.println(root.data()); func(root.left()); func(root.right()); } a. Preorder traversal b. Inorder traversal c. Postorder traversal d. Level order traversal 5. Which of the following is not the self-balancing binary search tree? a. AVL Tree b. 2-3-4 Tree c. Red – Black Tree d. Splay Tree Answer 1. (d) 2. (b) 3. (c) 4. (a) 5. (b) 13.9 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ 203 CU IDOL SELF LEARNING MATERIAL (SLM)

• https://www.tutorialspoint.com/ 204 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 14: GRAPH Structure 14.0 Learning Objective 14.1 Introduction and Terminology 14.2 Memory Representation of Graphs and Adjacency Matrix and List 14.3 Graph Operation: Depth First Search 14.4 Graph Operation: Breath First Search 14.5 Summary 14.6 Keywords 14.7 Learning activity 14.8 Unit End Questions 14.9 References 14.0 LEARNING OBJECTIVE After studying this unit, Students will be able to • Analyse what a graph is and how it is used. • State to implement the graph abstract data type using multiple internal representations. • Describe how operations of graphs can be used to solve a wide variety of problems. • Explain the importance of data structures in context of writing efficient programs. • Define the appropriate data structure and algorithm design method for a specified application. 14.1 INTRODUCTION AND TERMINOLOGY Graph is a non-linear data structure. It contains a set of points known as nodes (or vertices) and a set of links known as edges (or Arcs). Here edges are used to connect the vertices. 1. Graph is a collection of vertices and arcs in which vertices are connected with arcs 2. Graph is a collection of nodes and edges in which nodes are connected with edges Generally, a graph G is represented as ������ = (������ , ������) where V is set of vertices and E is set of edges. 205 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 14.1: Graph Representation The following is a graph with 5 vertices and 6 edges. This graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. Graph Terminology: Vertex Individual data element of a graph is called as Vertex. Vertex is also known as node. In above example graph, A, B, C, D & E are known as vertices. Edge An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as (startingVertex, endingVertex). For example, in above graph the link between vertices A and B is represented as (A,B). In above example graph, there are 7 edges (i.e., (A,B),(A,C),(A,D),(B,D),(B,E),(C,D),(D,E)). Edges are three types. 1. Undirected Edge - An undirected egde is a bidirectional edge. If there is undirected edge between vertices A and B then edge (A , B) is equal to edge (B , A). 2. Directed Edge - A directed egde is a unidirectional edge. If there is directed edge between vertices A and B then edge (A , B) is not equal to edge (B , A). 3. Weighted Edge - A weighted egde is an edge with value (cost) on it. Outdegree Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex. Parallel edges or Multiple edges If there are two undirected edges with same end vertices and two directed edges with same origin and destination, such edges are called parallel edges or multiple edges. Self-loop Edge (undirected or directed) is a self-loop if its two endpoints coincide with each other. Simple Graph 206 CU IDOL SELF LEARNING MATERIAL (SLM)

A graph is said to be simple if there are no parallel and self-loop edges. Path A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex such that each edge is incident to its predecessor and successor vertex. Outgoing Edge A directed edge is said to be outgoing edge on its origin vertex. Incoming Edge A directed edge is said to be incoming edge on its destination vertex. Degree Total number of edges connected to a vertex is said to be degree of that vertex. Indegree Total number of incoming edges connected to a vertex is said to be indegree of that vertex. Undirected Graph A graph with only undirected edges is said to be undirected graph. Directed Graph A graph with only directed edges is said to be directed graph. Mixed Graph A graph with both undirected and directed edges is said to be mixed graph. End vertices or Endpoints The two vertices joined by edge are called end vertices (or endpoints) of that edge. Origin If an edge is directed, its first endpoint is said to be the origin of it. Destination If an edge is directed, its first endpoint is said to be the origin of it and the other endpoint is said to be the destination of that edge. Adjacent If there is an edge between vertices A and B then both A and B are said to be adjacent. In other words, vertices A and B are said to be adjacent if there is an edge between them. Incident Edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge. 207 CU IDOL SELF LEARNING MATERIAL (SLM)

14.2 MEMORY REPRESENTATION OF GRAPHS Graph data structure is represented using following representations. 1. Adjacency Matrix 2. Incidence Matrix 3. Adjacency List Adjacency Matrix: In this representation, the graph is represented employing a matrix of size total number of vertices by a complete number of vertices. meaning a graph with 4 vertices is represented employing a matrix of size 4X4. during this matrix, both rows and columns represent vertices. This matrix is crammed with either 1 or 0. Here, 1 represents that there's a foothold from row vertex to column vertex and 0 represents that there's no edge from row vertex to column vertex. for instance, consider the subsequent undirected graph representation. Figure 14.2: Undirected Graph Adjacency Matrix representation Directed graph representation: Figure 14.3: Directed graph Adjacency Matrix representation 208 CU IDOL SELF LEARNING MATERIAL (SLM)

Incidence Matrix The graph is represented employing a matrix of size total number of vertices by a complete number of edges. meaning graph with 4 vertices and 6 edges is represented employing a matrix of size 4X6. during this matrix, rows represent vertices and columns represents edges. This matrix is crammed with 0 or 1 or -1. Here, 0 represents that the row edge isn't connected to column vertex, 1 represents that the row edge is connected because the outgoing edge to column vertex and -1 represents that the row edge is connected because the incoming edge to column vertex. Figure 14.4: Directed graph Incidence Matrix representation Adjacency List: Every vertex of a graph contains a list of its adjacent vertices in this representation. For example, consider the following directed graph representation implemented using linked list... Figure 14.5: Directed graph Adjacency List representation This representation can also be implemented using an array as follows. Figure 14.6: Directed graph Adjacency Array representation 209 CU IDOL SELF LEARNING MATERIAL (SLM)

14.3 GRAPH OPERATION: DEPTH FIRST SEARCH Depth First Search (DFS): The DFS algorithm may be a recursive algorithm that uses the thought of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. Here, the word backtrack means once you are moving forward and there are not any more nodes along the present path, you progress backwards on an equivalent path to seek out nodes to traverse. All the nodes are going to be visited on the present path till all the unvisited nodes are traversed after which subsequent path are going to be selected. This recursive nature of DFS is often implemented using stacks. the essential idea is as follows: Pick a starting node and push all its adjacent nodes into a stack. Pop a node from stack to pick subsequent node to go to and push all its adjacent nodes into a stack. Repeat this process until the stack is empty. However, make sure that the nodes that are visited are marked. this may prevent you from visiting an equivalent node quite once. If you are doing not mark the nodes that are visited and you visit an equivalent node quite once, you'll find yourself in an infinite loop. Algorithm: Procedure DFS-recursive(G, s): mark s as visited for all neighbours w of s in Graph G: if w is not visited: DFS-recursive(G, w) end procedure Depth First Search Example We use an undirected graph with 5 vertices. Figure 14.7: Depth First Search Initialization 210 CU IDOL SELF LEARNING MATERIAL (SLM)

Undirected graph with 5 vertices We start from vertex 0, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack. Figure 14.8: Depth First Search visit 0th node Visit the element and put it in the visited list Next, we visit the element at the top of stack i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead. Figure 14.9: Depth First Search visit 1st node Visit the element at the top of stack Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it. 211 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 14.10: Depth First Search visit 2nd node Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it. Figure 14.11: Depth First Search visit 4th node Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the top of the stack and visit it. After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph. Figure 14.12: Depth First Search visit 3rd node After we visit the last element 3, it doesn't have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph. 14.4 GRAPH OPERATION: BREATH FIRST SEARCH Traversal means visiting all the nodes of a graph. Breadth First Traversal or Breadth First Search is a recursive algorithm for searching all the vertices of a graph or tree data structure. BFS algorithm: Procedure DFS-recursive(G, s): 212 CU IDOL SELF LEARNING MATERIAL (SLM)

create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u end procedure Example Program: void bfs(struct Graph* graph, int startVertex) { struct queue* q = createQueue(); graph->visited[startVertex] = 1; enqueue(q, startVertex); while (!isEmpty(q)) { printQueue(q); int currentVertex = dequeue(q); printf(\"Visited %d\\n\", currentVertex); struct node* temp = graph->adjLists[currentVertex]; while (temp) { int adjVertex = temp->vertex; if (graph->visited[adjVertex] == 0) { graph->visited[adjVertex] = 1; enqueue(q, adjVertex); } temp = temp->next; } 213 CU IDOL SELF LEARNING MATERIAL (SLM)

} } A standard BFS implementation puts each vertex of the graph into one among two categories: 1. Visited Node 2. Not Visited Node The purpose of the algorithm is to mark each vertex as visited while avoiding cycles. The algorithm works as follows: 1. Start by putting anybody of the graph's vertices at the rear of a queue. 2. Take the front item of the queue and add it to the visited list. 3. Create an inventory of that vertex's adjacent nodes. Add those which are not within the visited list to the rear of the queue. 4. Keep repeating steps 2 and three until the queue is empty. The graph may need two different disconnected parts so to form sure that we cover every vertex, we will also run the BFS algorithm on every node BFS example Figure 14.13: Breath First Search initialization We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack. 214 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 14.14: Breath First Search visit 0th Node Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead. Figure 14.15: Breath First Search visit 1st Node Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of the queue and visit 3, which is at the front of the queue. Figure 14.16: Breath First Search visit 2nd Node 215 CU IDOL SELF LEARNING MATERIAL (SLM)

Visit 2 which was added to queue earlier to add its neighbours Figure 14.17: Breath First Search visit 4th Node 4 remains in the queue Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already visited. We visit it. Figure 14.18: Breath First Search visit 3rd Node Visit last remaining item in the stack to check if it has unvisited neighbours Since the queue is empty, we have completed the Breadth First Traversal of the graph. BFS Algorithm Applications 1. To build index by search index 2. For GPS navigation 3. Path finding algorithms 4. In Ford-Fulkerson algorithm to find maximum flow in a network 5. Cycle detection in an undirected graph 216 CU IDOL SELF LEARNING MATERIAL (SLM)

6. In minimum spanning tree 14.5 SUMMARY • Graph is a non-linear data structure. It contains a set of points known as nodes (or vertices) and a set of links known as edges (or Arcs). • Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. • DFS(Depth First Search) uses Stack data structure. • BFS (Breadth First Search) uses Queue data structure for finding the shortest path. • BFS can be used to find single source shortest path in an unweighted graph, because in BFS, we reach a vertex with minimum number of edges from a source vertex 14.6 KEYWORDS • Vertex: Individual data element of a graph is called as Vertex. Vertex is also known as node. • Edge: An edge is a connecting link between two vertices. Edge is also known as Arc. Undirected Edge - An undirected edge is a bidirectional edge. If there is undirected edge between vertices A and B then edge (A, B) is equal to edge (B, A). • Directed Edge - A directed edge is a unidirectional edge. If there is directed edge between vertices A and B then edge (A, B) is not equal to edge (B, A). • Weighted Edge - A weighted egde is an edge with value (cost) on it. • Outdegree: Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex. • Path: A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex such that each edge is incident to its predecessor and successor vertex. • Outgoing Edge: A directed edge is said to be outgoing edge on its origin vertex. • Incoming Edge: A directed edge is said to be incoming edge on its destination vertex. • Degree: Total number of edges connected to a vertex is said to be degree of that vertex. 217 CU IDOL SELF LEARNING MATERIAL (SLM)

• Indegree: Total number of incoming edges connected to a vertex is said to be indegree of that vertex. • Adjacent: If there is an edge between vertices A and B then both A and B are said to be adjacent. In other words, vertices A and B are said to be adjacent if there is an edge between them. • Incident: Edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge. 14.7 LEARNING ACTIVITY You are given a set of N sticks, which are lying on top of each other in some configuration. Each stick is specified by its two endpoints; each endpoint is an ordered triple giving its x, y , and z coordinates; no stick is vertical. A stick may be picked up only if there is no stick on top of it. 1. Explain how to write a routine that takes two sticks a and b and reports whether a is above, below, or unrelated to b. ___________________________________________________________________________ ____________________________________________________________________ 14.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define DFS and BFS? 2. List out the applications of DFS and BFS 3. What is an adjacency list? When it is used? 4. Define and Write the routine for Depth first and breadth first traversal 5. What is meant by digraph? Define the terms in-degree and out–degree with respect to digraph Long Questions 1. Write down the adjacency matrix of the graph. 218 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Explain in details about adjacency list? When it is used? 3. Explain in details about Depth first search? 4. Explain in details about Breath first search? 5. Define and Write the routine for Depth first and breadth first traversal. B. Multiple choice Questions 1. For the given conditions, which of the following is in the correct order of increasing space requirement? I. Undirected, no weight II. Directed, no weight III. Directed, weighted IV. Undirected, weighted a. ii iii i iv b. i iii ii iv c. iv iii i ii d. i ii iii iv 2. In which case adjacency list is preferred in front of an adjacency matrix? a. Dense graph b. Sparse graph c. Adjacency list is always preferred d. Complete graph 219 CU IDOL SELF LEARNING MATERIAL (SLM)

3. What would be the number of zeros in the adjacency matrix of the given graph? a. 10 b. 6 c. 16 d. 0 4. For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree. a. in, out b. out, in c. in, total d. total, out 5. How many of the following statements are correct? i) All cyclic graphs are complete graphs. ii) All complete graphs are cyclic graphs. iii) All paths are bipartite. iv) All cyclic graphs are bipartite. v) There are cyclic graphs which are complete. a. 1 b. 2 c. 3 d. 4 Answer 1. (a) 2. (b) 3. (c) 4. (b) 5. (b) 220 CU IDOL SELF LEARNING MATERIAL (SLM)

14.9 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 221 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 15: SORTING Structure 15.0 Learning Objective 15.1 Bubble Sort 15.2 Selection Sort 15.3 Radix Sort 15.4 Insertion Sort 15.5 Merge Sort 15.6 Summary 15.7 Keywords 15.8 Learning activity 15.9 Unit End Questions 15.10 References 15.0 LEARNING OBJECTIVE After studying this unit, students will be able to • Describe the basic data structures and their implementations. • Elaborate the applications of Sorting. • Describe and analyze the types of sorting algorithms such as Selection sort, Bubble sort, Radix Sort, Insertion sort, and Merge sort. • Summarize sorting techniques. 15.1 BUBBLE SORT Bubble sort may be a simple algorithm. This algorithm is employed to sort N elements that are given during a memory for e.g.: An Array with N number of elements. Bubble Sort compares the whole element one by one and type them supported their values. it's also referred to as Sinking Sort. It is called Bubble sort, because with each iteration the most important element within the list bubbles up towards the last place, a bit like a water bubble rises up to the water surface. 222 CU IDOL SELF LEARNING MATERIAL (SLM)

Sorting takes place by stepping through all the info items one-by-one in pairs and comparing adjacent data items and swapping each pair that's out of order. Let's consider an array with values {5, 1, 6, 2, 4, 3} Below, we've a picturing of how bubble sort will sort the given array. Figure 15.1: Bubble Sort Iteration 223 Algorithm: begin BubbleSort(list) for all elements of list if list[i] > list[i+1] swap(list[i], list[i+1]) CU IDOL SELF LEARNING MATERIAL (SLM)

end if 224 end for return list end BubbleSort Example Program: void bubbleSort(int arr[], int n) { int i, j, temp; for(i = 0; i < n; i++) { for(j = 0; j < n-i-1; j++) { if( arr[j] > arr[j+1]) { // swap the elements temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } // print the sorted array printf(\"Sorted Array: \"); for(i = 0; i < n; i++) { printf(\"%d \", arr[i]); } } CU IDOL SELF LEARNING MATERIAL (SLM)

15.2 SELECTION SORT The most fundamental algorithm is selection form. This algorithm would start by finding the littlest element within the array and swapping it with the element within the first position, then moving on to the second smallest element and swapping it with the element within the second position, then on until the entire array has been sorted. Following are the steps involved in selection sort (for sorting a given array in ascending order): 1. ranging from the primary element, we search the littlest element within the array, and replace it with the element within the first position. 2. We then advance to the second position, and appearance for smallest element present within the subarray, ranging from index 1, till the last index. 3. We replace the element at the second position within the original array, or we will say at the primary position within the subarray, with the second smallest element. 4. this is often repeated until the array is totally sorted. Consider the following depicted array as an example. For the first position in the sorted list, the whole list is scanned sequentially. The first position where 14 is stored presently, we search the whole list and find that 10 is the lowest value. So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in the list, appears in the first position of the sorted list. For the second position, where 33 is residing, we start scanning the rest of the list in a linear manner. 225 CU IDOL SELF LEARNING MATERIAL (SLM)

We find that 14 is the second lowest value in the list and it should appear at the second place. We swap these values. After two iterations, two least values are positioned at the beginning in a sorted manner. The same process is applied to the rest of the items in the array. Following is a pictorial depiction of the entire sorting process − Algorithm: Figure 15.2: Selection Sort Iteration CU IDOL SELF LEARNING MATERIAL (SLM) 226

begin selectionSort(array, size) repeat (size - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element < currentMinimum set element as new minimum swap minimum with first unsorted position end selectionSort Example program: void selectionSort(int array[], int size) { for (int step = 0; step < size - 1; step++) { int min_idx = step; for (int i = step + 1; i < size; i++) { // To sort in descending order, change > to < in this line. // Select the minimum element in each loop. if (array[i] < array[min_idx]) min_idx = i; } // put min at the correct position 227 swap(&array[min_idx], &array[step]); } } void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } CU IDOL SELF LEARNING MATERIAL (SLM)

Selection Sort Applications 1. a small list is to be sorted 2. cost of swapping does not matter 3. checking of all the elements is compulsory 4. cost of writing to a memory matters like in flash memory (number of writes/swaps is O(n) as compared to O(n2) of bubble sort) 15.3 RADIX SORT Radix sort is an integer algorithm that sorts data with integer keys by grouping the keys by individual digits that share an equivalent significant position and value (place value). Radix sort uses counting sort as a subroutine to sort an array of numbers. Because integers are often wont to represent strings (by hashing the strings to integers), radix sort works on data types aside from just integers. Radix sort incorporates the counting sort algorithm in order that it can sort larger, multi-digit numbers without having to potentially decrease the efficiency by increasing the range of keys the algorithm must sort over (since this might cause tons of wasted time). Consider the array of length 6 given below. Sort the array by using Radix sort. A = {10, 2, 901, 803, 1024} Pass 1: (Sort the list according to the digits at 0's place) 10, 901, 2, 803, 1024. Pass 2: (Sort the list according to the digits at 10's place) 02, 10, 901, 803, 1024 Pass 3: (Sort the list according to the digits at 100's place) 02, 10, 1024, 803, 901. Pass 4: (Sort the list according to the digits at 1000's place) 02, 10, 803, 901, 1024 Therefore, the list generated in the step 4 is the sorted list, arranged from radix sort. Algorithm: 228 Begin Radix-Sort (list, n) shift = 1 CU IDOL SELF LEARNING MATERIAL (SLM)

for loop = 1 to keysize do for entry = 1 to n do bucketnumber = (list[entry].key / shift) mod 10 append (bucket[bucketnumber], list[entry]) list = combinebuckets() shift = shift * 10 end Radix-Sort; Example Program: void radixsort(ll arr[],int n,int maxx) //maxx is the maximum element in the array { int mul=1; while(maxx) { countsort(arr,n,mul); mul*=10; maxx/=10; } } 15.4 INSERTION SORT Insertion sort may be a simple algorithm that works almost like the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the right position within the sorted part. To sort an array of size n in ascending order: 1: Iterate from arr[1] to arr[n] over the array. 2: Compare the present element (key) to its predecessor. 3: If the key element is smaller than its predecessor, compare it to the weather before. Move the greater elements one position up to form space for the swapped element. 229 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 15.3: Insertion Sort Iteration Algorithm: procedure insertionSort( A : array of items ) int holePos // holePosition int valueToInsert for i = 1 to length(A) inclusive do: /* select value to be inserted */ valueToInsert = A[i] holePos = i /*locate hole position for the element to be inserted while holePos >0 & A[holePos -1] > valueToInsert do: A[holePos] = A[holePos -1] holePos = holePos -1 230 CU IDOL SELF LEARNING MATERIAL (SLM)

end while /* insert the number at hole position */ A[holePos] = valueToInsert end for end procedure Example Program: void insertionSort(int arr[], int n) { int i, key, j; for (i = 1; i < n; i++) { key = arr[i]; j = i - 1; /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */ while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } 15.5 MERGE SORT Merge Sort is one among the foremost popular sorting algorithms that's supported the principle of the Divide and Conquer Algorithm. Here, a drag is split into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to make the ultimate solution. 231 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 15.4: Merge Sort Iteration Divide and Conquer Strategy: Using the Divide and Conquer technique, we divide a drag into subproblems. When the answer to every subproblem is prepared, we 'combine' the results from the subproblems to unravel the most problem. Suppose we had to sort an array A. A subproblem would be to sort a sub-section of this array starting at index p and ending at index r, denoted as A[p..r]. Divide 232 CU IDOL SELF LEARNING MATERIAL (SLM)

If q is that the half-way point between p and r, then we will split the subarray A[p..r] into two arrays A[p..q] and A[q+1, r]. Conquer In the conquer step, we attempt to sort both the subarrays A[p..q] and A[q+1, r]. If we've not yet reached the bottom case, we again divide both these subarrays and check out to sort them. Combine When the conquer step reaches the bottom step and that we get two sorted subarrays A[p..q] and A[q+1, r] for array A[p..r], we combine the results by creating a sorted array A[p..r] from two sorted subarrays A[p..q] and A[q+1, r]. MergeSort Algorithm MergeSort(A, p, r): if p > r return q = (p+r)/2 mergeSort(A, p, q) mergeSort(A, q+1, r) merge(A, p, q, r) Example Program: 233 void mergeSort(int arr[], int l, int r) { if (l < r) { // Finding mid element int m = l+(r-l)/2; // Recursively sorting both the halves mergeSort(arr, l, m); mergeSort(arr, m+1, r); // Merge the array merge(arr, l, m, r); CU IDOL SELF LEARNING MATERIAL (SLM)

} } 15.6 SUMMARY • Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. The order can be ascending or descending. • Selection sort is an algorithm that selects the smallest element from an unsorted list in each iteration and places that element at the beginning of the unsorted list. • Radix sort is a sorting technique that sorts the elements by first grouping the individual digits of the same place value. Then, sort the elements according to their increasing/decreasing order • Insertion operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end or any given index of the array. Here, we see a practical implementation of insertion operation, where we add data at the end of the array. • Merge Sort the elements are divided into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to form the final solution. 15.7 KEYWORDS • Bubble sort: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. • Selection sort: The selection sort algorithm sorts an array by repeatedly finding the minimum element from the unsorted part and putting it at the beginning • Radix sort: Radix sort is an integer sorting algorithm that sorts data with integer keys by grouping the keys by individual digits that share the same significant position and value. • Insertion sort: insertion sort is one of the simplest algorithms and it consists of N-1 passes. • Merge sort: merge sort runs in ������(������ log ������) worse-case running time and the number of comparisons used is nearly optimal. 15.8 LEARNING ACTIVITY You have to sort an array of student records by social security number. Write a program to do this, using radix sort with 100 buckets and three passes. 234 CU IDOL SELF LEARNING MATERIAL (SLM)

___________________________________________________________________________ ____________________________________________________________________ 15.9 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Write short notes on bubble sort. 2. What are Sorting and its types in data structure? 3. What is the slowest sorting algorithm? 4. Define merge sort? 5. List the characteristics of merge sort. Long Questions 1. Explain radix sort. 2. Explain the merge sort algorithm. 3. Write algorithm for selection sort. 4. How does insertion sort algorithm work? 5. Write an algorithm to sort the specified array int[] input = { 4, 1, 2, 7, 10, 1, 2, 4, 4, 7, 1, 2, 1, 10, 1, 2, 4, 1, 2, 7, 10, 1, 2}; B. Multiple choice Questions 1. What is the average case complexity of bubble sort? a. O(nlogn) b. O(logn) c. O(n) d. O(n2) 2. Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case of sorted elements? a. It is faster b. Consumes less memory c. Detects whether the input is already sorted d. Consumes less time 235 CU IDOL SELF LEARNING MATERIAL (SLM)

3. The given array is arr = {1, 2, 4, 3}. Bubble sort is used to sort the array elements. How many iterations will be done to sort the array? a. 4 b. 2 c. 1 d. 0 4. Merge sort uses which of the following technique to implement sorting? a. backtracking b. greedy algorithm c. divide and conquer d. dynamic programming 5. Which of the following is the distribution sort? a. Heap sort b. Smooth sort c. Quick sort d. radix sort Answer 1.(d) 2. (c) 3.(a) 4.(c) 5.(d) 15.10 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ 236 CU IDOL SELF LEARNING MATERIAL (SLM)

• https://www.tutorialspoint.com/ 237 CU IDOL SELF LEARNING MATERIAL (SLM)