2

Не понимаю, почему данные расположенные в массиве в случайном порядке сортируются по возрастанию дольше (в разы дольше) чем при порядке по убыванию?

Для наглядности

10
  • Зависит от алгоритма, как вы сортируете данные? 2 авг 2021 в 1:50
  • 1
    Код и метод его измерения в студию
    – tym32167
    2 авг 2021 в 2:10
  • 2
    не надо никаких ссылок никуда, добавляйте всю нужную инфомацию в вопрос.
    – tym32167
    2 авг 2021 в 2:59
  • 1
    у вас сортировка Шелла занимает 4к+ символов? Тогда у вас что то не так с алгоритмом скорее всего.
    – tym32167
    2 авг 2021 в 3:27
  • 1
    @АнатолийЛиндеманн В вопрос, не в комментарий!
    – Harry
    2 авг 2021 в 3:42

1 ответ 1

5

Внутри сортировки Шелла по выборкам должна использоваться сортировка вставками.

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

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

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

К адаптивным сортировкам относятся также natural merge sort (не обычно применяемый вариант), Timsort. А практически не зависят от упорядоченности данных сортировка выбором, быстрая, кучей.

Ещё у вас используется не слишком хорошая последовательность размеров шагов с делением их пополам. Да, дедушка Шелл так делал (у него были степени двойки), но с тех пор показали, что правильный выбор шагов существенно влияет.

2
  • Большое спасибо за объяснение. Если резюмировать написанное Вами, получается это нормально, что сортировка случайно расположенных данных занимает больше времени? 2 авг 2021 в 14:43
  • 1
    Да, для данного алгоритма.
    – MBo
    2 авг 2021 в 15:04

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.