James Jason | Software Engineer
Algorithms

Sorting Algorithms

Merge Sort
This program implements merge sort. It generates a specified number of integers (NUMBERS_GENERATED) ranging from (MIN_NUMBER) to (MAX_NUMBER). It then sorts them.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    final static int MIN_NUMBER = 1;
    final static int MAX_NUMBER = 100;
    final static int NUMBERS_GENERATED = 100;

    public static void main(String[] args) {
        Integer[] int_array = new Integer[NUMBERS_GENERATED];
        Random rand = new Random();

        for (int i = 0; i < int_array.length; i++) {
            int_array[i] = rand.nextInt((MAX_NUMBER - MIN_NUMBER) + 1) + MIN_NUMBER;
        }

        ArrayList list = new ArrayList<>(Arrays.asList(int_array));
        System.out.println(mergeSort(list));
    }

    private static ArrayList mergeSort(ArrayList list) {
        ArrayList left_half, right_half;
        if (list.size() <= 1) {
            return list;
        } else if (list.size() == 2) {
            left_half = new ArrayList<>(list.subList(0, 1));
            right_half = new ArrayList<>(list.subList(1, list.size()));
            return merge(left_half, right_half);
        } else {
            left_half = new ArrayList<>(list.subList(0, list.size() / 2));
            right_half = new ArrayList<>(list.subList(list.size() / 2, list.size()));
            return merge(mergeSort(left_half), mergeSort(right_half));
        }
    }

    private static ArrayList merge(ArrayList left_half, ArrayList right_half) {
        ArrayList final_list = new ArrayList<>();
        int right_half_index = 0;
        for (int i = 0; i < left_half.size(); i++) {
            while (right_half_index < right_half.size() && right_half.get(right_half_index) < left_half.get(i)) {
                final_list.add(right_half.get(right_half_index));
                right_half_index++;
            }
            final_list.add(left_half.get(i));
        }
        for (int i = right_half_index; i < right_half.size(); i++) {
            final_list.add(right_half.get(i));
        }
        return final_list;
    }
}
Quicksort
The following program implements Quicksort. It generates a specified number of integers (NUMBERS_GENERATED) ranging from (MIN_NUMBER) to (MAX_NUMBER). It then sorts them.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

public class QuickSort {

    final static int MIN_NUMBER = 1;
    final static int MAX_NUMBER = 100;
    final static int NUMBERS_GENERATED = 100;

    public static void main(String[] args) {
        Integer[] int_array = new Integer[NUMBERS_GENERATED];
        Random rand = new Random();

        for (int i = 0; i < int_array.length; i++) {
            int_array[i] = rand.nextInt((MAX_NUMBER - MIN_NUMBER) + 1) + MIN_NUMBER;
        }

        ArrayList list = new ArrayList<>(Arrays.asList(int_array));
        System.out.println(list);
        System.out.println(quickSort(list));
    }

    private static ArrayList quickSort(ArrayList list) {
        if (list.size() <= 1) {
            return list;
        } else {
            Integer pivot = (Integer) list.get(list.size() - 1);
            list.remove(list.size() - 1);
            ArrayList less_than_pivot, more_than_pivot;
            less_than_pivot = new ArrayList<>();
            more_than_pivot = new ArrayList<>();
            for (int i = 0; i < list.size(); i++) {
                if ((Integer) list.get(i) < pivot) {
                    less_than_pivot.add((Integer) list.get(i));
                } else {
                    more_than_pivot.add((Integer) list.get(i));
                }
            }
            return join_elements(quickSort(less_than_pivot), quickSort(more_than_pivot), pivot);
        }
    }

    private static ArrayList join_elements(ArrayList a, ArrayList b, Integer pivot) {
        a.add(pivot);
        a.addAll(b);
        return a;
    }
}
Sorting Algorithm Using Two Stacks
The following program uses two stacks to sort a list of numbers in descending order.
import java.util.Stack;
public class TwoStacksToSort {

    final static int MIN_NUMBER = 1;
    final static int MAX_NUMBER = 40;
    final static int NUMBERS_GENERATED = 20;
    
    public static void main(String[] args) {
        Stack st= new Stack();
        for (int i = 0; i < NUMBERS_GENERATED; i++) {
            int num = (int) (Math.random() * MAX_NUMBER);
            st.push(num);
        }
        System.out.print("Original:\t");
        printStack(st);
        twoStackSort(st);
        System.out.print("Sorted (DESC):\t");
        printStack(st);
    }
    
    public static void twoStackSort(Stack st1) {
        Stack st2 = new Stack<>();
        int times = st1.size();

        for (int j = 0; j < times; j++) {
            Integer min = st1.peek();
            for (int i = 0; i < times-j; i++) {
                Integer currentElement = st1.pop();
                if (currentElement < min) {
                    min = currentElement;
                }
                st2.push(currentElement);
            }
            st1.push(min);
            boolean first_instance = true;

            for (int i = 0; i < times-j; i++) {
                int currentElement = st2.pop();
                if (min == currentElement) {
                    if(!first_instance){
                        st1.push(currentElement);
                    }
                    first_instance = false;
                } else{
                    st1.push(currentElement);
                }
            }
        }

    }

    private static void printStack(Stack st) {
        String seperator = ", ";
        Stack temp = new Stack<>();
        int stackSize = st.size();
        for (int i = 0; i < stackSize; i++) {
            Integer element = st.pop();
            if(i == stackSize - 1){ seperator = ""; }
            System.out.print(element + seperator);
            temp.push(element);
        }
        
        for (int i = 0; i < stackSize; i++) {
            st.push(temp.pop());
        }
        System.out.println();
    }
}

String Algorithms

Check if String s1 is a Rotation of Another String s2
This program implements a clever algorithm to determine if a string is a rotation of another string. For example "llbasketba" is a rotation of "basketball".
import java.util.ArrayList;

public class CheckRotation {

    public static void main(String[] args) {
        String s1 = "I own a basketball";
        String s2 = "n a basketballI ow";
        boolean s2IsARotationofS1 = isRotation(s1, s2);
        System.out.println(s2IsARotationofS1);
        
        // Also Generate all Rotations of s1
        ArrayList allRotations = generateRotations(s1);
        System.out.println(allRotations);
    }

    private static boolean isRotation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        String ss = s1 + s1;
        return ss.contains(s2);
    }

    private static ArrayList generateRotations(String s1) {
        int len = s1.length();
        String ss = s1 + s1;
        ArrayList allRotations = new ArrayList<>();
        for (int i = 1; i < len; i++) {
            allRotations.add(ss.substring(i, i + len));
        }
        return allRotations;
    }

}
Check if String s1 is a Permutation of Another String s2
This program takes two strings and determines if one is a permutation of another.
public class IsPermutation {
    public static void main(String[] args) {
        String s1 = "andsl";
        String s2 = "sandl";
        boolean isPermutation = isPermutation(s1, s2);
        System.out.println(isPermutation);
    }

    private static boolean isPermutation(String s1, String s2) {

        StringBuilder sb1 = new StringBuilder(s1);
        StringBuilder sb2 = new StringBuilder(s2);

        for (int i = 0; i < sb1.length(); i++) {
            int index = firstIndexOfChar(sb2, sb1.charAt(i));
            if(index == -1){
                return false;
            } else{
                sb2.deleteCharAt(index);
            }
        }
        return ("".equals(sb2.toString()));
    }

    private static int firstIndexOfChar(StringBuilder str, char c) {
            for (int i = 0; i < str.length(); i++) {
                if(str.charAt(i) == c){
                    return i;
                }
        }
            return -1;
    }
    
}

Matrix Algorithms

Rotate a Matrix
This program rotates a randomly generated matrix 90 degrees. Here's a sample run with a 6 by 6 matrix.
   [88, 31, 18, 95, 9, 94]
   [27, 82, 99, 40, 3, 12]
   [70, 29, 23, 27, 26, 75]
   [45, 43, 57, 94, 77, 91]
   [55, 14, 84, 13, 96, 85]
   [41, 58, 7, 21, 31, 69]
   ---------------------------
   [41, 55, 45, 70, 27, 88]
   [58, 14, 43, 29, 82, 31]
   [7, 84, 57, 23, 99, 18]
   [21, 13, 94, 27, 40, 95]
   [31, 96, 77, 26, 3, 9]
   [69, 85, 91, 75, 12, 94]
public class RotateMatrix {

    final static int MATRIX_SIZE = 6;

    public static void main(String[] args) {

        int[][] scores = new int[MATRIX_SIZE][MATRIX_SIZE];

        for (int i = 0; i < MATRIX_SIZE; i++) {
            for (int j = 0; j < MATRIX_SIZE; j++) {
                scores[i][j] = (int) (Math.random() * 100.0);
            }
            printArray(scores[i]);
        }
        System.out.println("----------------------");
        int[][] rotatedScores = rotateMatrix(scores);
        for (int i = 0; i < MATRIX_SIZE; i++) {
            printArray(rotatedScores[i]);
        }
    }

    private static void printArray(int[] a) {
        System.out.print("[");
        String seperator = ", ";
        for (int i = 0; i < a.length; i++) {
            if (i == a.length - 1) {
                seperator = "";
            }
            System.out.print(a[i] + seperator);
        }
        System.out.print("]");
        System.out.println();
    }

    private static int[][] rotateMatrix(int[][] scores) {
        int matrixSize = scores[0].length;
        int[][] rotatedScores = new int[matrixSize][matrixSize];
        for (int i = 0; i < scores[0].length; i++) {
            rotatedScores[i] = reverseArray(getNthColumn(scores, i));
        }
        return rotatedScores;
    }

    private static int[] getNthColumn(int[][] matrix, int nthColumn) {
        int[] col = new int[matrix[0].length];
        for (int i = 0; i < matrix[0].length; i++) {
            col[i] = matrix[i][nthColumn];
        }
        return col;
    }

    private static int[] reverseArray(int[] a) {
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[a.length - 1 - i] = a[i];
        }

        return b;
    }
}
Set Entire Row & Column to Zero
This program generates a random matrix of specified dimensions. It then examines it for zero values. If a zero is encountered then its entire row and column are set to zero.
   [1, 4, 4, 2]
   [1, 4, 4, 2]
   [2, 4, 4, 0]
   [0, 3, 4, 1]
   [0, 1, 3, 1]
   [4, 1, 2, 4]
   ------------
   [0, 4, 4, 0]
   [0, 4, 4, 0]
   [0, 0, 0, 0]
   [0, 0, 0, 0]
   [0, 0, 0, 0]
   [0, 1, 2, 0]
public class MatrixSetRowsColsToZero {

    final static int MATRIX_NUM_OF_ROWS = 6;
    final static int MATRIX_NUM_OF_COLS = 4;

    public static void main(String[] args) {
        int[][] scores = new int[MATRIX_NUM_OF_ROWS][MATRIX_NUM_OF_COLS];

        // Populate & Print Matrix
        for (int i = 0; i < MATRIX_NUM_OF_ROWS; i++) {
            for (int j = 0; j < MATRIX_NUM_OF_COLS; j++) {
                scores[i][j] = (int) (Math.random() * 5.0);
            }
            printArray(scores[i]);
        }

        System.out.println("----------------------");

        int[][] aleteredMatrix = alterMatrix(scores);

        // Print Altered Matrix
        for (int i = 0; i < aleteredMatrix.length; i++) {
            printArray(aleteredMatrix[i]);

        }

    }

    private static int[][] alterMatrix(int[][] scores) {

        boolean[][] booleanMatrix = new boolean[scores.length][scores[0].length];
        for (int i = 0; i < booleanMatrix.length; i++) {
            for (int j = 0; j < booleanMatrix[0].length; j++) {
                if (scores[i][j] == 0) {
                    setRowToTrue(booleanMatrix, i);
                    setColToTrue(booleanMatrix, j);
                }
            }
        }

        int[][] finalMatrix = scores.clone();

        for (int i = 0; i < booleanMatrix.length; i++) {
            for (int j = 0; j < booleanMatrix[0].length; j++) {
                if (booleanMatrix[i][j] == true) {
                    finalMatrix[i][j] = 0;
                }
            }
        }

        return finalMatrix;
    }

    private static void setRowToTrue(boolean[][] finalMatrix, int rowNum) {
        boolean[] a = new boolean[finalMatrix[rowNum].length];
        for (int i = 0; i < a.length; i++) {
            a[i] = true;
        }
        finalMatrix[rowNum] = a;
    }

    private static void setColToTrue(boolean[][] finalMatrix, int colNum) {
        for (int i = 0; i < finalMatrix.length; i++) {
            finalMatrix[i][colNum] = true;
        }
    }

    private static void printArray(int[] a) {
        System.out.print("[");
        String seperator = ", ";
        for (int i = 0; i < a.length; i++) {
            if (i == a.length - 1) {
                seperator = "";
            }
            System.out.print(a[i] + seperator);
        }
        System.out.print("]");
        System.out.println();
    }
}

LinkedList Algorithms

Add Two Numbers Represented as LinkedLists
A number represented with a LinkedList has its ones value at the head node. The node following the head represents the tenth place and so on. In this program the addNumbers method takes two LinkedList represented numbers and adds them. The result is also a LinkedList Represented number. A basic implementation of LinkedList with helper methods such as printList and contains, is also included.
public class AddTwoNumbersLinkedList {

    public static void main(String[] args) {
        
        LinkedList number1 = new LinkedList();
        // 295
        number1.addElement(5);
        number1.addElement(9);
        number1.addElement(2);
        
        LinkedList number2 = new LinkedList();
        // 617
        number2.addElement(7);
        number2.addElement(1);
        number2.addElement(6);
        
        LinkedList sum = addNumbers(number1, number2);
        sum.printList();
    }

    private static LinkedList addNumbers(LinkedList number1, LinkedList number2) {
        if(number1.size() > number2.size()){
            for (int i = 0; i < number1.size() - number2.size(); i++) {
                number2.addElement(0);
            }
        } 
        if(number2.size() > number1.size()){
            for (int i = 0; i < number2.size() - number1.size(); i++) {
                number1.addElement(0);
            }
        }

        int carry = 0;
        
        Node number1CurrentNode = number1.getHead();
        Node number2CurrentNode = number2.getHead();
        LinkedList totalSum = new LinkedList();
        for (int i = 0; i < number1.size(); i++) {
            int sum = number1CurrentNode.getData() + number2CurrentNode.getData() + carry;
            if(sum > 9){
                if(number1CurrentNode.getNext() == null){
                    totalSum.addElement(sum % 10);
                    totalSum.addElement(sum / 10);
                } else{
                    carry = sum / 10;
                    totalSum.addElement(sum % 10);

                }
            } else{
                totalSum.addElement(sum);
            }
            number1CurrentNode = number1CurrentNode.getNext();
            number2CurrentNode = number2CurrentNode.getNext();
        }
        
        return totalSum;
    
    }
    
}


class Node{
    private Node next;
    private int data;

    public Node(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

}


class LinkedList{
    private Node head;
    private int size;
    
    public LinkedList() {
        this.size = 0;
    }
    
    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }
    
    
    public void addElement(int elm){
        if(head == null){
            head = new Node(elm);
        } else{
            Node tail = head;
            while(tail.getNext() != null){
                tail = tail.getNext();
            }
            tail.setNext(new Node(elm));
        }
        size++;
    }
    
    public void  printList(){
        Node currentNode = head;
        while(currentNode != null){
            String seperator = currentNode.getNext() != null ? ", " : "";
            System.out.print(currentNode.getData() + seperator);
            currentNode = currentNode.getNext();
        }
        System.out.println();
    }
    
    public boolean contains(int data){
        Node currentNode = head;
        while(currentNode != null){
            
            if(currentNode.getData() == data){
                return true;
            }
            currentNode = currentNode.getNext();
        }
        return false;
    }
    
    public int size(){
        return size;
    }
}
Delete Node from Singly LinkedList
How would you delete a node from a singly LinkedList when you're only given access to the node to be deleted? If we delete the node then all the nodes after it are lost. One solution is to copy the data of the next node to the current node (the node we're deleting) and then delete the next node. The code is given below. There is one small problem with this solution. It does not work when the node to be deleted is the tail node. To overcome that we can keep a dummy node at the end of the list.
public class DeleteNodeFromLinkedList {

    static LinkedList list;
    public static void main(String[] args) {
        list = new LinkedList();
        for (int i = 0; i < 10; i++) {
            int randNum = (int) (Math.random() * 10.0);
            list.addElement(randNum);
        }
        Node node = list.getHead().getNext().getNext().getNext();
        deleteNode(list, node);
        list.printList();
    }
    
    private static boolean deleteNode(LinkedList list, Node node) {
        if(node == null){
            return false;
        }
        if(node.getNext() != null){
            node.setData(node.getNext().getData());
            node.setNext(node.getNext().getNext());
            return true;
        } else{
            // tail node
            return false;
        }
    }
}
Top