SPARK ICP 2 - Apoorvag2597/BDP_Revised GitHub Wiki

Name : Apoorva Geetanjali Avadhanula

Class id : 34

1.Merge sort:

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves until each and every individual element is split as an equal half , calls itself for the two halves and then merges the two sorted halves.

We are going to provide the following input as an array to perform the Merge sort on it.

We are going to provide two functions to finish the job, one is the mergesort() It divides the arrays into halves and sends them for sorting in a recursive method.

And the next function merge() is used for sorting the elements in the arrays and merging 2 arrays and sorting them back.

Program -

Output:

2.Breadth First Search (BFS) Algorithm. Here a graph is given in the form of lists.The nodes are marked as visited, if we visit that node. So that way we dont keep visiting the node which we already visited. We define a function BFS is defined with several parameters - starting vertex as well as the entire graph. BFS0 is defined with elements of each list as well a visited list containing the vertices that are already visited. FilterNot() function is used to unfilter all the visited nodes. If the adjacent space is empty, it assumes that to be a node which is already visited.

Program -

Output -

3. Depth First Search It is similar to Depth First Traversal. But instead of a tree we are going to perform it in graphs.

In order to avoid loops, We are marking the nodes after they have been visited for the first time.

By this we can stay away from travelling to node that has already been visited.

When we have reached a dead end it travels back to the previous node to check if any other nodes have been left unvisited.

After all the nodes are traveled we are getting the output in the order of nodes we have visited one by one.

We are going to give inputs of the graph in the form of lists. Each list consists the neighboring nodes.

filternot():

The filterNot() method is utilized to select all elements of the list which does not satisfies a stated predicate.

Program -

Output: