Ни для кого не новость, что Quicksort считается одним из самых важных алгоритмов столетия и что это сортировка по умолчанию для многих языков, включая Arrays.sort в Java.
Итак, что нового в быстрой сортировке?
Ну, ничего, кроме того, что я понял только сейчас (после двух проклятых лет выпуска Java 7), что реализация Arrays.sort была заменена вариантом, названным Dual-Pivot QuickSort . Эта тема удивительна не только по этой причине, но и насколько скромны на самом деле Джон Бентли и Джошуа Блох.
Что я сделал дальше?
Как и все остальные, я хотел реализовать его и провести сравнительный анализ — с примерно 10 миллионами целых чисел (случайных и повторяющихся).
Как ни странно, я нашел следующие результаты:
Случайные данные:
- Быстрая сортировка Basic: 1222 миллис
- Быстрая сортировка 3 способа: 1295 миллис (серьезно!)
- Quick Sort Dual Pivot: 1066 миллис
Дубликаты данных:
- Быстрая сортировка Basic: 378 миллис
- Быстрая сортировка 3 способа: 15 миллис
- Quick Sort Dual Pivot: 6 миллис
Глупый Вопрос 1:
Я боюсь, что мне что-то не хватает при реализации 3-х стороннего раздела. Через несколько прогонов против случайных входов (из 10 миллионов) чисел, я мог видеть, что одиночный стержень всегда работает лучше (хотя разница составляет менее 100 миллисекунд для 10 миллионов чисел).
Я понимаю, что основная цель сделать трехстороннюю сортировку в качестве быстрой сортировки по умолчанию до сих пор состоит в том, что она не дает производительности 0 (n 2) для дублирующих ключей — что очень очевидно, когда я запускаю ее для дублированного ввода. Но правда ли, что ради обработки дубликатов данных, 3-х сторонний сбор небольшой штраф? Или моя реализация плохая?
Глупый вопрос 2
Моя реализация Dual Pivot (ссылка ниже) плохо обрабатывает дубликаты. Для исполнения требуется сладкое навсегда (0 (n 2)) . Есть хороший способ избежать этого? Обращаясь к реализации Arrays.sort , я выяснил, что восходящая последовательность и дубликаты удаляются задолго до того, как будет выполнена фактическая сортировка. Таким образом, как грязное исправление, если стержни равны, я ускоряю перемотку LowerIndex, пока он не станет отличным от pivot2. Это справедливая реализация?
|
1
2
3
4
5
6
|
else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } } |
Вот и все. Это все, что я сделал?
Я всегда нахожу трассировку алгоритма интересной, но с учетом количества переменных в быстрой сортировке Dual Pivot, мои глаза находили его подавляющим при отладке. Итак, я также пошел дальше и создал реализации с поддержкой трассировки (для всех 3), чтобы я мог видеть, где в данный момент находятся указатели переменных.
Эти классы с поддержкой трассировки просто накладываются, когда указатели находятся ниже значений массива. Я надеюсь, что вы найдете эти занятия полезными.
например. для итерации Dual Pivot
Весь проект (вместе с несколькими неудачными реализациями DSA) доступен на github здесь . Только классы быстрой сортировки можно найти здесь .
Вот моя реализация SinglePivot (Hoare), 3-way (Sedgewick) и нового Dual-Pivot (Yaroslavskiy)
Одиночный пивот
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
package basics.sorting.quick;import static basics.sorting.utils.SortUtils.exchange;import static basics.sorting.utils.SortUtils.less;import basics.shuffle.KnuthShuffle;public class QuickSortBasic { public void sort (int[] input){ //KnuthShuffle.shuffle(input); sort (input, 0, input.length-1); } private void sort(int[] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex){ return; } int partIndex=partition (input, lowIndex, highIndex); sort (input, lowIndex, partIndex-1); sort (input, partIndex+1, highIndex); } private int partition(int[] input, int lowIndex, int highIndex) { int i=lowIndex; int pivotIndex=lowIndex; int j=highIndex+1; 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); } exchange(input, pivotIndex, j); return j; }} |
3-полосная
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
package basics.sorting.quick;import static basics.shuffle.KnuthShuffle.shuffle;import static basics.sorting.utils.SortUtils.exchange;import static basics.sorting.utils.SortUtils.less;public class QuickSort3Way { public void sort (int[] input){ //input=shuffle(input); sort (input, 0, input.length-1); } public void sort(int[] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex) return; int lt=lowIndex; int gt=highIndex; int i=lowIndex+1; int pivotIndex=lowIndex; int pivotValue=input[pivotIndex]; while (i<=gt){ if (less(input[i],pivotValue)){ exchange(input, i++, lt++); } else if (less (pivotValue, input[i])){ exchange(input, i, gt--); } else{ i++; } } sort (input, lowIndex, lt-1); sort (input, gt+1, highIndex); }} |
Dual Pivot
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
package basics.sorting.quick;import static basics.shuffle.KnuthShuffle.shuffle;import static basics.sorting.utils.SortUtils.exchange;import static basics.sorting.utils.SortUtils.less;public class QuickSortDualPivot { public void sort (int[] input){ //input=shuffle(input); sort (input, 0, input.length-1); } private void sort(int[] input, int lowIndex, int highIndex) { if (highIndex<=lowIndex) return; int pivot1=input[lowIndex]; int pivot2=input[highIndex]; if (pivot1>pivot2){ exchange(input, lowIndex, highIndex); pivot1=input[lowIndex]; pivot2=input[highIndex]; //sort(input, lowIndex, highIndex); } else if (pivot1==pivot2){ while (pivot1==pivot2 && lowIndex<highIndex){ lowIndex++; pivot1=input[lowIndex]; } } int i=lowIndex+1; int lt=lowIndex+1; int gt=highIndex-1; while (i<=gt){ if (less(input[i], pivot1)){ exchange(input, i++, lt++); } else if (less(pivot2, input[i])){ exchange(input, i, gt--); } else{ i++; } } exchange(input, lowIndex, --lt); exchange(input, highIndex, ++gt); sort(input, lowIndex, lt-1); sort (input, lt+1, gt-1); sort(input, gt+1, highIndex); }} |