Квадратичное поведение во время выполнения Java Quicksort

Question

Я попытался реализовать эффективный алгоритм сортировки в Java. По этой причине, я также осуществил быструю сортировку и использовать следующий код:

public class Sorting { 
    private static Random prng; 

    private static Random getPrng() { 
     if (prng == null) { 
      prng = new Random(); 
     } 
     return prng; 
    } 

    public static void sort(int[] array) { 
     sortInternal(array, 0, array.length - 1); 
    } 

    public static void sortInternal(int[] array, int start, int end) { 
     if (end - start < 50) { 
      insertionSortInternal(array, start, end); 
     } else { 
      quickSortInternal(array, start, end); 
     } 
    } 

    private static void insertionSortInternal(int[] array, int start, int end) { 
     for (int i=start; i<end - 1; ++i) { 
      for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--) { 
       ArrayUtilities.swap(array, ptr, ptr - 1); 
      } 
     } 
    } 

    private static void quickSortInternal(int[] array, int start, int end) { 
     int pivotPos = getPrng().nextInt(end - start); 
     int pivot = array[start + pivotPos]; 
     ArrayUtilities.swap(array, start + pivotPos, end - 1); 
     int left = start; 
     int right = end - 2; 
     while (left < right) { 
      while (array[left] <= pivot && left < right) { 
       ++left; 
      } 
      if (left == right) break; 
      while (array[right] >= pivot && left < right) { 
       right--; 
      } 
      if (left == right) break; 
      ArrayUtilities.swap(array, left, right); 
     } 
     ArrayUtilities.swap(array, left, end - 1); 
     sortInternal(array, start, left); 
     sortInternal(array, left + 1, end); 
    } 
} 

ArrayUtilities.swap просто обменивает два данных элементов в массиве. Из этого кода я ожидаю O(n log(n)) времени выполнения. Но, некоторые различные длины массивов для сортировки дал следующие результаты:

10000 элементов: 32 мс

20000 элементов: 128мс

30000 элементов: 296ms

тест побежал в 100 раз, в каждом случае , а затем вычислялось среднее арифметическое времени работы. Но ясно, что в отличие от ожидаемого поведения время выполнения составляет O(n^2). Что случилось с моим алгоритмом?

Answer 1

В вашей реализации сортировки вставки ваш массив будет отсортирован в порядке убывания, а в вашем быстром сортировке массив сортируется в порядке возрастания. Так замените (для порядка убывания):

for (int ptr=i; ptr>0 && array[ptr - 1] < array[ptr]; ptr--) 

с

for (int ptr=i; ptr>0 && array[ptr - 1] > array[ptr]; ptr--) 

Это также кажется, что ваша индексация не является правильной. Попробуйте заменить:

sortInternal(array, 0, array.length - 1); 

с:

sortInternal(array, 0, array.length); 

И в вставках рода первый цикл вам не нужно делать end - 1, то есть использование:

for (int i=start; i<end; ++i) 

Наконец, добавьте if (start >= end) return; в начале метода быстрой сортировки.

И как @ljeabmreosn упоминалось, 50 немного слишком большой, я бы выбрал что-то между 5 и 20.

Надежда, что помогает!

Answer 2

QuickSort «оптимизирован» с вставкой Сортировка для массивов длиной менее 50 элементов, по-видимому, является проблемой.

Представьте себе, что у меня был массив размером 65, а стержень оказался медианным из этого массива. Если бы я запустил массив через ваш код, ваш код будет использовать Insertion Sort на двух 32-строчных подмассивах слева и справа от оси. Это привело бы к среднему случаю ~ O (2 * (n/2)^2 + n) = ~ O (n^2). Используя быструю сортировку и реализацию a pivot picking strategy для первого поворота, средний временной интервал будет ~ O ((n log (n)) + n) = ~ O (n (log (n) + 1)) = ~ O (п * журнала (п)). Не используйте Insertion Sort, поскольку он используется только тогда, когда массив почти отсортирован. Если вы используете сортировку вставки только из-за реального времени работы сортировки, то малые массивы могут работать быстрее, чем стандартный алгоритм быстрой сортировки (глубокая рекурсия), вы всегда можете использовать нерекурсивный алгоритм быстрой сортировки, который работает быстрее, чем Insertion Sort.

Возможно, измените значение «50» на «20» и соблюдайте результаты.