Почему QuickSort Single pivot быстрее, чем трехсторонний раздел?

Question

Я пытаюсь примерно сравнить производительность QuickSorts (Single Pivot, 3-way и Dual Pivot).

Вопросы 1: Я боюсь, что у меня что-то не хватает в реализации трехстороннего раздела. За несколько прогонов против случайных входных данных (из 10 миллионов) чисел я мог видеть, что единственный стержень всегда работает лучше (хотя разница составляет где-то около 100 миллисекунд за 10 миллионов номеров).

Я понимаю, что вся цель 3-way - это не производительность 0 (n^2) на дублирующих клавишах - что очень очевидно, когда я запускаю ее для дублирования ввода. Но верно ли, что для обработки дублированных данных небольшое наказание принимается 3-сторонним? Или моя реализация плоха?

Дублирование данных:

• Быстрый Сортировать Basic: 888 Миллис
• Быстрая сортировка 3 Way: 522 Миллис
• Быстрая сортировка Dual Pivot: 482 Миллис

Случайные данные:

• Быстрые Сортировать Basic: 1677 Миллиса
• Быстрых Сортировать 3 Пути: 1717 Миллиса
• Быстрых Сортировать Dual Pivot: 1595 Миллиса

Вопрос 2:

Двойной Реализация Pivot (ссылка ниже) плохо обрабатывает дубликаты. Требуется выполнить 0 (n^2) времени. Есть хороший способ перемотки вперед. Я мог видеть, что мы можем проверить, равны ли шарниры и увеличить значение pivot1 до тех пор, пока они не будут отличаться от pivot2. Является ли это справедливой реализацией?

else if (pivot1==pivot2){ 
     while (pivot1==pivot2 && lowIndex<highIndex){ 
      lowIndex++; 
      pivot1=input[lowIndex]; 
     } 
    } 

ссылки реализации:

Корневая папка: https://github.com/arunma/dsa/tree/master/src/basics/sorting/quick

QuickSort (Single Pivot): https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortBasic.java

QuickSort (3-полосная раздела): https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSort3Way.java

QuickSort (Dual Pivot): https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortDualPivot.java

TestCase: https://github.com/arunma/dsa/blob/master/src/basics/sorting/quick/QuickSortTest.java

Answer 1

Прежде всего избавиться от Суффля в конструкторах, чтобы получить правильное сравнение.

Во-вторых, поведение, как ожидается, так как в базовой версии вы только делаете переключатель, если вы нашли подходящего кандидата в обе стороны, то есть, в QuickSortBasic.java

while (true){ 

     while (less(input[++i], input[pivotIndex])){ 
      if (i==highIndex) break; 
     } 

     while (less (input[pivotIndex], input[--j])){ 
      if (j==lowIndex) break; 
     } 

     if (i>=j) break; 

     exchange(input, i, j); 

    } 

а версия 3Way вы делают переключатель в любом случае, если элемент не равен оси, то есть в QuickSort3Way.java

while (i<=gt){ 


     if (less(input[i],pivotValue)){ 
      exchange(input, i++, lt++); 
     } 
     else if (less (pivotValue, input[i])){ 
      exchange(input, i, gt--); 
     } 
     else{ 
      i++; 
     } 


    }