Почему алгоритм сортировки вставками работает лучше чем выборкой? Они же оба O(n^2),но разница существенная?
-
На чем вы это тестировали ? На сколько оптимально написан код обоих сортировок, на котором проводили тестирование. Большинство достаточно быстрых сортировок очень чувствительны к входным данным. На одних данных они работают отлично, на других могут тормозить. А что касается "O", это очень примерная величина выражаемая в сферических операциях в вакууме. А с точки зрения процессора даже выборка из массива 0-го элемента и 1-го может занимать разное время, если один из их есть в кеше на момент старта инструкии, а другого нет– MikeCommented 12 дек. 2017 в 8:02
-
2И на ваш вопрос, в таком виде как он сейчас, ответить невозможно. Дьявол как известно, в деталях. Надо видеть конкретные реализации обоих алгоритмов что бы хоть что то можно было сказать– MikeCommented 12 дек. 2017 в 8:03
Добавить комментарий
|
1 ответ
Например для частично упорядоченных массивов внутренний цикл сортировки вставками выполнятся гораздо меньшее кол-во раз. Отсюда и линейная сложность у него для наилучшего случая - а когда весь массив уже упорядочен в нужном порядке внутренний цикл вобще ни одного раза не выполнится ...
В то время как сор-ка выборкой на всех входных данных делает одно и тоже кол-во итераций с квадратичной сложностью.
-
-
@Atai Nnno если считаете что это отвечает на ваш вопрос то нажмите на галочку снизу чтобы принять ответ– ampawdCommented 13 дек. 2017 в 8:26