Sorting Algorithm Comparisons in Java

Sorting.java

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.concurrent.TimeUnit;

/**
 * -------------------------------------------
 * File name: Main.java
 * Project Name: Sorting Algorithms
 * Created By: Mackenly Jones
 * -------------------------------------------
 */

interface Algorithm {
    void name();
    void run(int[] array);
}

class BubbleSort implements Algorithm {
    public void name() {
        System.out.print("Bubble Sort: ");
    }

    public void run(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 1; j < array.length; j++) {
                if (array[j] < array[j-1]){
                    swap(array, j, j-1);
                }
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

class SelectionSort implements Algorithm {
    public void name() {
        System.out.println("Selection Sort");
    }

    public void run(int[] array) {
        int n = array.length;

        for (int i = 0; i < n-1; i++) {
            int min = i;
            for (int j = i+1; j < n; j++) {
                if (array[j] < array[min])
                    min = j;
            }
            int temp = array[min];
            array[min] = array[i];
            array[i] = temp;
        }
    }
}

class InsertionSort implements Algorithm {
    public void name() {
        System.out.println("Insertion Sort");
    }

    public void run(int[] array) {
        int n = array.length;
        for (int i=1; i<n; ++i) {
            int key = array[i];
            int j = i-1;
            while (j>=0 && array[j] > key) {
                array[j+1] = array[j];
                j = j-1;
            }
            array[j+1] = key;
        }
    }
}

class MergeSort implements Algorithm {
    public void name() {
        System.out.println("Merge Sort");
    }

    public void run(int[] array) {
        int n = array.length;
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = array[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = array[i];
        }
        run(l, mid);
        run(r, n - mid);

        merge(array, l, r, mid, n - mid);
    }

    public void run(int[] array, int n) {
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] l = new int[mid];
        int[] r = new int[n - mid];

        for (int i = 0; i < mid; i++) {
            l[i] = array[i];
        }
        for (int i = mid; i < n; i++) {
            r[i - mid] = array[i];
        }
        run(l, mid);
        run(r, n - mid);

        merge(array, l, r, mid, n - mid);
    }

    private static void merge(int[] array, int[] l, int[] r, int left, int right) {
        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            if (l[i] <= r[j]) {
                array[k++] = l[i++];
            }
            else {
                array[k++] = r[j++];
            }
        }
        while (i < left) {
            array[k++] = l[i++];
        }
        while (j < right) {
            array[k++] = r[j++];
        }
    }
}

class QuickSort implements Algorithm {
    public void name() {
        System.out.println("Quick Sort");
    }

    public void run(int[] array) {
        int low = 0, high = array.length - 1;
        if (low < high) {
            int pi = partition(array, low, high);
            run(array, low, pi-1);
            run(array, pi+1, high);
        }
    }

    public void run(int[] array, int low, int high) {
        if (low < high) {
            int pi = partition(array, low, high);
            run(array, low, pi-1);
            run(array, pi+1, high);
        }
    }

    private int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1);
        for (int j = low; j <= high-1; j++) {
            if (array[j] <= pivot) {
                i++;
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
        int temp = array[i+1];
        array[i+1] = array[high];
        array[high] = temp;
        return i+1;
    }
}

/**
 * Class Name: Main 
 * Purpose: Runs the sorting algorithms
 * Date: Sep 01, 2022
 */
public class Main {

    public static void main(String[] args) {
        //start code here:
        // run 100 trials of each algorithm
        System.out.println("Each algorithm's run time averaged over 100 trials");
        System.out.println("------------------------------------------------------");
        ArrayList<Long> bubbleSortTimes = new ArrayList<>();
        ArrayList<Long> selectionSortTimes = new ArrayList<>();
        ArrayList<Long> insertionSortTimes = new ArrayList<>();
        ArrayList<Long> mergeSortTimes = new ArrayList<>();
        ArrayList<Long> quickSortTimes = new ArrayList<>();

        for (int i = 0; i < 100; i++) {
            bubbleSortTimes.add(time(new BubbleSort(), randomArray()));
            selectionSortTimes.add(time(new SelectionSort(), randomArray()));
            insertionSortTimes.add(time(new InsertionSort(), randomArray()));
            mergeSortTimes.add(time(new MergeSort(), randomArray()));
            quickSortTimes.add(time(new QuickSort(), randomArray()));
        }

        System.out.println("Bubble Sort: " + average(bubbleSortTimes));
        System.out.println("Selection Sort: " + average(selectionSortTimes));
        System.out.println("Insertion Sort: " + average(insertionSortTimes));
        System.out.println("Merge Sort: " + average(mergeSortTimes));
        System.out.println("Quick Sort: " + average(quickSortTimes));
    } //end main

    private static long time(Algorithm r, int[] array) {
        long start = System.nanoTime();
        r.run(array);
        long end = System.nanoTime();
        return (end - start);
    }

    private static int getRandomInt(int min, int max) {
        return (int) (Math.random() * (max - min) + min);
    }

    private static long average(ArrayList<Long> times) {
        long sum = 0;
        for (long time : times) {
            sum += time;
        }
        return sum / times.size();
    }

    private  static int[] randomArray() {
        // array of 100 random numbers
        int[] array = new int[100];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 100);
        }
        return array;
    }
}