Выбор Сортировки синхронизация

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; выполненных заказов зависит от порядка.