Algo Project

JavaSortAlgoBench.java

import java.io.*;
import java.util.ArrayList;
import java.util.Random;

public class Main {

    public static void main(String[] args) {

        ArrayList<Integer> exArr = generateSortedIntArr(10000);
        ArrayList<Integer> exArrTemp = new ArrayList<>(exArr);

        // warm up jit (just do one heap sort)
        heapSort(exArrTemp);
        exArrTemp.clear();
        exArrTemp.addAll(exArr);
        // warm up finished lets begin real tests

        for (int a = 0; a < 3; a++) {
            exArr.clear();
            exArrTemp.clear();
            System.out.println("********************************************");
            if (a == 0) {
                // BEST CASE TEST (given array is already sorted)
                exArr.addAll(generateSortedIntArr(10000));
                exArrTemp.addAll(exArr);
                System.out.println("BEST CASE TEST - INPUT ARRAY IS ALREADY SORTED, INPUT ARRAY SIZE = 10K\n");
            } else if (a == 1) {
                // TEST WITH 1K INPUT ARRAY FROM 0 to 1000, NO DUPLICATE VALUE (given array is randomized)
                exArr.addAll(genRandIntArrUpToThousandWODup());
                exArrTemp.addAll(exArr);
                System.out.println("INPUT ARRAY SIZE = 1K, FROM 0 to 1000, CONTAINS NO DUPLICATE VALUE\n");
            } else {
                // TEST WITH 10K INPUT ARRAY FROM 0 to 1000, MAY CONTAIN DUPLICATE VALUE (given array is randomized)
                exArr.addAll(genRandIntArrWDup(10000));
                exArrTemp.addAll(exArr);
                System.out.println("INPUT ARRAY SIZE = 10K, FROM 0 to 1000, MAY CONTAIN DUPLICATE VALUE\n");
            }

            // INSERTION SORT
            long totTime = 0L;
            for (int i = 0; i < 5; i++) {
                long execTime = insertionSort(exArrTemp);
                exArrTemp.clear(); // clear sorted array
                exArrTemp.addAll(exArr); // copy unsorted array to cleared array (for next iteration)
                totTime += execTime;
            }
            double avgTime = totTime / 5d;
            System.out.println("INSERTION SORT AVERAGE EXECUTION TIME: " + String.valueOf(avgTime) + " millisecond");

            // COUNTING SORT
            totTime = 0L;
            for (int i = 0; i < 5; i++) {
                long execTime = countingSort(exArrTemp);
                exArrTemp.clear();
                exArrTemp.addAll(exArr);
                totTime += execTime;
            }
            avgTime = totTime / 5d;
            System.out.println("COUNTING SORT AVERAGE EXECUTION TIME: " + String.valueOf(avgTime) + " millisecond");

            // HEAP SORT
            totTime = 0L;
            for (int i = 0; i < 5; i++) {
                long execTime = heapSort(exArrTemp);
                exArrTemp.clear();
                exArrTemp.addAll(exArr);
                totTime += execTime;
            }
            avgTime = totTime / 5d;
            System.out.println("HEAP SORT AVERAGE EXECUTION TIME: " + String.valueOf(avgTime) + " millisecond");

            // MERGE SORT
            totTime = 0L;
            for (int i = 0; i < 5; i++) {
                long execTime = mergeSort(exArrTemp, 0 , exArrTemp.size() - 1);
                exArrTemp.clear();
                exArrTemp.addAll(exArr);
                totTime += execTime;
            }
            avgTime = totTime / 5d;
            System.out.println("MERGE SORT AVERAGE EXECUTION TIME: " + String.valueOf(avgTime) + " millisecond");

            // QUICK SORT
            totTime = 0L;
            for (int i = 0; i < 5; i++) {
                long execTime = quickSort(exArrTemp, 0 , exArrTemp.size() - 1);
                exArrTemp.clear();
                exArrTemp.addAll(exArr);
                totTime += execTime;
            }
            avgTime = totTime / 5d;
            System.out.println("QUICK SORT AVERAGE EXECUTION TIME: " + String.valueOf(avgTime) + " millisecond");

            System.out.println("********************************************\n");
        }
    }

    public static long insertionSort(ArrayList<Integer> arr) {
        long startTime = System.currentTimeMillis();
        int n = arr.size();
        for (int i = 1; i < n; ++i) {
            int key = arr.get(i);
            int j = i - 1;

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j >= 0 && arr.get(j) > key) {
                arr.set(j + 1, arr.get(j));
                j = j - 1;
            }
            arr.set(j + 1, key);
        }
        return System.currentTimeMillis() - startTime;
    }

    // Main function that sorts arr[l..r] using
    public static long mergeSort(ArrayList<Integer> arr, int l, int r) {
        long startTime = System.currentTimeMillis();
        if (l < r) {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            mergeSort(arr, l, m);
            mergeSort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
        return System.currentTimeMillis() - startTime;
    }

    /* The main function that implements QuickSort()
  arr[] --> Array to be sorted,
  low  --> Starting index,
  high  --> Ending index */
    public static long quickSort(ArrayList<Integer> arr, int low, int high) {
        long startTime = System.currentTimeMillis();
        if (low < high) {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            quickSort(arr, low, pi-1);
            quickSort(arr, pi+1, high);
        }
        return System.currentTimeMillis() - startTime;
    }

    public static long heapSort(ArrayList<Integer> arr) {
        long startTime = System.currentTimeMillis();
        int n = arr.size();

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract an element from heap
        for (int i=n-1; i>=0; i--) {
            // Move current root to end
            int temp = arr.get(0);
            arr.set(0, arr.get(i));
            arr.set(i, temp);

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
        return System.currentTimeMillis() - startTime;
    }

    public static long countingSort(ArrayList<Integer> array) {
        long startTime = System.currentTimeMillis();
        // array to be sorted in, this array is necessary
        // when we sort object datatypes, if we don't,
        // we can sort directly into the input array
        ArrayList<Integer> tempArr = new ArrayList<>(array);

        int[] aux = new int[tempArr.size()];

        // find the smallest and the largest value
        int min = tempArr.get(0);
        int max = tempArr.get(0);
        for (int i = 1; i < tempArr.size(); i++) {
            if (tempArr.get(i) < min) {
                min = tempArr.get(i);
            } else if (tempArr.get(i) > max) {
                max = tempArr.get(i);
            }
        }

        // init array of frequencies
        int[] counts = new int[max - min + 1];

        // init the frequencies
        for(int i = 0;  i < tempArr.size(); i++) {
            counts[tempArr.get(i) - min]++;
        }

        // recalculate the array - create the array of occurences
        counts[0]--;
        for (int i = 1; i < counts.length; i++) {
            counts[i] = counts[i] + counts[i-1];
        }

        /*
          Sort the array right to the left
          1) Look up in the array of occurences the last occurence of the given value
          2) Place it into the sorted array
          3) Decrement the index of the last occurence of the given value
          4) Continue with the previous value of the input array (goto set1),
             terminate if all values were already sorted
        */
        for (int i = tempArr.size() - 1; i >= 0; i--) {
            aux[counts[tempArr.get(i) - min]--] = tempArr.get(i);
        }

        // Update values on orig array based on aux arr
        for (int h = 0; h < aux.length; h++) {
            array.set(h, aux[h]);
        }
        return System.currentTimeMillis() - startTime;
    }

    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    public static void merge(ArrayList<Integer> arr, int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr.get(l + i);
        for (int j=0; j<n2; ++j)
            R[j] = arr.get(m + 1+ j);


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr.set(k, L[i]);
                i++;
            }
            else
            {
                arr.set(k, R[j]);
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr.set(k, L[i]);
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr.set(k, R[j]);
            j++;
            k++;
        }
    }

    public static int partition(ArrayList<Integer> arr, int low, int high)
    {
        int pivot = arr.get(high);
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr.get(j) <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr.get(i);
                arr.set(i, arr.get(j));
                arr.set(j, temp);
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr.get(i+1);
        arr.set(i+1, arr.get(high));
        arr.set(high, temp);

        return i+1;
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    public static void heapify(ArrayList<Integer> arr, int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2*i + 1; // left = 2*i + 1
        int r = 2*i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr.get(l) > arr.get(largest))
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr.get(r) > arr.get(largest))
            largest = r;

        // If largest is not root
        if (largest != i)
        {
            int swap = arr.get(i);
            arr.set(i, arr.get(largest));
            arr.set(largest, swap);

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    /* A utility function to print array of size n*/
    public static void printArray(ArrayList<Integer> arr)
    {
        int n = arr.size();
        for (int i = 0; i < n; ++i)
            System.out.print(arr.get(i) + " ");

        System.out.println();
    }

    public static ArrayList<Integer> generateSortedIntArr(int upperLimit) {
        ArrayList<Integer> intArr = new ArrayList<>();

        for (int i = 0; i < upperLimit; i++) {
            intArr.add(i);
        }
        return intArr;
    }

    /* All numbers are in between 0 and 1000
     * and array size is 1000 and NO DUPLICATE
     */
    public static ArrayList<Integer> genRandIntArrUpToThousandWODup() {
        Random rand = new Random(System.currentTimeMillis());
        ArrayList<Integer> intArr = new ArrayList<>();

        for (int i = 0; i < 1000; i++) {
            int randNum;
            do {
                randNum = rand.nextInt((1000) + 1);
            } while(intArr.contains(randNum));
            intArr.add(randNum);
        }
        return intArr;
    }

    /* All numbers are in between 0 and 1000
     * and array size is bounded with param@upperLimit and MAY CONTAIN DUPLICATE
     */
    public static ArrayList<Integer> genRandIntArrWDup(int upperLimit) {
        Random rand = new Random(System.currentTimeMillis());
        ArrayList<Integer> intArr = new ArrayList<>();

        for (int i = 0; i < upperLimit; i++) {
            int randNum = rand.nextInt((1000) + 1);
            intArr.add(randNum);
        }
        return intArr;
    }
}