3

Почему алгоритм сортировки вставками работает лучше чем выборкой? Они же оба O(n^2),но разница существенная?

2
  • На чем вы это тестировали ? На сколько оптимально написан код обоих сортировок, на котором проводили тестирование. Большинство достаточно быстрых сортировок очень чувствительны к входным данным. На одних данных они работают отлично, на других могут тормозить. А что касается "O", это очень примерная величина выражаемая в сферических операциях в вакууме. А с точки зрения процессора даже выборка из массива 0-го элемента и 1-го может занимать разное время, если один из их есть в кеше на момент старта инструкии, а другого нет
    – Mike
    Commented 12 дек. 2017 в 8:02
  • 2
    И на ваш вопрос, в таком виде как он сейчас, ответить невозможно. Дьявол как известно, в деталях. Надо видеть конкретные реализации обоих алгоритмов что бы хоть что то можно было сказать
    – Mike
    Commented 12 дек. 2017 в 8:03

1 ответ 1

1

Например для частично упорядоченных массивов внутренний цикл сортировки вставками выполнятся гораздо меньшее кол-во раз. Отсюда и линейная сложность у него для наилучшего случая - а когда весь массив уже упорядочен в нужном порядке внутренний цикл вобще ни одного раза не выполнится ...

В то время как сор-ка выборкой на всех входных данных делает одно и тоже кол-во итераций с квадратичной сложностью.

2
  • Спасибо большое
    – Atai Nnno
    Commented 13 дек. 2017 в 2:03
  • @Atai Nnno если считаете что это отвечает на ваш вопрос то нажмите на галочку снизу чтобы принять ответ
    – ampawd
    Commented 13 дек. 2017 в 8:26

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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