Какой метод сортировки является самым быстрым для уже отсортированных данных?

Question

Какой метод сортировки будет самым быстрым, когда список уже отсортирован? Все алгоритмы сортировки, такие как: [1] сортировка по пузырькам, [2] измененная сортировка по пузырькам и [3] сортировка по вставкам в лучшем случае, будут выполняться при O (n). Так что они должны быть одинаково быстрыми. Когда я пытаюсь решить проблему сортировки примеров, я вижу, что все они действительно работают за O (n). Затем я увидел график, что сортировка вставки будет быстрее, чем две другие (это здесь: https://www.toptal.com/developers/sorting-algorithms/nearly-sorted-initial-order). Мне интересно, правда ли это для уже отсортированных данных, как, например, list = 1, 2, 3, 4? Я думаю,они одинаково быстры - я прав?

Спасибо за помощь!

Answer 1

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

Если вам нужны доказательства, вы можете выписать пузырьковую сортировку / измененную сортировку пузырьков / сортировку вставок, а затем посмотреть, что произойдет в случае, когда ничего не нужно сортировать.

РЕДАКТИРОВАТЬ:

Также, как вы сказали, это, вероятно, модифицированная пузырьковая сортировка. (Больше всего похоже на базовую сортировку? Проверьте)

Какой алгоритм сортировки лучше всего работает с сортированными данными в основном? .

Подобный вопрос здесь.