+1 (315) 557-6473 

Work With Unbalanced Merge Sort in Java Assignment Solution.


Instructions

Objective
Write a program to work with unbalanced merge sort in java language.

Requirements and Specifications

Program to work with unbalanced merge sort in java
Program to work with unbalanced merge sort in java 1

Source Code

BS MERGE SORT

import java.util.Arrays;

import java.util.Random;

import java.util.stream.Collectors;

public class BSMergeSort implements IntegerSort {

    private int comparisons = 0;

    @Override

    public int[] sort(int[] arr) {

        BSTree.resetComparisons();

        int n = arr.length;

        BSTree[] trees = new BSTree[n];

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

            trees[i] = new BSTree(arr[i]);

        }

        int last = n-1;

        while(last > 0) {

            BSTree lastTree = trees[last];

            BSTree preLastTree = trees[last-1];

            trees[last-1] = BSTree.mergeTrees(preLastTree, lastTree);

            last--;

        }

        comparisons = BSTree.getComparisons();

        return trees[0].getSorted();

    }

    @Override

    public int getComparisons() {

        return comparisons;

    }

}

BS TREE

public class BSTree {

    private static int comparisons = 0;

    public static int getComparisons() {

        return comparisons;

    }

    public static void resetComparisons() {

        comparisons = 0;

    }

    private Component root;

    public BSTree(int singleValue) {

        root = new Component(singleValue);

    }

    private BSTree(Component root) {

        this.root = root;

    }

    public int[] getSorted() {

        Component[] components = new Component[root.height];

        int componentsNum = 0;

        Component curr = root;

        while (curr != null) {

            components[componentsNum] = curr;

            curr = curr.right;

            componentsNum++;

        }

        componentsNum--;

        int[] currResult = null;

        while (componentsNum >= 0) {

            curr = components[componentsNum];

            int size = curr.leftTree == null ? 1 : curr.leftTree.length + 1;

            int[] step = new int[size];

            for (int i = 0; i<size-1; i++) {

                step[i] = components[componentsNum].leftTree[i];

            }

            step[size-1] = curr.rootValue;

            if (currResult == null) {

                currResult = step;

            }

            else {

                int nextSize = step.length + currResult.length;

                int[] nextResult = new int[nextSize];

                int stepCounter = 0;

                int currResultCounter = 0;

                int counter = 0;

                while(counter < nextSize) {

                    if (stepCounter < step.length && currResultCounter < currResult.length) {

                        comparisons++;

                        if (step[stepCounter] <= currResult[currResultCounter]) {

                            nextResult[counter] = step[stepCounter];

                            stepCounter++;

                        }

                        else {

                            nextResult[counter] = currResult[currResultCounter];

                            currResultCounter++;

                        }

                    }

                    else if (stepCounter < step.length) {

                        nextResult[counter] = step[stepCounter];

                        stepCounter++;

                    }

                    else {

                        nextResult[counter] = currResult[currResultCounter];

                        currResultCounter++;

                    }

                    counter++;

                }

                currResult = nextResult;

            }

            componentsNum--;

        }

        return currResult;

    }

    public static BSTree mergeTrees(BSTree bsTree1, BSTree bsTree2) {

        Component[] tree1Components = new Component[bsTree1.root.height];

        int tree1ComponentsNum = 0;

        Component curr = bsTree1.root;

        while (curr != null) {

            tree1Components[tree1ComponentsNum] = curr;

            curr = curr.right;

            tree1ComponentsNum++;

        }

        tree1ComponentsNum--;

        Component[] tree2Components = new Component[bsTree2.root.height];

        int tree2ComponentsNum = 0;

        curr = bsTree2.root;

        while (curr != null) {

            tree2Components[tree2ComponentsNum] = curr;

            curr = curr.right;

            tree2ComponentsNum++;

        }

        tree2ComponentsNum--;

        Component carry = null;

        Component lastAdded = null;

        while(tree1ComponentsNum >= 0 || tree2ComponentsNum >= 0 || carry != null) {

            Component currComponent1 = tree1ComponentsNum >= 0 ? tree1Components[tree1ComponentsNum] : null;

            Component currComponent2 = tree2ComponentsNum >= 0 ? tree2Components[tree2ComponentsNum] : null;

            Component[] components = new Component[]{carry, currComponent1, currComponent2};

            int level = Integer.MAX_VALUE;

            for (Component c : components) {

                if (c != null) {

                    if (level > c.height) {

                        level = c.height;

                    }

                }

            }

            Component[] levelComponents = new Component[3];

            int levelComponentsNum = 0;

            for (Component c : components) {

                if (c != null) {

                    if (level == c.height) {

                        if (c == currComponent1) {

                            tree1ComponentsNum--;

                        }

                        if (c == currComponent2) {

                            tree2ComponentsNum--;

                        }

                        levelComponents[levelComponentsNum] = c;

                        levelComponentsNum++;

                    }

                }

            }

            if (levelComponentsNum == 3) {

                int maxIndex = 0;

                int maxRoot = levelComponents[0].rootValue;

                for (int i = 1; i<levelComponentsNum; i++) {

                    Component c = levelComponents[i];

                    comparisons++;

                    if (c.rootValue > maxRoot) {

                        maxIndex = i;

                        maxRoot = c.rootValue;

                    }

                }

                Component[] toMerge = new Component[2];

                int toMergeNum = 0;

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

                    if (i != maxIndex) {

                        toMerge[toMergeNum] = levelComponents[i];

                        toMergeNum++;

                    }

                }

                levelComponents[maxIndex].right = lastAdded;

                lastAdded = levelComponents[maxIndex];

                carry = mergeComponents(toMerge[0], toMerge[1]);

            }

            else if (levelComponentsNum == 2){

                carry = mergeComponents(levelComponents[0], levelComponents[1]);

            }

            else if (levelComponentsNum == 1) {

                levelComponents[0].right = lastAdded;

                lastAdded = levelComponents[0];

                carry = null;

            }

        }

        return new BSTree(lastAdded);

    }

    private static class Component {

        int height;

        int rootValue;

        int[] leftTree;

        Component right;

        Component(int rootValue) {

            this.rootValue = rootValue;

            this.height = 1;

            this.leftTree = null;

            this.right = null;

        }

        Component(int rootValue, int[] leftTree) {

            this.rootValue = rootValue;

            int size = leftTree.length;

            this.height = 1;

            while(size > 0) {

                size /= 2;

                height++;

            }

            this.leftTree = leftTree;

            this.right = null;

        }

    }

    private static Component mergeComponents(Component c1, Component c2) {

        if (c1.height != c2.height) {

            throw new IllegalStateException();

        }

        int size = c1.leftTree == null ? 1 : c1.leftTree.length + 1;

        int newLength = 2 * size - 1;

        int[] leftTree = new int[newLength];

        int counter1 = 0;

        int counter2 = 0;

        int counter = 0;

        while(counter < newLength) {

            if (counter1 < size && counter2 < size) {

                int val1 = (counter1 < size - 1) ? c1.leftTree[counter1] : c1.rootValue;

                int val2 = (counter2 < size - 1) ? c2.leftTree[counter2] : c2.rootValue;

                comparisons++;

                if (val1 <= val2) {

                    leftTree[counter] = val1;

                    counter1++;

                }

                else {

                    leftTree[counter] = val2;

                    counter2++;

                }

            }

            else if (counter1 < size) {

                leftTree[counter] = (counter1 < size - 1) ? c1.leftTree[counter1] : c1.rootValue;

                counter1++;

            }

            else {

                leftTree[counter] = (counter2 < size - 1) ? c2.leftTree[counter2] : c2.rootValue;

                counter2++;

            }

            counter++;

        }

        int rootValue = (counter1 < size) ? c1.rootValue : c2.rootValue;

        return new Component(rootValue, leftTree);

    }

    public static void main(String[] args) {

        Component c1 = new Component(90, new int[]{21, 30, 89});

        Component c11 = new Component(77);

        c1.right = c11;

        Component c2 = new Component(93, new int[]{3, 22, 57});

        Component c21 = new Component(87, new int[]{8});

        Component c211 = new Component(58);

        c21.right = c211;

        c2.right = c21;

        BSTree tree1 = new BSTree(c1);

        BSTree tree2 = new BSTree(c2);

        BSTree tree = mergeTrees(tree1, tree2);

        System.out.println(tree);

    }

}

INTEGER SORT

public interface IntegerSort {

    int[] sort(int[] arr);

    int getComparisons();

}

MERGE SORT

public class MergeSort implements IntegerSort {

    private int comparisons = 0;

    @Override

    public int[] sort(int[] arr) {

        comparisons = 0;

        int[] aux = new int[arr.length];

        int[] copy = new int[arr.length];

        System.arraycopy(arr, 0, copy, 0, arr.length);

        mergeSort(copy, aux, 0, arr.length - 1);

        return copy;

    }

    @Override

    public int getComparisons() {

        return comparisons;

    }

    private void mergeSort(int[] arr, int[] aux, int low, int high) {

        if (low >= high) {

            return;

        }

        int middle = (low + high) / 2;

        mergeSort(arr, aux, low, middle);

        mergeSort(arr, aux, middle+1, high);

        merge(arr, aux, low, middle, high);

    }

    private void merge(int[] arr, int[] aux, int low, int mid, int high) {

        if (high + 1 - low >= 0) System.arraycopy(arr, low, aux, low, high + 1 - low);

        int i = low;

        int j = mid + 1;

        for (int k = low; k <= high; k++) {

            if (i > mid) {

                arr[k] = aux[j];

                j++;

            } else if (j > high) {

                arr[k] = aux[i];

                i++;

            } else {

                comparisons++;

                if (aux[i] <= aux[j]) {

                    arr[k] = aux[i];

                    i++;

                } else {

                    arr[k] = aux[j];

                    j++;

                }

            }

        }

    }

}