## Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

### Binary Search Tree in Java

`public class BinarySearchTree<Key extends Comparable<Key>, Value> {    Node<Key, Value> root;    public void addNode(Key key, Value val) {        addNode(this.root, key, val);    }    public Node addNode(Node<Key, Value> node, Key key, Value value) {        if (node == null) {            Node<Key, Value> nodeTemp = new Node<Key, Value>(key, value);            if (this.root == null) {                this.root = nodeTemp;            }            return nodeTemp;        }        int compareTo = key.compareTo((Key) node.keyT);        if (compareTo < 0) {            node.left = addNode(node.left, key, value);        } else if (compareTo > 0) {            node.right = addNode(node.right, key, value);        } else {            node.keyT = key;            node.value = value;        }        return node;    }    Node<Key, Value> getNode(Key key) {        Node<Key, Value> node = this.root;        while (node != null) {            int cmp = key.compareTo((Key) node.keyT);            if (cmp < 0) {                node = node.left;            } else if (cmp > 0) {                node = node.right;            } else if (cmp == 0) {                return node;            }        }        return null;    }    private static void printInOrder(Node<Integer, String> node) {        if (node == null) {            return;        }        printInOrder(node.left);        System.out.println(node.value);        printInOrder(node.right);    }    /**     * @param args     */    public static void main(String[] args) {        BinarySearchTree<Integer, String> bst = new BinarySearchTree<Integer, String>();        bst.addNode(new Integer(7), "seven");        bst.addNode(new Integer(8), "eight");        bst.addNode(new Integer(9), "nine");        bst.addNode(new Integer(5), "five");        bst.addNode(new Integer(6), "six");        bst.addNode(new Integer(4), "four");        bst.addNode(new Integer(3), "three");        bst.addNode(new Integer(10), "ten");        bst.addNode(new Integer(2), "two");        bst.addNode(new Integer(1), "one");        printInOrder(bst.root);    }}class Node<T extends Comparable<T>, Value> {    T keyT;    Value value;    Node<T, Value> left;    Node<T, Value> right;    Node(T key, Value val) {        this.keyT = key;        this.value = val;    }}`

### Quick Sort in Java

` private static void quickSort(Integer[] toSortArray, int low, int high) {        if (low >= high)            return;        int k = partition(toSortArray, low, high);        quickSort(toSortArray, low, k - 1);        quickSort(toSortArray, k + 1, high);    }    /**     * given a number index low, it partitions array      * such that all numbers less than numbers[]low] are left     * and greater are right     * @param numbers     * @param low     * @param high     * @return     */    private static int partition(Integer[] numbers, int low, int high) {        int leftIndex = low;        int rightIndex = high + 1;        while (true) {                        //find left index to swap            while (numbers[++leftIndex] < numbers[low]) {                if (leftIndex == high) {                    break;                }            }            //find right index to swap            while (numbers[low] < numbers[--rightIndex]) {                if (rightIndex == low) {                    break;                }            }            // pointers cross            if (leftIndex >= rightIndex)                break;            //swap            swap(leftIndex, rightIndex, numbers);        }        swap(low, rightIndex, numbers);        return rightIndex;    }    private static void printArray(Integer[] toSortArray) {        for (int i = 0; i < toSortArray.length; i++) {            System.out.print(toSortArray[i] + " ");        }        System.out.println(" ");    }    /**     * swap 2 numbers at the index     *      * @param minIndex     * @param index     * @param numbers     */    private static void swap(int minIndex, int index, Integer[] numbers) {        Integer temp = numbers[minIndex];        numbers[minIndex] = numbers[index];        numbers[index] = temp;    }`

### Merge Sort in Java

`  private static void sortList(Integer[] toSortArray) {        Integer[] sortedArray = new Integer[toSortArray.length];        mergeSortList(toSortArray, sortedArray, 0, toSortArray.length - 1);    }    private static void mergeSortList(Integer[] toSortArray, Integer[] sortedArray, int low, int high) {        if (low >= high)            return;        int mid = (high + low) / 2;        mergeSortList(toSortArray, sortedArray, low, mid);        mergeSortList(toSortArray, sortedArray, mid + 1, high);        mergeResults(toSortArray, sortedArray, low, mid, high);        printArray(toSortArray);    }    private static void mergeResults(Integer[] toSortArray, Integer[] sortedArray, int low, int mid, int high) {        for (int index = low; index <= high; index++) {            sortedArray[index] = toSortArray[index];        }        int leftIndex = low;        int rightIndex = mid + 1;        for (int k = low; k <= high; k++) {            System.out.println(leftIndex + " " + rightIndex + " " + k);            if (leftIndex > mid) {                toSortArray[k] = sortedArray[rightIndex++];            } else if (rightIndex > high) {                toSortArray[k] = sortedArray[leftIndex++];            } else if (sortedArray[leftIndex] < sortedArray[rightIndex]) {                toSortArray[k] = sortedArray[leftIndex++];            } else {                toSortArray[k] = sortedArray[rightIndex++];            }        }    }`

Time Complexity: n log n

### Insertion Sort in Java

Before Sorting, Input :0 10 2 9 3 8 1 6 5 7 4   the first element is sorted here
0 10 2 9 3 8 1 6 5 7 4    first 2 elements are sorted
0 2 10 9 3 8 1 6 5 7 4   and so on….
0 2 9 10 3 8 1 6 5 7 4
0 2 3 9 10 8 1 6 5 7 4
0 2 3 8 9 10 1 6 5 7 4
0 1 2 3 8 9 10 6 5 7 4
0 1 2 3 6 8 9 10 5 7 4
0 1 2 3 5 6 8 9 10 7 4
0 1 2 3 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9 10
After Sorting, output :
0 1 2 3 4 5 6 7 8 9 10

` /**     * every element before the index is sorted. so select the number at the     * index location and put it in appropriate position     *      * @param numbers     */    private static void sortList(Integer[] numbers) {        for (int index = 0; index < numbers.length; index++) {            for (int sortIndex = index; sortIndex > 0; sortIndex--) {                if (numbers[sortIndex] < numbers[sortIndex - 1]) {                    swap(sortIndex, sortIndex - 1, numbers);                } else {                    break;                }            }            printArray(numbers);        }    }    /**     * swap 2 numbers at the index     *      * @param indexOne     * @param indexTwo     * @param numbers     */    private static void swap(int indexOne, int indexTwo, Integer[] numbers) {        Integer temp = numbers[indexOne];        numbers[indexOne] = numbers[indexTwo];        numbers[indexTwo] = temp;    }`

### Selection Sort in Java

• Find the smallest entry for an Index
• Swap it with the index element do this iteratively till the end of the array

Complexity: (n power 2)/2  comparisions & n exchanges

`  /**     * find the minimum in the series and swap it to the index      * @param numbers     */    private static void sortList(Integer[] numbers) {        for (int index = 0; index < numbers.length; index++) {            int minIndex = findMininRest(index, numbers);            if (minIndex != index) {                swap(minIndex, index, numbers);                printArray(numbers);            }        }    }    /**     * swap 2 numbers at the index      * @param minIndex     * @param index     * @param numbers     */    private static void swap(int minIndex, int index, Integer[] numbers) {        Integer temp = numbers[minIndex];        numbers[minIndex] = numbers[index];        numbers[index] = temp;    }    /**     * find the minimum in the rest of the series     *      * @param index     *            the current index to fill     * @param numbers     *            all the numbers     * @return returns the index of the minimum element in the rest series from     *         index     */    private static int findMininRest(int index, Integer[] numbers) {        int currentMin = index;        for (int restIndex = index + 1; restIndex < numbers.length; restIndex++) {            if (numbers[currentMin] > numbers[restIndex]) {                currentMin = restIndex;            }        }        return currentMin;    }`

Trace of the sort per Iteration

0 10 2 9 3 8 1 6 5 7 4 INPUT

0 1 2 9 3 8 10 6 5 7 4
0 1 2 3 9 8 10 6 5 7 4
0 1 2 3 4 8 10 6 5 7 9
0 1 2 3 4 5 10 6 8 7 9
0 1 2 3 4 5 6 10 8 7 9
0 1 2 3 4 5 6 7 8 10 9

0 1 2 3 4 5 6 7 8 9 10 OUTPUT

### Recursively print Permutations of a String

`        recursivelyReverse("", "helloWorld");       private static void recursivelyReverse(String first, String second) {        if (second.length() == 0) {            System.out.println(first);            return;        }        for (int index = 0; index < second.length(); index++) {            recursivelyReverse(first + second.charAt(index), second.substring(0, index) + second.substring(index + 1));        }    }`

### Recursively reverse a linked list

`private static Node recurReverseLinkedList(Node firstNode) {        if (firstNode == null || firstNode.next == null) {            return firstNode;        }                Node secondNode = firstNode.next; // the new head node to be reversed        firstNode.next = null; // de-link the node from the list        Node previousFirstNode = recurReverseLinkedList(secondNode); //reverse rest        secondNode.next = firstNode; //the second node next will be first node        return previousFirstNode;     }`

### Recursive Sum of Linked list node values

`   private static int recursiveSum(Node head) {        //base case        if (head.next == null) {            return head.value;        }        //general case        return head.value + recursiveSum(head.next);    }`

`    private static void reverseLinkedList(MyLinkedList linkedList) {        Node current = linkedList.head;        Node previous = null;        Node next = null;        while (current != null) {            next = current.next;            current.next = previous;            previous = current;            current = next;        }        linkedList.head = previous;    }`
`    private static int factorial(int i) {        // base case        if (i == 0 || i == 1) {            return 1;        } else { // general case            return i * factorial(i - 1);        }    }`
` `