Непонятка с сортировкой — почему random более плохой случай, чем decremental array?

Question

[Saboteur]

Собственно тренируюсь в java.
Написал bubble sort и quicksort, но меня удивляет такая ситуация:
Дольше всего сортируются рандомные данные.
Я предполагал, что worst case должен быть декрементальный массив (от большего к меньшему), но он сортируется быстрее, чем случайные данные.
Массив со случайными числами генерю отдельно, то есть время замеряю исправно.
Или decremental и не должен быть worst case?

Answer 1

[Mercury13]

Для пузырька убывающий массив действительно худший возможный случай, и единственное, что могу предположить,— JIT и предсказание ветвлений на уровне процессора. Ради интереса перейди на устаревшую виртуальную машину — думаю, этот случай сразу же станет худшим.

Для быстрой убывающий массив — один из лучших случаев, будет сделано ровно [n/2] обменов. Легко показать, что элементы в начале и конце массива, стоящие на своих местах, быстрая сортировка не сместит никогда. Так что первое, что сделает сортировка,— разобьёт на меньший (отсортированный) и больший (частично отсортированный как надо, частично — в обратном порядке). Ту часть, которая как надо, сортировка не тронет. А ту, которая наоборот — задействуем трансфинитную индукцию, и получаем, что ровно [n/2].

Answer 2

[uvelichitel]

Обе не особо чувствительны к данным.
Для пузырька все кейсы одинаково плохие кроме отсортированного массива. Для быстрой гораздо важнее насколько средним вы выбираете опорный элемент сравнения, чем распределение массива. Суть оптимизаций быстрой сортировки правильный выбор опорного элемента(случайный выбор считается достаточно хорошим)