Оценка скорости сортировки.
Случайный массив:
Таблица времени исполнения алгоритмов:
Перестановки элементов: Сравнения элементов:
Самый быстрый метод – Вставка, и с ростом количества элементов его преимущество только увеличивается, т.к. он выполняет меньше всего сравнений элементов.
Отсортированный массив:
Перестановки элементов: Сравнения элементов:
В данных условиях метод Вставки снова быстрее всех. Это объясняется тем, что в уже упорядоченном массиве он делает только N перестановок и N сравнений, в то время, как остальные алгоритмы сильно проигрывают ему по какому-то из этих двух параметров.
Метод Простого Выбора сильно отстал в производительности, т.к. его скорость не зависит от степени отсортированности исходного массива, он всегда выполняет N перестановок и N^2 сравнений. Обратноотсортированный массив:
Перестановки элементов: Сравнения элементов:
В данном случае метод Вставки и метод Простого Выбора лидируют и оказываются одинаково эффективны. Это объясняется тем, что на обатноотсортированном массиве алгоритм Вставки выполняет больше перестановок, чем алгоритм Простого выбора, но при этом меньше сравнений.
|
Таблица времени исполнения алгоритмов:
Таблица времени исполнения алгоритмов:
