SortingAlgorithmsTermProject

MergeSort.java

package main;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * Created by Austin on 2/24/17.
 */
public class MergeSort extends SortAlgorithm {

    public void sort(int[] array) throws Exception{
        try{
            mergeSort(array);
        }catch(Exception e){
            e.printStackTrace();
        }
    }

    public void runningTime(int numArrays, int arraySize) {

        // Declare list of arrays of type int
        ArrayList<int[]> list = new ArrayList<int[]>();
        long [] durationArray = new long[numArrays];
        long totalDuration = 0;
        long avgDuration = 0;

        // Alloc array and fill with random integers
        // Then add array to ArrayList.
        for (int i = 0; i < numArrays; ++i) {
            int[] array = new int[arraySize];
            for (int j = 0; j < array.length; ++j) {
                Random r = new Random();
                int randomNum = r.nextInt();
                array[j] = randomNum;
            }
            list.add(i, array);
        }

        // Iterate through list, using system time to determine how long shellSort algorithm takes.
        for(int i = 0; i < list.size(); ++i) {
            long startTime = System.nanoTime();
            mergeSort(list.get(i));
            long endTime = System.nanoTime();
            long duration = ((endTime - startTime)/1000000);  //divide by 1000000 to get milliseconds
            durationArray[i] = duration;
            totalDuration += duration;
        }
        // Display duration stats.
        avgDuration = totalDuration/list.size();
        System.out.print("Array Size: " + arraySize + ", ");
        //System.out.println("Sort Times: " + Arrays.toString(durationArray));
        System.out.println("Average Merge Sort time: " + avgDuration + " milliseconds.");
    }

    public int[] mergeSort(int[] array) {
        if(array != null){
            // Base case, one or zero elements remaining in array
            if (array.length <= 1) {
                return array;
            }
            // Make local arrays to store each half of original array
            int[] left = new int[array.length / 2];
            int[] right = new int[array.length - left.length];

            // Copy first half of integers into left
            System.arraycopy(array, 0, left, 0, left.length);

            // Copy second half of integers into right
            System.arraycopy(array, left.length, right, 0, right.length);

            // recursive call on first half
            mergeSort(left);

            // recursive call on second half
            mergeSort(right);

            // combine sorted
            merge(left, right, array);
            return array;
        }
        return null;
    }

    public void merge(int[] left, int[] right, int[] result) {
        int i = 0;
        int j = 0;
        int k = 0;

        int i1 = left[i];
        int i2 = right[j];

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                result[k] = left[i];
                ++i;
            } else {
                result[k] = right[j];
                ++j;
            }
            ++k;
        }
        System.arraycopy(left, i, result, k, left.length - i);
        System.arraycopy(right, j, result, k, right.length - j);
    }

    public static void main(String[] args) {

        int numArraysToSort = 10;
        int arraySize = 1000;

        MergeSort obj = new MergeSort();

        System.out.println("-- Merge Sort Stats -- ");
        for(int i = 0; i < 5; ++i) {
            obj.runningTime(numArraysToSort, arraySize);
            arraySize *= 10;
        }
    }
}

MergeSortTest.java

package test;

import main.MergeSort;
import main.ShellSort;
import main.SortAlgorithm;
import org.junit.Test;

import java.util.Arrays;

import static org.junit.Assert.*;

/**
 * Created by Austin on 3/14/17.
 */
public class MergeSortTest {

    @Test // Case where each element in array has same value
    public void sortSameNumbers(){
        //System.out.print("@Test (MergeSort) sortSameNumbers: ");
        int size = 10000;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];

        for (int i = 0; i < myArray.length; ++i) {
            myArray[i] = 42; // set each index element to 42
        }
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm mergeSort = new MergeSort();
        try{
            mergeSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }
        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where each element in array is increasing by 1
    public void sortSequentialNumbers(){
        //System.out.print("@Test (MergeSort) sortSequentialNumbers: ");
        int size = 10000;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];

        for (int i = 0; i < myArray.length; ++i) {
            myArray[i] = i;
        }
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm mergeSort = new MergeSort();
        try{
            mergeSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }
        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where array is empty
    public void sortEmpty(){
        //System.out.print("@Test (MergeSort) sortEmpty: ");
        int size = 0;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm mergeSort = new MergeSort();
        try{
            mergeSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }
        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where array has one element
    public void sortOne(){
        //System.out.print("@Test (ShellSort) sortOne: ");
        int size = 1;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm mergeSort = new ShellSort();
        try{
            mergeSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }


    @Test // Case where array is null
    public void sortNull(){
        //System.out.print("@Test (MergeSort) sortOne: ");
        int[] myArray = null;
        try{
            SortAlgorithm mergeSOrt = new ShellSort();
            mergeSOrt.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }
        //System.out.println("Passed.");
    }
}

ShellSort.java

package main;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * Created by Austin on 3/4/17.
 */
public class ShellSort extends SortAlgorithm {

    public void sort(int[] array) throws Exception{
        try{
            shellSort(array);
        }catch(Exception e){
            e.printStackTrace();
        }
    }

    public void shellSort(int [] array){

        int inner = 0;
        int outer = 0;
        int temp = 0;
        int h = 1;

        /*
        Knuth's increment sequence (3h+1), aka interval
         */
        if(array != null){
            while (h <= array.length/3){
                h = (3 * h) + 1;
            }
            while (h > 0){
                for (outer = h; outer < array.length; outer++){
                    temp = array[outer];
                    inner = outer;

                    while (inner > h - 1 && array[inner - h] >= temp) {
                        array[inner] = array[inner - h];
                        inner -= h;
                    }
                    array[inner] = temp;
                }
                // Calculate new inteval
                h = (h - 1) / 3;
            }
        }
    }

    public void runningTime(int numArrays, int arraySize){

        // Declare list of arrays of type int
        ArrayList<int[]> list = new ArrayList<int[]>();
        long [] durationArray = new long[numArrays];
        long totalDuration = 0;
        long avgDuration = 0;

        // Alloc array and fill with random integers
        // Then add array to ArrayList.
        for (int i = 0; i < numArrays; ++i) {
            int[] array = new int[arraySize];
            for (int j = 0; j < array.length; ++j) {
                Random r = new Random();
                int randomNum = r.nextInt();
                array[j] = randomNum;
            }
            list.add(i, array);
        }

        // Iterate through list, usiing system time to determine how long shellSort algorithm takes.
        for(int i = 0; i < list.size(); ++i) {
            long startTime = System.nanoTime();
            try{
                sort(list.get(i));

            }catch(Exception e){
                e.printStackTrace();
            }
            long endTime = System.nanoTime();
            long duration = ((endTime - startTime)/1000000);  //divide by 1000000 to get milliseconds
            durationArray[i] = duration;
            totalDuration += duration;
        }
        // Display duration stats.
        avgDuration = totalDuration/list.size();
        System.out.print("Array Size: " + arraySize + ", ");
        //System.out.println("Sort Times: " + Arrays.toString(durationArray));
        System.out.println("Average shellSort time: " + avgDuration + " milliseconds.");
    }

    public static void main(String[] args){

        int numArraysToSort = 10;
        int arraySize = 1000;
        SortAlgorithm obj = new ShellSort();

        System.out.println("-- Shell Sort Stats -- ");
        for(int i = 0; i < 5; ++i) {
            obj.runningTime(numArraysToSort, arraySize);
            arraySize *= 10;
        }
    }
}

ShellSortTest.java

package test;

import main.ShellSort;
import main.SortAlgorithm;
import org.junit.Test;

import java.util.Arrays;
import static org.junit.Assert.*;

/**
 * Created by Austin on 3/13/17.
 */
public class ShellSortTest {

    @Test // Case where each element in array has same value
    public void sortSameNumbers(){

        //System.out.print("@Test (ShellSort) sortSameNumbers: ");
        int size = 10000;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];

        for (int i = 0; i < myArray.length; ++i) {
            myArray[i] = 42; // set each index element to 42
        }
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm shellSort = new ShellSort();
        try{
            shellSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where each element in array is increasing by 1
    public void sortSequentialNumbers(){
        //System.out.print("@Test (ShellSort) sortSequentialNumbers: ");
        int size = 10000;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];

        for (int i = 0; i < myArray.length; ++i) {
            myArray[i] = i;
        }
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm shellSort = new ShellSort();
        try{
            shellSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where array is empty
    public void sortEmpty(){
        //System.out.print("@Test (ShellSort) sortEmpty: ");
        int size = 0;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm shellSort = new ShellSort();
        try{
            shellSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where array has one element
    public void sortOne(){
        //System.out.print("@Test (ShellSort) sortOne: ");
        int size = 1;
        int[] myArray = new int[size];
        int[] javaArray = new int[size];
        System.arraycopy(myArray, 0, javaArray, 0, myArray.length);
        SortAlgorithm shellSort = new ShellSort();
        try{
            shellSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }        Arrays.sort(javaArray);
        assertArrayEquals(myArray, javaArray);
        //System.out.println("Passed.");
    }

    @Test // Case where array is null
    public void sortNull(){
        //System.out.print("@Test (ShellSort) sortOne: ");
        int[] myArray = null;
        try{
        SortAlgorithm shellSort = new ShellSort();
            shellSort.sort(myArray);
        }catch(Exception e){
            e.printStackTrace();
        }
        //System.out.println("Passed.");
    }



}

SortAlgorithm.java

package main;

/**
 * Created by Austin on 2/24/17.
 */
public abstract class SortAlgorithm {
    public abstract void sort(int [] array) throws Exception;
    public abstract void runningTime(int numArrays, int arraySize);
    public boolean isSorted(int[] array){
        for(int i = 0; i < array.length -1; ++i){
            if (array[i] > array[i+1]) {
                return false; // Not sorted
            }
        }
        return true;
    }

    //25,600,000
    public static void main(String [] args){
        // number of arrays to shellSort is the number of times the algorithm will
        // run on an array. The array size is the size of the array to be sorted.
        int numArraysToSort = 10;
        int arraySize = 50000;
        int numScales = 10;

        SortAlgorithm mergeSort = new MergeSort();
        SortAlgorithm shellSort = new ShellSort();

        System.out.println("-- Merge Sort Stats -- ");
        for(int i = 0; i < numScales; ++i) {
            mergeSort.runningTime(numArraysToSort, arraySize);
            arraySize *= 2;
        }

        // Repeat for shell shellSort algorithm, resetting array size back to
        // starting value.
        arraySize = 50000;
        System.out.println("-- Shell Sort Stats -- ");
        for(int i = 0; i < numScales; ++i) {
            shellSort.runningTime(numArraysToSort, arraySize);
            arraySize *= 2;
        }
    }
}