На этой статье я хочу закончить разбирать алгоритмы сортировки (на какое-то время) и уже приступить к другим типам алгоритмов.
Но перед этим подведем сравнительный итог по изученному.
Как оценивают алгоритмы? Во всех статьях мы разбирали работу алгоритмов в худшем случае, но в реальных задачах нам попадаются совершенно разные данные, в том числе полностью или частично отсортированные. Отсюда возникает необходимость оценки для разных случаев:
- В худшем случае – когда входной массив данных отсортирован в обратном порядке
- В лучшем случае – когда входной массив отсортирован в нужном порядке
- В среднем случае – когда данные во входном массиве случайно перемешаны
Расчет сложности для случаев отличных от худшего ведется по аналогии с тем как это проводилось в статьях о конкретной сортировке.
Конечно же для наглядности сведем всё к красивой таблице:
Существует еще множество различных алгоритмов сортировки и их модификаций. В дальнейшем я обязательно к ним еще вернусь и опишу их, но для тех, кто не хочет ждать вот небольшой список некоторых из них:
1. Гномья сортировка
2. Гребневая сортировка
3. Шейкерная сортировка
4. Сортировка Шелла
5. Поразрядная сортировка