Короче говоря, быстрая сортировка для сортировки массива нижнего элемента сначала работает так:
- Выберите элемент поворота
- Массив предварительной сортировки, так что все элементы, меньшие, чем сводная, находятся на левой стороне
- Рекурсивно выполните шаги 1. и 2. для левой и правой сторон
Обычно это был бы элемент сводки, который разделяет последовательность на две одинаково длинные подпоследовательности.
В настоящее время существуют разные схемы выбора элемента разворота. Ранняя версия просто заняла самый левый элемент. В худшем случае, однако, элемент поворота всегда будет w.l.o.g. самый низкий элемент.
Самый левый элемент - это стержень
В этом случае легко догадаться, что наихудший случай - это уже увеличивающийся отсортированный массив:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Самый правый элемент - это стержень
Аналогично, при выборе самого правого элемента наихудшим случаем будет убывающая последовательность.
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
Центральный элемент - это стержень
Одним из возможных средств защиты является использование центрального элемента (или немного левее центра, если последовательность имеет четную длину). В этом случае худший случай будет более экзотичным. Его можно построить, изменив алгоритм быстрой сортировки, чтобы установить элементы массива, соответствующие выбранному в данный момент элементу поворота, в монотонное возрастающее значение. То есть мы знаем, что первая ось является центром, поэтому центр должен иметь наименьшее значение, например 0. Затем он поменяется на крайний левый, то есть крайнее левое значение теперь находится в центре и будет следующим элементом поворота, поэтому оно должно быть 1, так что мы уже догадываемся, что массив будет выглядеть так:
1 ? ? 0 ? ? ?
Мы можем позволить измененной быстрой сортировке сделать все остальное. Вот код C ++:
// g++ -std=c++11 worstCaseQuicksort.cpp && ./a.out
#include <algorithm> // swap
#include <iostream>
#include <vector>
#include <numeric> // iota
int main( void )
{
std::vector<int> v(20); /**< will hold the worst case later */
/* p basically saves the indices of what was the initial position of the
* elements of v. As they get swapped around by Quicksort p becomes a
* permutation */
auto p = v;
std::iota( p.begin(), p.end(), 0 );
/* in the worst case we need to work on v.size( sequences, because
* the initial sequence is always split after the first element */
for ( auto i = 0u; i < v.size(); ++i )
{
/* i can be interpreted as:
* - subsequence starting index
* - current minimum value, if we start at 0 */
/* note thate in the last step iPivot == v.size()-1 */
auto const iPivot = ( v.size()-1 + i )/2;
v[ p[ iPivot ] ] = i;
std::swap( p[ iPivot ], p[i] );
}
for ( auto x : v ) std::cout << " " << x;
}
Мы получаем следующие наихудшие последовательности:
0
0 1
1 0 2
2 0 1 3
1 3 0 2 4
4 2 0 1 3 5
1 5 3 0 2 4 6
4 2 6 0 1 3 5 7
1 5 3 7 0 2 4 6 8
8 2 6 4 0 1 3 5 7 9
1 9 3 7 5 0 2 4 6 8 10
6 2 10 4 8 0 1 3 5 7 9 11
1 7 3 11 5 9 0 2 4 6 8 10 12
10 2 8 4 12 6 0 1 3 5 7 9 11 13
1 11 3 9 5 13 7 0 2 4 6 8 10 12 14
8 2 12 4 10 6 14 0 1 3 5 7 9 11 13 15
1 9 3 13 5 11 7 15 0 2 4 6 8 10 12 14 16
16 2 10 4 14 6 12 8 0 1 3 5 7 9 11 13 15 17
1 17 3 11 5 15 7 13 9 0 2 4 6 8 10 12 14 16 18
10 2 18 4 12 6 16 8 14 0 1 3 5 7 9 11 13 15 17 19
1 11 3 19 5 13 7 17 9 15 0 2 4 6 8 10 12 14 16 18 20
16 2 12 4 20 6 14 8 18 10 0 1 3 5 7 9 11 13 15 17 19 21
1 17 3 13 5 21 7 15 9 19 11 0 2 4 6 8 10 12 14 16 18 20 22
12 2 18 4 14 6 22 8 16 10 20 0 1 3 5 7 9 11 13 15 17 19 21 23
1 13 3 19 5 15 7 23 9 17 11 21 0 2 4 6 8 10 12 14 16 18 20 22 24
В этом есть порядок. Правая сторона - это просто приращение двух, начиная с нуля. На левой стороне также есть порядок. Давайте отформатируем левую сторону последовательности длиной в 73 элемента в худшем случае, используя Ascii art:
0 1 2 3 4 5 6 7 8 9 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
------------------------------------------------------------------------------------------------------------
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35
37 39 41 43 45 47 49 51 53
55 57 59 61 63
65 67
69
71
Заголовок - это индекс элемента. В первом ряду номера, начинающиеся с 1 и увеличивающиеся на 2, присваиваются каждому второму элементу. Во второй строке то же самое делается для каждого 4-го элемента, в 3-й строке номера присваиваются каждому 8-му элементу и так далее. В этом случае первое значение, которое будет записано в i-й строке, имеет индекс 2 ^ i-1, но для некоторых длин это выглядит несколько иначе.
Полученная структура напоминает перевернутое двоичное дерево, узлы которого помечены снизу вверх, начиная с листьев.
Медиана крайнего левого, центрального и правого элементов - это ось
Другой способ - использовать медиану левого, центрального и правого элементов. В этом случае наихудшим случаем может быть только то, что левая подпоследовательность имеет длину 2 (а не только длину 1, как в примерах выше). Также мы предполагаем, что самое правильное значение всегда будет наибольшим из медианы трех. Это также означает, что это самое высокое из всех значений. Внося коррективы в программу выше, теперь у нас есть это:
auto p = v;
std::iota( p.begin(), p.end(), 0 );
auto i = 0u;
for ( ; i < v.size(); i+=2 )
{
auto const iPivot0 = i;
auto const iPivot1 = ( i + v.size()-1 )/2;
v[ p[ iPivot1 ] ] = i+1;
v[ p[ iPivot0 ] ] = i;
std::swap( p[ iPivot1 ], p[i+1] );
}
if ( v.size() > 0 && i == v.size() )
v[ v.size()-1 ] = i-1;
Сгенерированные последовательности:
0
0 1
0 1 2
0 1 2 3
0 2 1 3 4
0 2 1 3 4 5
0 4 2 1 3 5 6
0 4 2 1 3 5 6 7
0 4 2 6 1 3 5 7 8
0 4 2 6 1 3 5 7 8 9
0 8 2 6 4 1 3 5 7 9 10
0 8 2 6 4 1 3 5 7 9 10 11
0 6 2 10 4 8 1 3 5 7 9 11 12
0 6 2 10 4 8 1 3 5 7 9 11 12 13
0 10 2 8 4 12 6 1 3 5 7 9 11 13 14
0 10 2 8 4 12 6 1 3 5 7 9 11 13 14 15
0 8 2 12 4 10 6 14 1 3 5 7 9 11 13 15 16
0 8 2 12 4 10 6 14 1 3 5 7 9 11 13 15 16 17
0 16 2 10 4 14 6 12 8 1 3 5 7 9 11 13 15 17 18
0 16 2 10 4 14 6 12 8 1 3 5 7 9 11 13 15 17 18 19
0 10 2 18 4 12 6 16 8 14 1 3 5 7 9 11 13 15 17 19 20
0 10 2 18 4 12 6 16 8 14 1 3 5 7 9 11 13 15 17 19 20 21
0 16 2 12 4 20 6 14 8 18 10 1 3 5 7 9 11 13 15 17 19 21 22
0 16 2 12 4 20 6 14 8 18 10 1 3 5 7 9 11 13 15 17 19 21 22 23
0 12 2 18 4 14 6 22 8 16 10 20 1 3 5 7 9 11 13 15 17 19 21 23 24
Псевдослучайный элемент со случайным начальным числом 0 является стержнем
Последствия в наихудшем случае для центрального элемента и медианы-трех выглядят уже довольно случайными, но для того, чтобы сделать Quicksort еще более устойчивым, элемент опоры можно выбирать случайным образом. Если используемая случайная последовательность, по крайней мере, воспроизводима при каждом запуске быстрой сортировки, то для этого мы также можем построить последовательность наихудшего случая. Нам нужно только настроить строку iPivot = в первой программе, например, чтобы:
srand(0); // you shouldn't use 0 as a seed
for ( auto i = 0u; i < v.size(); ++i )
{
auto const iPivot = i + rand() % ( v.size() - i );
Сгенерированные последовательности:
0
1 0
1 0 2
2 3 1 0
1 4 2 0 3
5 0 1 2 3 4
6 0 5 4 2 1 3
7 2 4 3 6 1 5 0
4 0 3 6 2 8 7 1 5
2 3 6 0 8 5 9 7 1 4
3 6 2 5 7 4 0 1 8 10 9
8 11 7 6 10 4 9 0 5 2 3 1
0 12 3 10 6 8 11 7 2 4 9 1 5
9 0 8 10 11 3 12 4 6 7 1 2 5 13
2 4 14 5 9 1 12 6 13 8 3 7 10 0 11
3 15 1 13 5 8 9 0 10 4 7 2 6 11 12 14
11 16 8 9 10 4 6 1 3 7 0 12 5 14 2 15 13
6 0 15 7 11 4 5 14 13 17 9 2 10 3 12 16 1 8
8 14 0 12 18 13 3 7 5 17 9 2 4 15 11 10 16 1 6
3 6 16 0 11 4 15 9 13 19 7 2 10 17 12 5 1 8 18 14
6 0 14 9 15 2 8 1 11 7 3 19 18 16 20 17 13 12 10 4 5
14 16 7 9 8 1 3 21 5 4 12 17 10 19 18 15 6 0 11 2 13 20
1 2 22 11 16 9 10 14 12 6 17 0 5 20 4 21 19 8 3 7 18 15 13
22 1 15 18 8 19 13 0 14 23 9 12 10 5 11 21 6 4 17 2 16 7 3 20
2 19 17 6 10 13 11 8 0 16 12 22 4 18 15 20 3 24 21 7 5 14 9 1 23
Так как проверить правильность этих последовательностей?
- Измерьте время, которое потребовалось для последовательностей. Время графика по длине последовательности N. Если кривая масштабируется с O (N ^ 2) вместо O (N log (N)), то это действительно наихудшие последовательности.
- Настройте правильную быструю сортировку, чтобы получить отладочную информацию о длине подпоследовательности и / или выбранных элементах разворота.Одна из подпоследовательностей всегда должна иметь длину 1 (или 2 для медианы-трех).Выбранные элементы разворота должны быть увеличены.
