3

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

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

1 ответ 1

1

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

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

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

Ваш ответ

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

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