Euclid's Algorithm for Calculating GCD of two Integers [Java Implementation]

Tutorial on the Algorithm : http://www.rit.edu/~w-asc/documents/services/resources/handouts/DM%20-%206%20Euclidean%20Algorithm.pdf

Source:

public class EuclidGCD {
    public static int findGCD(int a, int b){  
        if(a==0)return b;
        if(b==0)return a;
        
        if(a<0)a=-a;
        if(b<0)b=-b;
        
        int min = Math.min(a, b);
        int max = a;
        if(min==a)max = b;
       
        int t, rem = t = min;
        
        while(t!=0){
            rem = t;
            t = max%min; 
            max = min;
            min = t; 
        }
        return rem;
    }
    
    public static void main(String[] args) throws Exception{ 
        System.out.println(findGCD(4278, 8602));
    } 
}

Output:

46

Quick Sort With Minor Improvements

Improvements:

1. Setting the element with index hi (the pivot element) equal to the median of the three elements lo, hi and (lo+hi) / 2 so that the probability that it lies in between the values is more.

2. Using the faster Insertion sort if the number of elements in the sub array is less than some predefined value (the value 5 is used here).

Source:

package QuickSort;

import java.util.Arrays;

public class QuickSort {

    public static void quickSort(int array[]) {
        quickSorter(array, 0, array.length - 1);
    }

    public static void quickSorter(int array[], int lo, int hi) {
        if (lo > hi) {
            return;
        }

        //If array size is less than 5, we will use Insertion Sort
        if (hi - lo <= 5) { 
            InsertionSort.insertionSort(array, lo, hi);
            return;
        }

        int m = median(array, lo, (lo + hi) / 2, hi); 
        swap(array, m, hi);

        int partition = partition(array, lo, hi);
        quickSorter(array, lo, partition - 1);
        quickSorter(array, partition + 1, hi);
    }

    private static int partition(int array[], int lo, int hi) {
        int partitionIndex = lo;

        for (int i = lo; i < hi; ++i) {
            if (array[i] < array[hi]) {
                swap(array, partitionIndex, i);
                partitionIndex++;
            }
        }
        swap(array, partitionIndex, hi);
        return partitionIndex;
    }

    public static int median(int[] x, int a, int b, int c) {
        if (x[a] > x[b] && x[a] > x[c]) { if (x[b] > x[c]) return b; else return c; }
        else if (x[b] > x[a] && x[b] > x[c]) { if (x[a] > x[c]) return a; else return c; } 
        else if (x[c] > x[a] && x[c] > x[b]) { if (x[a] > x[b]) return a; }
        return b;
    }

    public static void swap(int array[], int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 3, 2, 1, 3, 44, 21, 3, 2, 33, 12, 123};
        quickSort(array);
        System.out.println(Arrays.toString(array));
    }
}

class InsertionSort {

    public static void insertionSort(int[] a, int lo, int hi) {
        for (int i = lo + 1; i <= hi; ++i) {
            int j = i;
            while (a[j] < a[j - 1]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
                if (--j == 0) {
                    break;
                }
            }
        }
    }
}

Output:

[1, 2, 2, 3, 3, 3, 3, 4, 12, 21, 33, 44, 123]

Bottom Up Merge Sort Java Implementation

Bottom up merge sort sorts the array without using recursion. It is 10% slower than the top down (recursive) mergesort. The idea is to start sorting the array elements from the start in groups of 2, 4, 8, 16, and so on (powers of two). So that the effect is the same as the recursive algorithm.
Here is a trace for sorting numbers 13,12, ..., 1

 

Source:

import java.util.Arrays;

public class BottomUpMergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; 
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
        System.out.println(Arrays.toString(orig));
        System.out.println("start = "+start+" mid = "+mid+" end = "+end);
        System.out.println(Arrays.toString(aux)+"\n");
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        int N = orig.length;
        for (int sz = 1; sz < N; sz *= 2) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(orig, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N-1));
            }
        }
    }

    public static void main(String[] args) {
        int array[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }
}

lo < N - sz 
takes care to see that the mid value falls before end. 

lo < N - sz
lo + sz < N
lo + sz - 1 < N - 1
mid < N - 1

Math.min() takes care to see that end does not extend beyond the last index.

Output:

[11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 0 mid = 0 end = 1
[10, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 2 mid = 2 end = 3
[10, 11, 8, 9, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 7, 6, 5, 4, 3, 2, 1]
start = 4 mid = 4 end = 5
[10, 11, 8, 9, 6, 7, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 1]
start = 6 mid = 6 end = 7
[10, 11, 8, 9, 6, 7, 4, 5, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 3, 2, 1]
start = 8 mid = 8 end = 9
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1]
start = 0 mid = 1 end = 3
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 0]
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 1]
start = 4 mid = 5 end = 7
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 0]
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 1]
start = 8 mid = 9 end = 10
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
start = 0 mid = 3 end = 7
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
start = 0 mid = 7 end = 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Merge Sort Implementation with minor Improvements [Java]

Here is the basic merge sort algorithm implementation to which we will be adding some improvements:

Source: 

import java.util.Arrays;
 
public class MergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start;  
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while (j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while (i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }   
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        sort(orig, aux, start, mid); 
        sort(orig, aux, mid + 1, end); 
        merge(orig, aux, start, mid, end);
    }

    public static void main(String[] args) {
        int array[] = {5, 4, 3, 2, 1};
        int aux[] = new int[array.length]; 
        sort(array, aux, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

Improvements that we can add:

1. Skip merge procedure if the elements in the two sorted halves to merge are already in ascending order (i.e. if firstHalf's end element <= secondHalf's first element so no merge is needed at all).
2. We can avoid copying back from auxiliary array every time merge is called by interchanging the roles of original array and auxiliary array during recursion. (The final result will be stored in the auxiliary array.)

Source: 

import java.util.Arrays;

public class MergeSort2 {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; //Point #1
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        sort(aux, orig, start, mid);        //Point #2
        sort(aux, orig, mid + 1, end);      
        merge(orig, aux, start, mid, end);
    }

    public static void main(String[] args) {
        int array[] = {5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        System.arraycopy(array, 0, aux, 0, array.length);  //Be careful, both arrays must be the same initially!
        sort(array, aux, 0, array.length-1);
        System.out.println(Arrays.toString(aux));
    }
}

Red Black Tree Java Implementation

This program implements Red Black Tree in Java.

Red Black Tree Visualizer (Helps a lot) : http://www.cs.usfca.edu/~galles/visualization/RedBlack.html

[Note: The delete operation used in this source finds the min element in the right child of the node to be deleted (the node having two children) but the link above uses the min element from the left subtree in that case. So delete operations will be different. Both are correct.]
 
There are 5 basic properties a red-black tree must statisfy:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (nil) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the
same number of black nodes.

Here is a random Red Black Tree so you can visualize the structure of a Red Black Tree:

The leaf nodes have both left and right references set to node nil. The root has it's parent node set to node nil as well.

Source:

import java.util.Scanner;

public class RedBlackTree {

    private final int RED = 0;
    private final int BLACK = 1;

    private class Node {

        int key = -1, color = BLACK;
        Node left = nil, right = nil, parent = nil;

        Node(int key) {
            this.key = key;
        } 
    }

    private final Node nil = new Node(-1); 
    private Node root = nil;

    public void printTree(Node node) {
        if (node == nil) {
            return;
        }
        printTree(node.left);
        System.out.print(((node.color==RED)?"Color: Red ":"Color: Black ")+"Key: "+node.key+" Parent: "+node.parent.key+"\n");
        printTree(node.right);
    }

    private Node findNode(Node findNode, Node node) {
        if (root == nil) {
            return null;
        }

        if (findNode.key < node.key) {
            if (node.left != nil) {
                return findNode(findNode, node.left);
            }
        } else if (findNode.key > node.key) {
            if (node.right != nil) {
                return findNode(findNode, node.right);
            }
        } else if (findNode.key == node.key) {
            return node;
        }
        return null;
    }

    private void insert(Node node) {
        Node temp = root;
        if (root == nil) {
            root = node;
            node.color = BLACK;
            node.parent = nil;
        } else {
            node.color = RED;
            while (true) {
                if (node.key < temp.key) {
                    if (temp.left == nil) {
                        temp.left = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.left;
                    }
                } else if (node.key >= temp.key) {
                    if (temp.right == nil) {
                        temp.right = node;
                        node.parent = temp;
                        break;
                    } else {
                        temp = temp.right;
                    }
                }
            }
            fixTree(node);
        }
    }

    //Takes as argument the newly inserted node
    private void fixTree(Node node) {
        while (node.parent.color == RED) {
            Node uncle = nil;
            if (node.parent == node.parent.parent.left) {
                uncle = node.parent.parent.right;

                if (uncle != nil && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                    continue;
                } 
                if (node == node.parent.right) {
                    //Double rotation needed
                    node = node.parent;
                    rotateLeft(node);
                } 
                node.parent.color = BLACK;
                node.parent.parent.color = RED;
                //if the "else if" code hasn't executed, this
                //is a case where we only need a single rotation 
                rotateRight(node.parent.parent);
            } else {
                uncle = node.parent.parent.left;
                 if (uncle != nil && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                    continue;
                }
                if (node == node.parent.left) {
                    //Double rotation needed
                    node = node.parent;
                    rotateRight(node);
                }
                node.parent.color = BLACK;
                node.parent.parent.color = RED;
                //if the "else if" code hasn't executed, this
                //is a case where we only need a single rotation
                rotateLeft(node.parent.parent);
            }
        }
        root.color = BLACK;
    }

    void rotateLeft(Node node) {
        if (node.parent != nil) {
            if (node == node.parent.left) {
                node.parent.left = node.right;
            } else {
                node.parent.right = node.right;
            }
            node.right.parent = node.parent;
            node.parent = node.right;
            if (node.right.left != nil) {
                node.right.left.parent = node;
            }
            node.right = node.right.left;
            node.parent.left = node;
        } else {//Need to rotate root
            Node right = root.right;
            root.right = right.left;
            right.left.parent = root;
            root.parent = right;
            right.left = root;
            right.parent = nil;
            root = right;
        }
    }

    void rotateRight(Node node) {
        if (node.parent != nil) {
            if (node == node.parent.left) {
                node.parent.left = node.left;
            } else {
                node.parent.right = node.left;
            }

            node.left.parent = node.parent;
            node.parent = node.left;
            if (node.left.right != nil) {
                node.left.right.parent = node;
            }
            node.left = node.left.right;
            node.parent.right = node;
        } else {//Need to rotate root
            Node left = root.left;
            root.left = root.left.right;
            left.right.parent = root;
            root.parent = left;
            left.right = root;
            left.parent = nil;
            root = left;
        }
    }

    //Deletes whole tree
    void deleteTree(){
        root = nil;
    }
    
    //Deletion Code .
    
    //This operation doesn't care about the new Node's connections
    //with previous node's left and right. The caller has to take care
    //of that.
    void transplant(Node target, Node with){ 
          if(target.parent == nil){
              root = with;
          }else if(target == target.parent.left){
              target.parent.left = with;
          }else
              target.parent.right = with;
          with.parent = target.parent;
    }
    
    boolean delete(Node z){
        if((z = findNode(z, root))==null)return false;
        Node x;
        Node y = z; // temporary reference y
        int y_original_color = y.color;
        
        if(z.left == nil){
            x = z.right;  
            transplant(z, z.right);  
        }else if(z.right == nil){
            x = z.left;
            transplant(z, z.left); 
        }else{
            y = treeMinimum(z.right);
            y_original_color = y.color;
            x = y.right;
            if(y.parent == z)
                x.parent = y;
            else{
                transplant(y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }
            transplant(z, y);
            y.left = z.left;
            y.left.parent = y;
            y.color = z.color; 
        }
        if(y_original_color==BLACK)
            deleteFixup(x);  
        return true;
    }
    
    void deleteFixup(Node x){
        while(x!=root && x.color == BLACK){ 
            if(x == x.parent.left){
                Node w = x.parent.right;
                if(w.color == RED){
                    w.color = BLACK;
                    x.parent.color = RED;
                    rotateLeft(x.parent);
                    w = x.parent.right;
                }
                if(w.left.color == BLACK && w.right.color == BLACK){
                    w.color = RED;
                    x = x.parent;
                    continue;
                }
                else if(w.right.color == BLACK){
                    w.left.color = BLACK;
                    w.color = RED;
                    rotateRight(w);
                    w = x.parent.right;
                }
                if(w.right.color == RED){
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.right.color = BLACK;
                    rotateLeft(x.parent);
                    x = root;
                }
            }else{
                Node w = x.parent.left;
                if(w.color == RED){
                    w.color = BLACK;
                    x.parent.color = RED;
                    rotateRight(x.parent);
                    w = x.parent.left;
                }
                if(w.right.color == BLACK && w.left.color == BLACK){
                    w.color = RED;
                    x = x.parent;
                    continue;
                }
                else if(w.left.color == BLACK){
                    w.right.color = BLACK;
                    w.color = RED;
                    rotateLeft(w);
                    w = x.parent.left;
                }
                if(w.left.color == RED){
                    w.color = x.parent.color;
                    x.parent.color = BLACK;
                    w.left.color = BLACK;
                    rotateRight(x.parent);
                    x = root;
                }
            }
        }
        x.color = BLACK; 
    }
    
    Node treeMinimum(Node subTreeRoot){
        while(subTreeRoot.left!=nil){
            subTreeRoot = subTreeRoot.left;
        }
        return subTreeRoot;
    }
    
    public void consoleUI() {
        Scanner scan = new Scanner(System.in);
        while (true) {
            System.out.println("\n1.- Add items\n"
                    + "2.- Delete items\n"
                    + "3.- Check items\n"
                    + "4.- Print tree\n"
                    + "5.- Delete tree\n");
            int choice = scan.nextInt();

            int item;
            Node node;
            switch (choice) {
                case 1:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item);
                        insert(node);
                        item = scan.nextInt();
                    }
                    printTree(root);
                    break;
                case 2:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item);
                        System.out.print("\nDeleting item " + item);
                        if (delete(node)) {
                            System.out.print(": deleted!");
                        } else {
                            System.out.print(": does not exist!");
                        }
                        item = scan.nextInt();
                    }
                    System.out.println();
                    printTree(root);
                    break;
                case 3:
                    item = scan.nextInt();
                    while (item != -999) {
                        node = new Node(item);
                        System.out.println((findNode(node, root) != null) ? "found" : "not found");
                        item = scan.nextInt();
                    }
                    break;
                case 4:
                    printTree(root);
                    break;
                case 5:
                    deleteTree();
                    System.out.println("Tree deleted!");
                    break;
            }
        }
    }
    public static void main(String[] args) {
        RedBlackTree rbt = new RedBlackTree();
        rbt.consoleUI();
    }
}

Output Sample [-999 is the (end of input) indicator]:
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree
1
22 33 4 5 6 7 8 55 3 2 1 6 4 -999
Color: Red Key: 1 Parent: 2
Color: Black Key: 2 Parent: 3
Color: Black Key: 3 Parent: 5
Color: Black Key: 4 Parent: 3
Color: Red Key: 4 Parent: 4
Color: Black Key: 5 Parent: -1
Color: Black Key: 6 Parent: 7
Color: Red Key: 6 Parent: 6
Color: Red Key: 7 Parent: 22
Color: Black Key: 8 Parent: 7
Color: Black Key: 22 Parent: 5
Color: Black Key: 33 Parent: 22
Color: Red Key: 55 Parent: 33
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree
2
33 22 5 4 7 6 55 8 2 3 6 1 4 -999
Deleting item 33: deleted!
Deleting item 22: deleted!
Deleting item 5: deleted!
Deleting item 4: deleted!
Deleting item 7: deleted!
Deleting item 6: deleted!
Deleting item 55: deleted!
Deleting item 8: deleted!
Deleting item 2: deleted!
Deleting item 3: deleted!
Deleting item 6: deleted!
Deleting item 1: deleted!
Deleting item 4: deleted!
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree
4
1.- Add items
2.- Delete items
3.- Check items
4.- Print tree
5.- Delete tree

Calculating LCM of N numbers using Euclid's Algorithm

This program calculates the LCM of N numbers using Euclid's method.

Visit here for calculation of LCM using Common Factors Grid Method.

Read about Euclid's method here.

Source: 

public class LCMEuclid {
    
    public static double getGCD(double a, double b){
        double divisor, dividend, remainder = 1; 
         
        if(a>b){dividend = a; divisor = b;}
        else {dividend = b; divisor = a;}
         
        while(true){
            remainder = dividend % divisor;
            dividend = divisor;
            if(remainder==0)break;
            divisor = remainder;
        } 
        return divisor; //GCD - Greatest Common Divisor
    }
    
    public static void main(String[] args){
        double[] array = new double[]{9, 14, 21, 99};
         
        for(int i=0;i<array.length-1;i+=1){
            double GCD = getGCD(array[i], array[i+1]); 
            double product = array[i] * array[i+1];
            double LCM = product/GCD;
            array[i+1] = LCM;
        } 
        System.out.println("LCM is = "+array[array.length-1]);
    }
}

Output:
LCM is = 1386.0