Проверка скорости выполнения различных сортировок

test_sorts

package TEST;

import sun.reflect.generics.tree.Tree;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class qSort {
    static Random rand = new Random();

    public static void main(String[] args) {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int n = 1;
        while (true) {
            System.out.println("Введите число - размер массива:");
            try {
                n = Integer.parseInt(r.readLine());
                break;
            }
            catch (NumberFormatException e) {
                System.out.println("Ошибка! Введенные данные не являются числом.");
            }
            catch (Exception e) {
                System.out.println("Неизвестная ошибка!");
                System.exit(-1);
            }
        }

        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            array[i] = rand.nextInt();
        }
        int[] array1;
        array1 = array.clone();

        int[] array2;
        array2 = array.clone();

        int[] array3;
        array3 = array.clone();

        System.out.println("Список массива до сортировки:");
        for (int i = 0; i < array2.length - 1; i++) {
            System.out.print(array2[i] + ", ");
        }
        System.out.println(array2[array2.length - 1]);
//Украшательства :)
        System.out.print("Сортируем ");
//        for (int i = 0; i < 5; i++) {
//            try {
//                Thread.sleep(300);
//            }
//            catch (Exception e) {
//                System.out.println(e);
//            }
//            System.out.print(". ");
//        }
//        System.out.println("\n");


        long start = System.nanoTime();
        quickSort(array, 0, array.length - 1);
        long end = System.nanoTime();

        long start1 = System.nanoTime();
        bubbleSort(array1, 0, array1.length - 1);
        long end1 = System.nanoTime();

        long start2 = System.nanoTime();
        quickSortOptimize(array2, 0, array.length - 1);
        long end2 = System.nanoTime();

        long start3 = System.nanoTime();
        combSort(array3, 0, array3.length - 1);
        long end3 = System.nanoTime();


        System.out.println("Список массива после сортировки:");
        for (int i = 0; i < array3.length - 1; i++) {
            System.out.print(array3[i] + ", ");
        }
        System.out.println(array[array3.length - 1]);

        System.out.println("");
        //WARNING! Дальше говнокод.
        HashMap <String, Long> map = new HashMap<String, Long>();
        long time = end - start;
        long time1 = end1 - start1;
        long time2 = end2 - start2;
        long time3 = end3 - start3;

        map.put("ВРЕМЯ БЫСТРОЙ СОРТИРОВКИ: ",time);
        map.put("ВРЕМЯ ПУЗЫРЬКОВОЙ СОРТИРОВКИ: ",time1);
        map.put("ВРЕМЯ ОПТИМИЗИРОВАННОЙ СОРТИРОВКИ: ",time2);
        map.put("ВРЕМЯ СОРТИРОВКИ РАСЧЕСКОЙ: ",time3);

        List<Map.Entry<String, Long>> entries = new ArrayList<Map.Entry<String, Long>>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<String, Long>>() {
            @Override
            public int compare(Map.Entry<String, Long> e1, Map.Entry<String, Long> e2) {
                long v1 = e1.getValue();
                long v2 = e2.getValue();
                return (v1 > v2) ? 1 : (v1 == v2) ? 0 : -1;
            }
        });
        for (Map.Entry<String, Long> e : entries) {
            System.out.println(e.getKey()+e.getValue()+" наносекунд!");
        }

    }



//БЫСТРАЯ СОРТИРОВКА
    public static void quickSort(int[] array, int l, int r) {
//Индекс элемента массива начала сортировки:
        int i = l;
//Индекс элемента массива конца сортировки:
        int j = r;
//Вычисление "среднего" элемента для сравнения:
        int x = array[l + (r - l) / 2]; //Здесь причина ошибки StackOverflowError, используйте этот вариант
//      int x = array[(l+r)/2];
//      int x = array[l + rand.nextInt(r - l + 1)];        //Этот вариант медленнее в ~ 1.74 раза верхнего
//Крутим цикл, пока i<=j, если иначе, то элементы массива уже рассортированы относительно элемента x:
        while (i <= j) {
//Идем по массиву от начала (i) до "середины" (x) и ищем элемент, который меньше середины.
//Как только нашли - приостанавливаемся и получаем индек i большего элемента чем x.
//Его нужно перенести правее середины.
            while (array[i] < x) {
                i++;
            }
//Аналогично предыдущему шагу идем от конца (j) до "середины". Ищем индекс нужного элемента.
            while (array[j] > x) {
                j--;
            }
//Если i<=j, т.е. если наш индекс не зашел на другую сторону (в противном случае сортировка
//относительно "середины" (x) окончена.
            if (i <= j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
// ОТОБРАЖЕНИЕ ИТЕРАЦИЙ:
//            for (int t : array) System.out.print(t+", ");
//            System.out.println("");
        }
// Если j не дошел до начала (l) сортируемого участка, то сортируем рекурсивно тем же методом участок левее j:
        if (l < j) {
            quickSort(array, l, j);
        }
// Если i не дошел до конца (r) сортируемого участка, то сортируем рекурсивно тем же методом участок правее i:
        if (i < r) {
            quickSort(array, i, r);
        }
        // Если оба оператора - false - массив отсортирован!
    }


// ПУЗЫРЬКОВАЯ СОРТИРОВКА
    public static void bubbleSort(int[] array, int start, int end) {
        int er;
        while (true) {
            er = 0;
            for (int j = start; j < end; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;

//если есть элементы не попорядку, то прибавляем единицу к er
                    er++;
                }
            }
            if (er == 0) break; //если нет неотсортированных элементов, то прирываем сортировку
            end--;
        }
    }


//КОМБИНИРОВАННАЯ СОРТИРОВКА С БЫСТРАЯ+ПУЗЫРЕК
    public static void quickSortOptimize(int[] array, int l, int r) {
//Индекс элемента массива начала сортировки:
        int i = l;
//Индекс элемента массива конца сортировки:
        int j = r;
//Вычисление "среднего" элемента для сравнения:
        int x = array[l + (r - l) / 2]; //Здесь причина ошибки StackOverflowError, используйте этот вариант
//      int x = array[(l+r)/2];
//      int x = array[l + rand.nextInt(r - l + 1)];        //Этот вариант медленнее в ~ 1.74 раза верхнего
//Крутим цикл, пока i<=j, если иначе, то элементы массива уже рассортированы относительно элемента x:
        while (i <= j) {
//Идем по массиву от начала (i) до "середины" (x) и ищем элемент, который меньше середины.
//Как только нашли - приостанавливаемся и получаем индек i большего элемента чем x.
//Его нужно перенести правее середины.
            while (array[i] < x) {
                i++;
            }
// Аналогично предыдущему шагу идем от конца (j) до "середины". Ищем индекс нужного элемента.
            while (array[j] > x) {
                j--;
            }
//Если i<=j, т.е. если наш индекс не зашел на другую сторону (в противном случае сортировка
//относительно "середины" (x) окончена.
            if (i <= j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
                i++;
                j--;
            }
//ОТОБРАЖЕНИЕ ИТЕРАЦИЙ:
//            for (int t : array) System.out.print(t+", ");
//            System.out.println("");
        }
        if (l < j && (j-l)<=7) {
            bubbleSort(array, l, j);
            j=l;
        }
//Если j не дошел до начала (l) сортируемого участка, то сортируем рекурсивно тем же методом участок левее j:
        else if (l < j) {
            quickSort(array, l, j);
        }
//Если i не дошел до конца (r) сортируемого участка, то сортируем рекурсивно тем же методом участок правее i:
        if (i < r && (r-i)<=7) {
        bubbleSort(array, i, r);
            i=r;
    }
        else if (i < r) {
            quickSort(array, i, r);
        }
// Если оба оператора - false - массив отсортирован!
    }


//СОРТИРОВКА РАСЧЕСКОЙ
    public static void combSort(int[] array, int start, int end) {
        int j;
        double step = end/1.247;
        while (true) {
            j=start+(int)step-1;
            if (j==start) break;
            for (int i = start; j < end; i++) {
                if (array[i]>array[j]) {
                    int t = array[i];
                    array[i] = array[j];
                    array [j] = t;
                }
                j++;
            }
            step/=1.247;
        }
    }
}