Почему вставка сортировки быстрее, чем быстрая сортировка и пузырьковая сортировка для небольших случаев?

Question

Недавно я прочитал статью о сложности вычислений в алгоритмах. Автор упомянул "почему сортировка вставок быстрее, чем быстрая сортировка и сортировка по пузырькам для небольших случаев". Кто-нибудь может объяснить это?

Кто-нибудь знает реальную сложность каждого алгоритма сортировки, который я упомянул выше?

Answer 1

Рассмотрим две функции сложности:

F (X) = X ^ 2
G (X) = 4 * X * ln (X)

F (3) = 9
G (3) = 13

Таким образом, алгоритм F выигрывает за 3 позиции. Но:

F (100) = 10000
G (100) = 1842

Таким образом, алгоритм G выигрывает за 100 предметов.

Сложность сортировки вставок подобна F (X). Сложность быстрой сортировки похожа на G (X).

Answer 2

Фактическая сложность каждого алгоритма сортировки заключается в следующем:

1. Best - вставка сортировка: O(N ^ 2), O(N), O(N ^ 2)
2. Средний - Быстрый Qort: O(N ^ 2), O(N log N), O(N log N)
3. Худший - Пузырь Сортировать: O(N ^ 2), O(N), O(N ^ 2)

Answer 3

Если список уже отсортирован, то для быстрой сортировки необходимо выполнить все рекурсивные шаги, чтобы получить n списков размера 1. Оба из них требуют времени. Но сортировка вставки будет проходить по списку один раз и обнаружит, что это сделано. Это самый быстрый для этого случая.

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