Анализ алгоритма сортировки по списку из 0 и 1 элемента.

Сортировка слиянием — это забывчивый алгоритм, то есть он будет выполнять одни и те же шаги (за исключением тех, которые участвуют в слиянии) для каждой входной последовательности, поэтому его среднее и наихудшее время будут$\Theta(n\log n)$на входах, ограниченных$0/1$последовательности.

Сортировка вставками становится интересной для ваших входных данных, но нетрудно заметить, что время выполнения в худшем случае все равно будет$O(n^2)$: Посмотрите на количество свопов, которые нужно будет сделать на входе$\langle\; 1, 0, 1, 0, \dots , 1, 0\;\rangle$. Средняя производительность, как обычно, более сложная, и я не готов претендовать на какие-либо результаты за это.

Быстрая сортировка еще более интересна, так как первый вызов partition оставит массив в отсортированном порядке после$O(n)$свопы. Если бы QS был написан с учетом этого, то его поведение изменилось бы с$O(n\log n)$в среднем (или$O(n^2)$в худшем случае)$O(n)$. Если бы этот факт не был выявлен, то после первого разбиения последующие разбивали бы каждый подмассив на две части, одна из которых содержала бы один элемент, а другая — все остальные, что приводило бы к$O(n^2)$производительность как в среднем, так и в худшем случае.

Ой! Я только что заметил, что heapsort также был в вашем списке. Я должен вернуться к вам по этому поводу.

Лучший случай = данные уже отсортированы Средний случай = некоторые данные отсортированы, некоторые данные не отсортированы. Худший случай = данные полностью не отсортированы

Сортировка слиянием: Лучшее = NlogN , AVE=NlogN, ХУДШЕЕ = NlogN

Сортировка вставками = Лучший = N , AVE=N^2, ХУДШИЙ = N^2

Быстрая сортировка = NlogN , AVE=NlogN, ХУДШЕЕ = N^2