Статьи

Все, что вам нужно знать о быстрой сортировке

Май 3, 2019
Было бы верно сказать, что Quicksort является одним из самых популярных алгоритмов сортировки. Вы можете найти его реализованным на большинстве языков, и он присутствует практически в любой базовой библиотеке. В Java и Go Quicksort является алгоритмом сортировки по умолчанию для некоторых типов данных, и он используется в C ++ STL ( Introsoft, который используется там, начинается с Quicksort). Такая популярность объясняется тем, что в среднем Quicksort является одним из самых быстрых известных алгоритмов сортировки. Интересно, что сложность Quicksort не меньше, чем для других алгоритмов, таких как MergeSort или HeapSort. Наилучшая производительность — O (nlogn), а в худшем — O (n ^ 2). Последнее, к счастью, является исключительным случаем для правильной реализации. Производительность быстрой сортировки достигается основным циклом, который имеет тенденцию к превосходному использованию кэшей процессора. Еще одна причина популярности заключается в том, что для этого не требуется выделение дополнительной памяти.
Лично для меня Quicksort оказался одним из самых сложных алгоритмов сортировки. Основная идея довольно проста и обычно занимает всего несколько минут. Но эта версия, конечно, если практически не используется. Когда дело доходит до деталей и эффективности, это становится все более и более сложным.
Quicksort был впервые обнаружен CAR Hoare в 1962 году (см. «Quicksort», Computer Journal 5, 1, 1962), и в последующие годы алгоритм немного мутировал. Наиболее известной версией является трехсторонняя быстрая сортировка. Наиболее полным из широко известных из них является Dual-Pivot Quicksort. Оба алгоритма будут рассмотрены в этом посте.
Язык Java использовался для реализации всех алгоритмов. Этот пост не претендует на адекватный анализ производительности. Тестовые данные, используемые для сравнения производительности, являются неполными и используются только для демонстрации определенных методов оптимизации. Кроме того, реализации алгоритма не обязательно являются оптимальными. Просто имейте это в виду, пока вы читаете.

основы

Базовая версия Quicksort довольно проста и может быть реализована всего несколькими строками кода:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void basicQuickSort(long arr[], int beginIdx, int len) {
    if ( len <= 1 )
         return;
     
    final int endIdx = beginIdx+len-1;
 
    // Pivot selection
    final int pivotPos = beginIdx+len/2;
    final long pivot = arr[pivotPos];
    Utils.swap(arr, pivotPos, endIdx);
 
    // partitioning
    int p = beginIdx;
    for(int i = beginIdx; i != endIdx; ++i) {
         if ( arr[i] <= pivot ) {
             Utils.swap(arr, i, p++);
         }
     }
     Utils.swap(arr, p, endIdx);
 
     // recursive call
     basicQuickSort(arr, beginIdx, p-beginIdx);
     basicQuickSort(arr, p+1,  endIdx-p);
}

Код выглядит довольно простым и легко читаемым. Выбор сводки тривиален и не требует каких-либо объяснений. Процесс разделения можно проиллюстрировать с помощью следующего рисунка:

указатель «i» перемещается от начала к концу массива (обратите внимание, что последний элемент массива пропущен — мы знаем, что это стержень). Если i-й элемент равен «<= pivot», то i-й и p-й элементы меняются местами, и указатель «p» перемещается на следующий элемент. Когда разделение закончено, массив будет выглядеть так:
Помните, что в коде в конце массива есть элемент со значением pivot, и этот элемент исключается из цикла pivoting. Этот элемент помещается в p-ю позицию, что делает p-й элемент включенным в область «<= 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
public static void basicQuickSort(long arr[], int beginIdx, int len) {
    if ( len <= 1 )
        return;
  
    final int endIdx = beginIdx + len - 1;
    final int pivotIdx = getPivotIdx(arr, beginIdx, len);
    final long pivot = arr[pivotIdx];
 
    Utils.swap(arr, pivotIdx, endIdx);
    int p = partition(arr, beginIdx, len, pivot);
    Utils.swap(arr, p, endIdx);
 
    basicQuickSort(arr, beginIdx, p-beginIdx);
    basicQuickSort(arr, p+1,  endIdx-p);
} 
 
public static int partition(long[] arr, int beginIdx, int len, long pivot) {
     final int endIdx = beginIdx + len - 1;
     int p = beginIdx;
     for(int i = beginIdx; i != endIdx; ++i) {
         if ( arr[i] <= pivot ) {
             Utils.swap(arr, i, p++);        
         }    
     }    
     return p;
}
 
public static int getPivotIdx(long arr[], int beginIdx, int len) {
     return beginIdx+len/2;
}

Теперь давайте посмотрим, как он выполняет алгоритм сортировки Java 1.6. Для теста я сгенерирую массив, используя следующий цикл:

1
2
3
4
5
6
7
8
static Random rnd = new Random();
private static long[] generateData() {
   long arr[] = new long[5000000];
   for(int i = 0; i != arr.length; ++i) {
       arr[i] = rnd.nextInt(arr.length);
   }
   return arr;
}

Затем я запускаю каждый JDK 6 Arrays.sort () и basicQuickSort () по 30 раз и в качестве результата взял среднее время выполнения. Новый набор случайных данных был создан для каждого запуска. Результат этого упражнения:

обр [я] = rnd.nextInt (arr.length)
Java 6 Arrays.sort 1654ms
basicQuickSort 1431ms

Не так уж плохо. Теперь посмотрим, что произойдет, если во входных данных есть еще несколько повторяющихся элементов. Чтобы сгенерировать эти данные, я просто разделил аргумент nextInt () на 100:

обр [я] = rnd.nextInt (arr.length) обр [я] = rnd.nextInt (arr.length / 100)
Java 6 Arrays.sort 1654ms 935ms
basicQuickSort 1431ms 2570ms
Это очень плохо. Очевидно, что простой алгоритм не ведет себя хорошо в таких случаях. Можно предположить, что проблема заключается в качестве центра. Худший возможный стержень — это самый большой или самый маленький элемент массива. В этом случае алгоритм будет иметь сложность O (n ^ 2). В идеале должен быть выбран круг, так как он разбивает массив на две части с одинаковыми размерами. Это означает, что идеальный стержень является медианой для всех значений данного массива. Практически это не очень хорошая идея — слишком медленно. Поэтому обычно для реализации используется медиана из 3-5 элементов. Решение о количестве элементов, используемых для сводки, может быть основано на размере секционированного массива. Код для выбора сводки может выглядеть так:
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
public static int getPivotIdx(long arr[], int beginIdx, int len) {
   if ( len <= 512 ) {
       int p1 = beginIdx;
       int p2 = beginIdx+(len>>>1);
       int p3 = beginIdx+len-1;
 
       if ( arr[p1] > arr[p2] ) { int tmp = p1; p1 = p2; p2 = tmp; }
       if ( arr[p2] > arr[p3] ) { p2 = p3; }
       if ( arr[p1] > arr[p2] ) { p2 = p1; }
 
       return p2;
   } else {
       int p1 = beginIdx+(len/4);
       int p2 = beginIdx+(len>>1);
       int p3 = beginIdx+(len-len/4);
       int p4 = beginIdx;
       int p5 = beginIdx+len-1;
 
       if ( arr[p1] > arr[p2] ) { int tmp = p1; p1 = p2; p2 = tmp; }
       if ( arr[p2] > arr[p3] ) { int tmp = p2; p2 = p3; p3 = tmp; }
       if ( arr[p1] > arr[p2] ) { int tmp = p1; p1 = p2; p2 = tmp; }
       if ( arr[p3] > arr[p4] ) { int tmp = p3; p3 = p4; p4 = tmp; }
       if ( arr[p2] > arr[p3] ) { int tmp = p2; p2 = p3; p3 = tmp; }
       if ( arr[p1] > arr[p2] ) { p2 = p1; }
       if ( arr[p4] > arr[p5] ) { p4 = p5; }
       if ( arr[p3] > arr[p4] ) { p3 = p4; }
       if ( arr[p2] > arr[p3] ) { p3 = p2; }
       return p3;
   }
}

Вот результаты после улучшений в стратегии выбора сводных данных:

обр [я] = rnd.nextInt (arr.length) обр [я] = rnd.nextInt (arr.length / 100)
Java 6 Arrays.sort 1654ms 935ms
basicQuickSort 1431ms 2570ms
basicQuickSort с «лучшей» опорой 1365ms 2482ms
К сожалению, улучшение почти ничего. Оказалось, что выбор оси не является основной причиной проблемы. Но все же давайте сохраним, это не вредит, даже немного помогает. Это также значительно снижает вероятность поведения O (n ^ 2). Другим подозреваемым является сам алгоритм. Кажется, это не достаточно хорошо. Очевидно, это не очень хорошо работает, когда в коллекции есть повторяющиеся элементы. Поэтому что-то должно быть изменено.
Трехстороннее разделение
Способ обойти эту проблему — трехстороннее разбиение. В результате такого разделения элементы, равные оси вращения, помещаются в середину массива. Элементы, которые больше, чем шарнир, помещаются в правой части массива, а элементы, которые меньше в левой части, соответственно.
Реализация этого метода разделения состоит из двух этапов. На первом этапе массивы сканируются двумя указателями («i» и «j»), которые приближаются в противоположных направлениях. Элементы, равные 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
public static long partition(long[] arr, int beginIdx, int endIdx, long pivot) {
   int i = beginIdx-1;
   int l = i;
   int j = endIdx+1;
   int r = j;
   while ( true ) {
       while(arr[++i] <> pivot){}
 
       if ( i >= j )
           break;
 
       Utils.swap(arr, i, j);
       if ( arr[i] == pivot ) {
           Utils.swap(arr, i, ++l);
       }
       if ( arr[j] == pivot ) {
           Utils.swap(arr, j, --r);
       }
   }
   // if i == j then arr[i] == arr[j] == pivot
   if ( i == j ) {
       ++i;
       --j;
   }
 
   final int lLen = j-l;
   final int rLen = r-i;
 
   final int pLen = l-beginIdx;
   final int exchp = pLen > lLen ? lLen: pLen;
   int pidx = beginIdx;
   for(int s = 0; s <= exchp; ++s) {
         Utils.swap(arr, pidx++, j--);
   }
   final int qLen = endIdx-r;
   final int exchq = rLen > qLen ? qLen : rLen;
   int qidx = endIdx;
   for(int s = 0; s <= exchq; ++s) {
         Utils.swap(arr, qidx--, i++);
   }
 
   return (((long)lLen)<<32)|rlen;
}

Выбор точки поворота также должен быть изменен, но, скорее, для удобства идея остается абсолютно неизменной. Теперь он возвращает фактическое значение pivot, а не index:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
public static long getPivot(long arr[], int beginIdx, int len) {
   if ( len <= 512 ) {
       long p1 = arr[beginIdx];
       long p2 = arr[beginIdx+(len>>1)];
       long p3 = arr[beginIdx+len-1];
 
       return getMedian(p1, p2, p3);
   } else {
       long p1 = arr[beginIdx+(len/4)];
       long p2 = arr[beginIdx+(len>>1)];
       long p3 = arr[beginIdx+(len-len/4)];
       long p4 = arr[beginIdx];
       long p5 = arr[beginIdx+len-1];
 
       return getMedian(p1, p2, p3, p4, p5);
   }
}

И вот основной метод, который также немного изменился:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
public static void threeWayQuickSort(long[] arr, int beginIdx, int len) {
    if ( len < 2 )
        return;
 
    final int endIdx = beginIdx+len-1;
    final long pivot = getPivot(arr, beginIdx, len);
    final long lengths = threeWayPartitioning(arr, beginIdx, endIdx, pivot);
 
    final int lLen = (int)(lengths>>32);
    final int rLen = (int)lengths;
 
    threeWayQuickSort(arr, beginIdx, lLen);
    threeWayQuickSort(arr, endIdx-rLen+1, rLen);
}

теперь давайте сравним это с Java 6 sort:

обр [я] = rnd.nextInt (arr.length) обр [я] = rnd.nextInt (arr.length / 100)
Java 6 Arrays.sort 1654ms 935ms
basicQuickSort 1431ms 2570ms
basicQuickSort с «лучшей» опорой 1365ms 2482ms
Трехстороннее разбиение Quicksort 1330ms 829ms
Да, впечатляет! Это быстрее, чем стандартная библиотека, которая, кстати, реализует тот же алгоритм. Честно говоря, я был удивлен, когда обнаружил, что побить стандартную библиотеку — такая простая задача.
Но как насчет того, чтобы сделать это еще быстрее? Есть одна хитрость, которая всегда помогает, и она работает для всех алгоритмов сортировки, которые работают с последовательной памятью. Этот трюк типа вставки . Несмотря на большие шансы O (n ^ 2), он очень эффективен для небольших массивов и всегда дает некоторые улучшения производительности. Особенно это заметно, когда входные данные не отсортированы и повторных элементов не так много. Все, что вам нужно сделать, это просто добавить его в начале метода сортировки:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
public static void threeWayQuickSort(long[] arr, int beginIdx, int len) {
    if ( len < 2 )
        return;
 
    if ( len < 17 ) {
        InsertionSort.sort(arr, beginIdx, len);
        return;
    }
 
    final int endIdx = beginIdx+len-1;
    final long pivot = getPivot(arr, beginIdx, len);
    final long lengths = threeWayPartitioning(arr, beginIdx, endIdx, pivot);
 
    final int lLen = (int)(lengths>>32);
    final int rLen = (int)lengths;
 
   threeWayQuickSort(arr, beginIdx, lLen);
   threeWayQuickSort(arr, endIdx-rLen+1, rLen);
}

и снова запустите тест:

обр [я] = rnd.nextInt (arr.length) обр [я] = rnd.nextInt (arr.length / 100)
Java 6 Arrays.sort 1654ms 935ms
basicQuickSort 1431ms 2570ms
basicQuickSort с «лучшей» опорой 1365ms 2482ms
Трехстороннее разбиение Quicksort 1330ms 829ms
Трехстороннее разбиение Quicksort с сортировкой Insertion 1155ms 818ms

теперь стандартная библиотека выглядит просто ужасно. Похоже, теперь все сказано и сделано. Но на самом деле это еще не конец истории, и есть о чем поговорить.

Двойной поворот Quicksort

Двигаясь вперед, я обнаружил, что Java 7 намного более продвинута и работает намного быстрее, чем версия Java 6, и превосходит все предыдущие тесты:

обр [я] = rnd.nextInt (arr.length) обр [я] = rnd.nextInt (arr.length / 100)
Java 6 Arrays.sort 1654ms 935ms
Java 7 Arrays.sort 951ms 764ms
basicQuickSort 1431ms 2570ms
basicQuickSort с «лучшей» опорой 1365ms 2482ms
Трехстороннее разбиение Quicksort 1330ms 829ms
Трехстороннее разбиение Quicksort с сортировкой Insertion 1155ms 818ms
После нескольких секунд очень захватывающего исследования было обнаружено, что Java 7 использует новую версию алгоритма Quicksort, которая была открыта только в 2009 году Владимиром Ярославским и получила название Dual-Pivot QuickSort . Интересно, что после некоторого поиска в интернете я нашел алгоритм под названием «Многократная сортировка сводов», который был опубликован в 2007 году. Это похоже на общий случай «Двойной сводной сортировки », где возможно иметь любое количество сводок.
Как вы можете заметить из названия, основное отличие этого алгоритма состоит в том, что он использует два стержня вместо одного. Кодирование сейчас становится еще сложнее. Простейшая версия этого алгоритма может выглядеть так:
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
public static void dualPivotQuicksort(long arr[], int beginIdx, int len) {
    if ( len < 2 )
        return;
 
    final int endIdx = beginIdx+len-1;
 
    long pivot1 = arr[beginIdx];
    long pivot2 = arr[endIdx];
 
    if ( pivot1 == pivot2 ) {
        final long lengths = QuickSort.threeWayPartitioning(arr, beginIdx, endIdx, pivot1);
        final int lLen = (int)(lengths>>32);
        final int rLen = (int)lengths;
 
        dualPivotQuicksort3(arr, beginIdx, lLen);
        dualPivotQuicksort3(arr, endIdx-rLen+1, rLen);
    } else {
        if ( pivot1 > pivot2 ) {
            long tmp = pivot1;
            pivot1 = pivot2;
            pivot2 = tmp;
            Utils.swap(arr, beginIdx, endIdx);
        }
 
        int l = beginIdx;
        int r = endIdx;
        int p = beginIdx;
 
        while ( p <= r ) {
            if ( arr[p] < pivot1 ) {
                Utils.swap(arr, l++, p++);
            } else if ( arr[p] > pivot2 ) {
                while ( arr[r] > pivot2 && r > p ) {
                    --r;
                }
                Utils.swap(arr, r--, p);
            } else {
                ++p;
            }
        }
        if ( arr[l] == pivot1 ) ++l;
        if ( arr[r] == pivot2 ) --r;
 
        dualPivotQuicksort3(arr, beginIdx, l-beginIdx);
        dualPivotQuicksort3(arr, l, r-l+1);
        dualPivotQuicksort3(arr, r+1, endIdx-r);
    }
}

Первый код поднимает два центра. Если стержни одинаковы, это означает, что у нас есть только один стержень, и в этом случае мы можем использовать трехсторонний метод для разбиения. Если стержни разные, то процесс разбиения будет выглядеть так:

Сканирующий указатель «p» движется от начала массива. Если текущим элементом является «<> pivot1», то r-й элемент заменяется на p-й, а указатель «r» перемещается к следующему элементу назад. Все останавливается, когда «р» становится меньше, чем «р». После разбиения массив будет выглядеть так:

Когда раздел закончен, алгоритмы вызываются рекурсивно для каждого раздела.
Читатель не должен ожидать хорошей производительности от предоставленного кода, он не быстрый и работает даже хуже, чем Java 6 Arrays.sort. Мне предоставили только для иллюстрации концепции.
Честно говоря, я не смог заставить свою реализацию работать лучше, чем версия из Java 7. Должен признать, что Ярослав проделал там очень хорошую работу. Поэтому я не думаю, что есть смысл подробно обсуждать здесь мою реализацию.
Но, если кто-то хочет оспорить версию Java 7, я могу указать некоторые направления для оптимизации. Во-первых, что кажется очевидным? это основной выбор. Еще одно простое улучшение — сортировка вставок в начале. Кроме того, я заметил, что этот алгоритм очень чувствителен к встраиванию, поэтому есть смысл встроить Utils.swap (). В качестве другого варианта вы можете решить, что средняя секция и переместить элементы, равные pivot1 или pivot2, в их конечные позиции, что исключит их из дальнейшей сортировки. Я обнаружил, что он эффективен для относительно (<= 512 элементов) небольших массивов. Вы также можете взглянуть на исходный код Java 7 и попытаться реализовать некоторые приемы. Будьте готовы потратить много времени 🙂 В целом видно, что с годами сортировка становится все лучше и лучше. И это утверждение относится не только к быстрой сортировке. Другие алгоритмы сортировки также улучшаются. В качестве примеров можно рассмотреть Introsoft или Timsort . Однако было бы правдой сказать, что с 1960-х по 1980-е годы в этой области не было обнаружено ничего нового. Надеюсь, нам повезет увидеть что-то совершенно новое и радикальное в будущем.
Для тех, кто хочет копать глубже, в качестве отправной точки, я бы предложил посетить следующие ссылки:
Ссылка: Все, что вам нужно знать о QuickSort от нашего партнера JCG Станислава Кобылянского в блоге Стаса .
40
Share: