Instructions
Requirements and Specifications
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
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
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
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
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++;
}
}
}
}
}