Является ли сортировка быстрее, чем вставка сортировки в обратных массивах?

Question

В случае, если у нас есть отсортированный по заказу массив, выбор сортировки быстрее, чем сортировка вставки?

Я думаю, что выбор сортировка быстрее, потому что мы имеем O(n^2) поиска и O(n) свопа, но в той вставке мы имеем O(n^2) подкачки и O(n^2) поиска.

Может кто-нибудь скажет мне, правильно я или нет? Спасибо

Answer 1

Я сделал некоторый бенчмаркинг по этой теме на моих собственных реализациях Python. Это зависит от того, какой тип ввода у вас есть. Я обнаружил, что Sorting Sorting немного быстрее (например, 3%) для произвольно упорядоченного ввода, но выбор сортировки намного быстрее для обратного сортированного ввода. Я всегда слышал, что Selection Sort является более быстрым из двух, но мои собственные тесты на моих реализациях не отражают этого.