Наблюдение за квадратичным поведением с быстрой сортировкой - O (n ^ 2)

Question

Алгоритм быстрой сортировки имеет среднюю временную сложность O (n * log (n)) и сложность наихудшего случая O (n ^ 2).

Если предположить какой-либо вариант алгоритма быстрой сортировки Хоара, какие виды ввода приведут к тому, что алгоритм быстрой сортировки будет демонстрировать сложность наихудшего случая?

Пожалуйста, укажите любые предположения, относящиеся к деталям реализации, относящимся к конкретному алгоритму быстрой сортировки, такому как выбор сводной области и т. Д., Или если он получен из общедоступной библиотеки, такой как libc.

Некоторые читают:

1. Убийца-противник для быстрой сортировки
2. Быстрая сортировка оптимальна
3. Разработка функции сортировки
4. Алгоритмы интроспективной сортировки и выбора

Answer 1

Быстрая сортировка работает хуже всего, т. Е. При O (n ^ 2), когда все значения выбранной сводной точки являются либо самыми большими, либо самыми маленькими из взятого набора.Рассмотрим этот пример.

1 2 3 4 5

Выбранная опорная точка, скажем, 1, у вас будет 4 элемента с правой стороны от оси, а с левой стороны нет элементов.Применяя эту же логику рекурсивно и шарнирный выбрали, 2, 3, 4, 5, соответственно, мы достигли такой ситуации, когда такого рода была выполнена на его самый неподходящий момент.

1008 * Было рекомендовано и доказано, что Quicksort выполняетхорошо, если вход хорошо перемешан.

Кроме того, выбор вида обычно зависит от четких знаний о входной области.Например, если ввод огромен, то есть нечто, называемое внешней сортировкой, которое может использовать внешнюю память.Если входной размер очень мал, мы можем пойти на сортировку слиянием, но не для средних и огромных входных наборов, так как она использует дополнительную память.Основное преимущество быстрой сортировки заключается в ее значении «на месте», поскольку для входных данных не используется дополнительная память.Его худшее время на бумаге - O (n ^ 2), но все еще широко предпочитается и используется.Моя точка зрения заключается в том, что алгоритмы сортировки могут быть изменены на основе знаний о входном наборе и его предпочтениях.

Answer 2

Чтобы расширить то, что сказал Брэгбой, вместо того, чтобы только бежать:

quicksort(array);

Выполнить:

shuffle(array);
quicksort(array);

Где определение shuffle() может быть:

shuffle(array){
    for(int i = array.length; i > 0; i--){
        r= random number % i;
        swap(array[i], array[r]);
    }
}

Это, вероятно, будет иметь дело со случаем получения ввода, который замедляет quicksort().

Answer 3

Алгоритм быстрой сортировки Хоара выбирает случайный шарнир. Для воспроизводимых результатов я бы предложил модификацию Скоуэна, которая, среди прочего, выбирает средний элемент из входных данных. Для этого варианта наихудший случай - пилообразный паттерн с наименьшей точкой поворота:

starting with           {  j   i   h   g   f   a   e   d   c   b  }
compare 1 to 6          { (j)  i   h   g   f  (a)  e   d   c   b  }
compare 6 to 10         {  j   i   h   g   f  (a)  e   d   c  (b) }
compare 6 to 9          {  j   i   h   g   f  (a)  e   d  (c)  b  }
compare 6 to 8          {  j   i   h   g   f  (a)  e  (d)  c   b  }
compare 6 to 7          {  j   i   h   g   f  (a) (e)  d   c   b  }
swap 1<=>6              { (a)  i   h   g   f  (j)  e   d   c   b  }
compare 1 to 5          { (a)  i   h   g  (f)  j   e   d   c   b  }
compare 1 to 4          { (a)  i   h  (g)  f   j   e   d   c   b  }
compare 1 to 3          { (a)  i  (h)  g   f   j   e   d   c   b  }
compare 1 to 2          { (a) (i)  h   g   f   j   e   d   c   b  }
compare 2 to 6          {  a  (i)  h   g   f  (j)  e   d   c   b  }
compare 3 to 6          {  a   i  (h)  g   f  (j)  e   d   c   b  }
compare 4 to 6          {  a   i   h  (g)  f  (j)  e   d   c   b  }
compare 5 to 6          {  a   i   h   g  (f) (j)  e   d   c   b  }
compare and swap 6<=>10 {  a   i   h   g   f  (b)  e   d   c  (j) }
compare 7 to 10         {  a   i   h   g   f   b  (e)  d   c  (j) }
compare 8 to 10         {  a   i   h   g   f   b   e  (d)  c  (j) }
compare 9 to 10         {  a   i   h   g   f   b   e   d  (c) (j) }
compare 2 to 6          {  a  (i)  h   g   f  (b)  e   d   c   j  }
compare 6 to 9          {  a   i   h   g   f  (b)  e   d  (c)  j  }
compare 6 to 8          {  a   i   h   g   f  (b)  e  (d)  c   j  }
compare 6 to 7          {  a   i   h   g   f  (b) (e)  d   c   j  }
swap 2<=>6              {  a  (b)  h   g   f  (i)  e   d   c   j  }
compare 2 to 5          {  a  (b)  h   g  (f)  i   e   d   c   j  }
compare 2 to 4          {  a  (b)  h  (g)  f   i   e   d   c   j  }
compare 2 to 3          {  a  (b) (h)  g   f   i   e   d   c   j  }
compare 3 to 6          {  a   b  (h)  g   f  (i)  e   d   c   j  }
compare 4 to 6          {  a   b   h  (g)  f  (i)  e   d   c   j  }
compare 5 to 6          {  a   b   h   g  (f) (i)  e   d   c   j  }
compare and swap 6<=>9  {  a   b   h   g   f  (c)  e   d  (i)  j  }
compare 7 to 9          {  a   b   h   g   f   c  (e)  d  (i)  j  }
compare 8 to 9          {  a   b   h   g   f   c   e  (d) (i)  j  }
compare 3 to 6          {  a   b  (h)  g   f  (c)  e   d   i   j  }
compare 6 to 8          {  a   b   h   g   f  (c)  e  (d)  i   j  }
compare 6 to 7          {  a   b   h   g   f  (c) (e)  d   i   j  }
swap 3<=>6              {  a   b  (c)  g   f  (h)  e   d   i   j  }
compare 3 to 5          {  a   b  (c)  g  (f)  h   e   d   i   j  }
compare 3 to 4          {  a   b  (c) (g)  f   h   e   d   i   j  }
compare 4 to 6          {  a   b   c  (g)  f  (h)  e   d   i   j  }
compare 5 to 6          {  a   b   c   g  (f) (h)  e   d   i   j  }
compare and swap 6<=>8  {  a   b   c   g   f  (d)  e  (h)  i   j  }
compare 7 to 8          {  a   b   c   g   f   d  (e) (h)  i   j  }
compare 4 to 6          {  a   b   c  (g)  f  (d)  e   h   i   j  }
compare 6 to 7          {  a   b   c   g   f  (d) (e)  h   i   j  }
swap 4<=>6              {  a   b   c  (d)  f  (g)  e   h   i   j  }
compare 4 to 5          {  a   b   c  (d) (f)  g   e   h   i   j  }
compare 5 to 6          {  a   b   c   d  (f) (g)  e   h   i   j  }
compare and swap 6<=>7  {  a   b   c   d   f  (e) (g)  h   i   j  }
compare and swap 5<=>6  {  a   b   c   d  (e) (f)  g   h   i   j  }