Выбор сортировки по времени

Question

Я написал программу быстрой сортировки, показанную ниже:

public static ArrayList<Integer> selectionSort(ArrayList<Integer> list) {
        for (int i=0; i < list.size()-1; i++) {
            int smallestElement = i;
            for (int j=i+1; j < list.size(); j++) {
                if (list.get(j) < list.get(smallestElement)) {
                    smallestElement = j;
                }
            }
            swapPosition(list, smallestElement, i);
        }

        return list;
    }

    public static void swapPosition(ArrayList<Integer> list, int first, int second) {
        Collections.swap(list, first, second);
    }

В моей основной программе я вычисляю время, необходимое программе для запуска в миллисекундах. Я создал новый ArrayList из 1000 элементов, которые уже отсортированы, и рассчитал время сценария наилучшего варианта. Затем я изменил порядок 1000 элементов, чтобы обозначить сценарий наихудшего случая, когда все элементы должны поменяться местами, но мой сценарий наихудшего случая занимает меньше времени, чем мой лучший вариант по какой-то причине. В лучшем случае ничего нельзя менять. Почему моя программа требует больше времени для запуска в лучшем случае, чем в худшем? Вот код для отдыха:

ArrayList<Integer> bestCase = new ArrayList<Integer>();
        for (int i=1; i < 1001; i++) {
            bestCase.add(i);
        }
        long startTimeBest = System.currentTimeMillis();
        selectionSort(bestCase);
        long endTimeBest = System.currentTimeMillis();
        long totalTimeBest = endTimeBest - startTimeBest;
        System.out.println("Total time of this program in the best case "
                + "scenario is: " + totalTimeBest + " millisecond(s)");

        Collections.reverse(bestCase);
        long startTimeWorst = System.currentTimeMillis();
        selectionSort(bestCase);
        long endTimeWorst = System.currentTimeMillis();
        long totalTimeWorst = endTimeWorst - startTimeWorst;
        System.out.println("Total time of this program in the worst case "
                + "scenario is: " + totalTimeWorst + " millisecond(s)");

Время для наилучшего случая составляет 16 мс, а для худшего - 4 мс. Это не имеет смысла.

Answer 1

Помимо проблем с методами тестирования, есть и другая проблема.

"Затем я изменил порядок 1000 элементов, чтобы обозначить наихудший сценарий, когда все элементы должны поменяться местами, но мой сценарий наихудшего случая занимает меньше времени, чем мой лучший случай по какой-то причине. В лучшем случае ничего не должно быть места ".

В вашей программе количество свопов (swapPosition(...) выполнено) не зависит от порядка сортировки элементов.

Номер smallestElement = j; Выполненные инструкции зависят от порядка.