Algorithm: Depth First Search in Java

Graph as you must be aware is used to represent network. Network could be of any type:

1. Your friends network
2. Your work Network
3. Communication Network
4. Commute Network

As every network has nodes (src and destination) and we may have a way to reach from one to another (edge of the network).

Depth First Search as name suggest, will try to reach the last reachable node first then it retrace back and go again deep, so basically searching across the depth of each node.

for below graph breadth first search will go in below order, if our root node is 3.

3 -> 4 -> 0 -> 1 -> 2 -> 5

For the graph creation please visit:

https://maddy4java.blogspot.com/2019/11/algorithm-graph-representation.html

And for complete code: Github link

package madwani.sushil.Graph;
import madwani.sushil.model.Graph;
import madwani.sushil.model.Node;
import madwani.sushil.service.GraphService;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class DFS {

    List<Node> nodes = new ArrayList<>();
    // to keep track of nodes which are visited
    HashMap<Node, Boolean> visited = new HashMap<>();
    public void dfs(Graph g){

        if(g.getAdjacencyMap() !=null) {

            // read all the nodes
            nodes = new ArrayList<>(g.getAdjacencyMap().keySet());
            // initialize all nodes as false for visited
            initializeVisited();
            // actual algo
            // root node to start the bfs, push to queue
            Node root = new Node(1,"zero");
            doDfs(g, root);
        }
    }

    private void doDfs(Graph g, Node root) {

       // mark node as visited
        visited.put(root, true);
        // print for visibility
        System.out.print(root.getN() + " -> ");
        // for each node visit adjacent and do the above recursively
        for (Node n : g.getAdjacencyMap().get(root)) {
            if(!visited.containsKey(n) || !visited.get(n)){
                doDfs(g,n);
            }
        }

    }

    public void initializeVisited() {
        for(Node n: nodes) {
            visited.put(n, false);
        }
    }

    public static void main(String[] args) {
        GraphService service = new GraphService();
        List<Graph> graphs = service.getSampleGraphs();
        DFS dfs = new DFS();
        dfs.dfs(graphs.get(0));
    }

}

Algorithm: Breadth First Search (BFS)

Graph as you must be aware is used to represent network. Network could be of any type:

1. Your friends network
2. Your work Network
3. Communication Network
4. Commute Network

As every network has nodes (src and destination) and we may have a way to reach from one to another (edge of the network).

Breadth First Search as name suggest, will try to reach neighbors first then only it will move ahead, so basically searching across the breadth of a node and then going deep.

for below graph breadth first search will go in below order, if our root node is 3.

3   4   0   1   2   5

For the graph creation please visit:

https://maddy4java.blogspot.com/2019/11/algorithm-graph-representation.html

And for complete code: Github link

package madwani.sushil.Graph;
import madwani.sushil.model.Graph;
import madwani.sushil.model.Node;
import madwani.sushil.service.GraphService;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

public class BFS {

    List<Node> nodes = new ArrayList<>();
    // to keep track of neighboring node
    Queue<Node> nodeQueue = new ArrayBlockingQueue<>(200);
    // to keep track of nodes which are visited
    HashMap<Node, Boolean> visited = new HashMap<>();
    public void bfs(Graph g){

        if(g.getAdjacencyMap() !=null) {

            // read all the nodes
            nodes = new ArrayList<>(g.getAdjacencyMap().keySet());

            // initialize all nodes as false for visited
            initializeVisited();

            //actual algo
            doBfs(g);
        }
    }

    public void doBfs(Graph g){

        // root node to start the bfs, push to queue
        nodeQueue.add(new Node(3,"three"));

        // poll the queue and run algo till queue is empty
        do {

            Node initialNode = nodeQueue.poll();
            // get all the adjacent nodes of the polled node
            LinkedList<Node> adjacentNodes = g.getAdjacencyMap().get(initialNode) == null ?
                    new LinkedList<>():g.getAdjacencyMap().get(initialNode);

            // if not visited, get all adjacent nodes
            // print it for visibility purpose
            // mark it visited
            if(!visited.containsKey(initialNode) || !visited.get(initialNode)) {
                for (Node node: adjacentNodes){
                    nodeQueue.add(node);
                }
                System.out.print(initialNode.getN() + "   ");
                visited.put(initialNode, true);
            }
        } while (!nodeQueue.isEmpty());
    }


    public void initializeVisited() {
        for(Node n: nodes) {
            visited.put(n, false);
        }
    }

    public static void main(String[] args) {
        GraphService service = new GraphService();
        List<Graph> graphs = service.getSampleGraphs();
        BFS bfs = new BFS();
        bfs.bfs(graphs.get(0));
    }
}

Algorithm: Merge Sort

Merge Sort is again a way to sort array of elements. It is same as quick sort with small difference.

It works on Divide and Conquer algorithm.

It recursively divide array in 2 parts and once division reached the smallest unit, start merging the left and right arrays of middle elements in sorted way.

So basically while merging back the elements it does the comparison, that's the reason it is called merge sort.

Few Points:

1. It sorts using merging so it require extra space equivalent to the size of input array to keep elements temporary for merging. so its space complexity is O(n)
2. It always divides array in 2 parts using middle element.
3. Its worst and best case time complexity is O(nlogn).

package madwani.sushil.sorting;

import madwani.sushil.Util;

public class MergeSort {

    public static void main(String[] args) {

        String input = Util.readLine();

        int[] elements = Util.convertLineToIntArray(input);

        mergesort(elements, 0, elements.length-1);

        Util.print1dArray(elements);
    }

    public static void mergesort(int[] arr, int start, int end) {

        if(start < end) {

            int middle = ( start + end ) /2;

            mergesort(arr, start, middle);

            mergesort(arr, middle + 1, end);

            merge(arr, start, end, middle);

        }
    }

    private static void merge(int[] arr, int start, int end, int middle) {

        // left array size to keep left side elements

        int leftArrayLength = middle - start + 1;

        // right array size to keep right side elements
        int rightArrayLength = end - middle;

        int[] tempLeft = new int[leftArrayLength];

        int[] tempRight = new int[rightArrayLength];

        // temporary populate temp left array with left elements

        for ( int i =0; i< leftArrayLength ;i++) {
            tempLeft[i] = arr[start + i];

        }        // temporary populate temp right array with right elements

        for ( int i =0; i< rightArrayLength ;i++) {

            tempRight[i] = arr[middle + i + 1 ];
        }

        //lets actual merge start

        // i for left array
        // j for right array
        // k for merged array

        int i = 0, j = 0, k = start;

        while(i < leftArrayLength && j < rightArrayLength ) {

            // if left element is lesser than right element

            if(tempLeft[i] <= tempRight[j]) {
                arr[k] = tempLeft[i];
                i++;
            } else{
                // if right element is lesser than left element
                arr[k] = tempRight[j];
                j++;
            }
            k++;]
        }

        // populate remaining left element 

        while(i< leftArrayLength) {

            arr[k] = tempLeft[i];
            k++;i++;
        }

        // populate remaining right element 

        while(j< rightArrayLength) {
            arr[k] = tempRight[j];

            k++;j++;
        }
    }
}

Algorithms: QuickSort

Quicksort as name suggests is the one of the quick technique to sort array of elements.

Now Question is, is it the best one ? No, not at all, we have many other sorting algorithms better than it.

Still you should have a very good understanding of Quicksort.

Quicksort works on the Divide and Conquer strategy. 

It divides the whole array around an element of the array (we will call it Pivot), and try to arrange the elements in such a way that elements to the left of the array are smaller than it (might not be sorted) and elements to the right of Pivot are all greater than it    (might not be sorted).

Once you finish this activity, you are sure that the Pivot element is at the right position in the array.

Do the same to the left and right subarrays around the Pivot element recursively and you are done.

Just before moving to the code:
1. I have explained every step as comments in the code, so please read process in code only.

2. We can select any element as Pivot, it could be 1st element, last element or middle or any random. generally I choose middle, however it is not the most efficient.

3. When we write any recursive method we always have to think before hand when to break the recursion, so have this in mind.

4. Best case time complexity is O(nlogn)

5. Worst case time complexity is O(n*n) in case of worst choice of pivot or already sorted.

6. in Java 8, Quicksort is used for primitive elements array, however Mergesort is used for Objects array.

Github link

lets write some code:

package madwani.sushil.sorting;

import madwani.sushil.Util;

public class QuickSort {

    public static void main(String[] args) {

        String input = Util.readLine();

        int[] elements = Util.convertLineToIntArray(input);

        quicksort(elements, 0, elements.length-1);

        Util.print1dArray(elements);

    }

    public static void quicksort(int[] arr, int start, int end) {

        // basic check to ensure corner case

        if (arr == null || arr.length == 0) {

            return;

        }

        // condition to break recursion

        if (start >= end) {

            return;

        }

        // I always chose middle element as Pivot

        int middle = start + (end - start) / 2;

        // Pivot element

        int pivot = arr[middle];

        // lets start the real sorting

        int i = start, j = end;

        // do comparison and swapping till start and end have not met

        while (i <= j) {

            // increment till left side elements are lesser or equal to pivot

            while (arr[i] <= pivot) {

                i++;

            }

            // decrement till right side elements are greater to pivot

            while (arr[j] > pivot) {

                j--;

            }

            // swap elements from left right only when indices haven't crossed each other

            // after swap always increase lower index and decrease higher index

            if (i <= j) {

                Util.swapElementsInArray(arr, i, j);

                i++;

                j--;

            }

        }

        // one pass is done, so we have 2 boundaries
        // lower boundary: i which was moving towards end
        // upper boundary: j which was moving towards start



        // if i has not reached and crossed the end lets do one more pass from i to end
        // this is left subarray

        if (end > i) {
            quicksort(arr, i, end);
        }

        // if j has not reached the start and crossed, lets do one more pass from start to j
        // this is right subarray

        if (start < j) {
            quicksort(arr, start, j);
        }
    }
}