Почему сортировка при случайном порядке данных дольше чем при порядке по убыванию?
Не понимаю, почему данные расположенные в массиве в случайном порядке сортируются по возрастанию дольше (в разы дольше) чем при порядке по убыванию?
Ответы (1 шт):
Внутри сортировки Шелла по выборкам должна использоваться сортировка вставками.
Последняя является адаптивной - т.е. для уже сортированных данных она выполняет меньше операций, чем для случайных. Поэтому на сортированном наборе работать как вставки, так и Шелл должны быстрее.
Надо заметить, что у вас вместо вставок используется какая-то экзотика, похожая не то на пузырёк, не то на гномью сортировку. Последние тоже являются адаптивными, и на сортированных данных будут быстрее.
Указанные вложенные сортировки сортируют убывающий массив долго, однако для сортировки Шелла характерно то, что упорядочение выборок очень быстро приводит к тому, что элементы быстро приходят близко к своей финальной позиции, а для таких массивов скорость вставок и пр. очень хорошая. Полный анализ сортировки Шелла, насколько я знаю, до сих пор не сделан.
К адаптивным сортировкам относятся также natural merge sort (не обычно применяемый вариант), Timsort. А практически не зависят от упорядоченности данных сортировка выбором, быстрая, кучей.
Ещё у вас используется не слишком хорошая последовательность размеров шагов с делением их пополам. Да, дедушка Шелл так делал (у него были степени двойки), но с тех пор показали, что правильный выбор шагов существенно влияет.