import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Random;

public class Main {

    public static void main(String[] args)
    {
        long time1 = System.nanoTime();

        int[] sizes = {1_000, 2_000, 4_000, 8_000, 16_000, 32_000, 64_000, 128_000};

        Random random = new Random();

        Sort.dummy();
        System.out.println("\nBubble Sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            Sort.bubbleSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBubble Sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            Sort.bubbleSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBubble Sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Sort.bubbleSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nSelection Sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            Sort.selectionSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nSelection Sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            Sort.selectionSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nSelection Sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Sort.selectionSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nInsertion Sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            Sort.insertionSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nInsertion Sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            Sort.insertionSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nInsertion Sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Sort.insertionSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nHeap Sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            Sort.heapSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nHeap Sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            Sort.heapSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nHeap Sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Sort.heapSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nQuicksort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            try {
                Sort.quicksort(A, 0, A.length - 1);
            }
            catch (StackOverflowError e) {
                System.out.println("Error: " + e);
            }
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nQuicksort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            try {
                Sort.quicksort(A, 0, A.length - 1);
            }
            catch (StackOverflowError e) {
                System.out.println("Error: " + e);
            }
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nQuicksort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            try {
                Sort.quicksort(A, 0, A.length - 1);
            }
            catch (StackOverflowError e) {
                System.out.println("Error: " + e);
            }
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nShell Sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            Sort.shellSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nShell Sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            Sort.shellSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nShell Sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Sort.shellSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nMergesort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            try {
                Sort.mergesort(A, 0, A.length - 1);
            }
            catch (StackOverflowError e) {
                System.out.println("Error: " + e);
            }
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nMergesort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            try {
                Sort.mergesort(A, 0, A.length - 1);
            }
            catch (StackOverflowError e) {
                System.out.println("Error: " + e);
            }
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nMergesort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            try {
                Sort.mergesort(A, 0, A.length - 1);
            }
            catch (StackOverflowError e) {
                System.out.println("Error: " + e);
            }
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBucket Sort - best case");
        for (int size : sizes) {
            float[] A = new float[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i / (float) A.length;
            }

            long t1 = System.nanoTime();
            Sort.bucketSort(A, 32);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBucket Sort - worst case");
        for (int size : sizes) {
            float[] A = new float[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = (A.length - i - 1) / (float) A.length;
            }

            long t1 = System.nanoTime();
            Sort.bucketSort(A, 32);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nBucket Sort - average case");
        for (int size : sizes) {
            float[] A = new float[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextFloat();
            }

            long t1 = System.nanoTime();
            Sort.bucketSort(A, 32);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nRadix Sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = i;
            }

            long t1 = System.nanoTime();
            Sort.radixSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nRadix Sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = A.length - i;
            }

            long t1 = System.nanoTime();
            Sort.radixSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nRadix Sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = Math.abs(random.nextInt());
            }

            long t1 = System.nanoTime();
            Sort.radixSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nArrays.sort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            Arrays.parallelSort(A);
            long t1 = System.nanoTime();
            Arrays.sort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nArrays.sort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            int[] B = Arrays.stream(A).boxed().sorted(Collections.reverseOrder()).
                    mapToInt(Integer::intValue).toArray();

            long t1 = System.nanoTime();
            Arrays.sort(B);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nArrays.sort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Arrays.sort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nArrays.parallelSort - best case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            Arrays.parallelSort(A);
            long t1 = System.nanoTime();
            Arrays.parallelSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nArrays.parallelSort - worst case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            int[] B = Arrays.stream(A).boxed().sorted(Collections.reverseOrder()).
                    mapToInt(Integer::intValue).toArray();

            long t1 = System.nanoTime();
            Arrays.parallelSort(B);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        System.out.println("\nArrays.parallelSort - average case");
        for (int size : sizes) {
            int[] A = new int[size];

            for (int i = 0; i < A.length; i++) {
                A[i] = random.nextInt();
            }

            long t1 = System.nanoTime();
            Arrays.parallelSort(A);
            long t2 = System.nanoTime();

            System.out.println(printNumber(size) + " " + printNumber(t2 - t1) + " nanoseconds");
        }

        long time2 = System.nanoTime();

        System.out.println("\nTotal time: " + ((time2 - time1) / 1e9) + " seconds");
    }

    public static String printNumber(double value)
    {
        DecimalFormat df = new DecimalFormat("###,###,###");
        return df.format(value);
    }
}