Почему сортировка вставки быстрее, чем быстрая сортировка по отсортированному массиву

Question

Я сравниваю сортировку вставки с быстрой сортировкой. Я выяснил, почему qsort медленнее на почти отсортированном массиве, но я не могу понять, почему сортировка сортировки намного быстрее, и, конечно, ей все же приходится сравнивать почти столько же элементов в массиве?

Answer 1

Это зависит от нескольких факторов. Сортировка вставки будет более эффективной, чем быстрая сортировка по небольшим наборам данных. Это также зависит от реализации вашего резервного списка (LinkedList или ArrayList). Наконец, это также зависит от того, есть ли какой-либо порядок для входных данных. Например, если ваши входные данные уже отсортированы в обратном порядке, и вы используете LinkedList, сортировка вставки будет быстро разгоняться.

Answer 2

Quicksort имеет наихудший временной масштаб (O (n^2)) на уже отсортированных массивах (см. quicksort entry on Wikipedia).

В зависимости от выбора элемента поворота это может быть несколько смягчено, но в то же время наилучшим вариантом для сортировки вставки является именно предварительно отсортированный случай (у него есть O (n) временная сложность для таких входов), поэтому он будет бить quicksort для этого конкретного варианта использования.

Answer 3

Причина, по которой сортировка вставки быстрее на отсортированных или почти отсортированных массивах, заключается в том, что когда она вставляет элементы в отсортированную часть массива, ей едва ли нужно перемещать какие-либо элементы вообще. Например, если отсортированная часть массива равна 1 2, а следующий элемент - 3, он должен сделать только одно сравнение - 2 < 3 - чтобы определить, что ему не нужно перемещать 3. В результате сортировка вставки по уже отсортированному массиву линейно-временна, так как для каждого элемента требуется только одно сравнение.

Answer 4

Сортированные входы - лучший вариант для сортировки вставки (O (n)) и наихудшего случая для быстрого сортировки (O (n^2)).

Все это связано со сложностью, которая определяется числом сравнения ключей, которое является основной операцией в обоих алгоритмах.

Итак, когда вы видите алгоритм, вы обнаруживаете, что при сортировке вставки у вас есть только сравнение n, так как при вставке элемента мы сравниваем только элемент слева и его результат. С другой стороны, в случае быстрой сортировки u вам следует продолжать сравнивать свой элемент поворота со всем вашим левым элементом, а ваш тип уменьшения уменьшится на постоянный один фактор, что приведет к сравнению n^2.