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

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. Оба из них требуют времени. Но сортировка вставки будет проходить по списку один раз и обнаруживать, что это сделано. Это самый быстрый для этого случая.

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