Быстрая сортировка В худшем случае сложность времени?

Question

Я работаю над проектом, который улучшает алгоритмы быстрой сортировки наихудшего времени. Я изменил алгоритм, выбрав срединную ось вместо крайнего левого выделения, и ввел сортировку вставки после определенного числа итераций. Результаты следующие:

Для ввода несортированных данных длиной от 5000 до 100000:

1. Количество сравнений, выполненных в моей модифицированной быстрой сортировке, намного меньше, чем количество сравнений, выполненных в обычной быстрой сортировке.
2. Истекшее время для обоих равно нулю секунд для всей длины, если данные.

Для ввода уже отсортированных данных длиной от 5000 до 100000:

1. Количество сравнений, выполненных в моей модифицированной быстрой сортировке, все еще намного меньше, чем число сравнений, выполненных в обычной быстрой сортировке.
2. Истекшее время для моей модифицированной быстрой сортировки очень меньше, чем истекшее время обычной быстрой сортировки для всей длины данных.

Как теперь я могу доказать, что временная сложность O(n^2) для уже отсортированных данных была улучшена? У меня есть все приведенные выше данные, но я не знаю, как это теоретически показать Прямых ответов нет, но с намеками все будет в порядке.

Answer 1

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

Хорошей моделью для такого анализа является рецензия Тима Питера на алгоритм Timsort : http://hg.python.org/cpython/file/2.7/Objects/listsort.txt