В этом разделе рассмотрим алгоритмы быстрой сортировки и сортировки слиянием, имеющих асимптотику O(n×ln(n)). Также обратим внимание на возможность использования стандартных функций языка C++, которые можно использовать для сортировки массивов.
Быстрая сортировка
Этот алгоритм является одним из самых популярных и наиболее часто используемым среди алгоритмов, имеющих порядок сложности O(n×ln(n)). Сам алгоритм является рекурсивным и его идея заключается в следующем: для сортировки массива достаточно разбить его на две части так, чтобы все элементы левой части были меньше либо равны всех элементов правой части, далее следует выполнить подобную операцию с левой и правой частью, рассматривая их как отдельные массивы. Алгоритмическое представление функции, которая сортирует подмассив с l-го по r-й элемент можно представить следующим образом:
Подробнее о быстрой сортировке можно прочитать здесь.
Сортировка слиянием
Данный алгоритм имеет рекурсивную основу и работает по принципу «разделяй и властвуй» c асимптотикой O(n×ln(n)). Основные его моменты можно описать следующими концепциями:
Сортируемый массив разбивается на две части примерно одинакового размера.
Каждая из получившихся частей сортируется отдельно, используя тот же алгоритм.
Два упорядоченных массива половинного размера соединяются в один.
Следует отметить, что данный алгоритм является устойчивым, т.е. в результате сортировки равные элементы (по критерию сравнения) не меняют своего положения относительно друг друга. Алгоритмическое представление функции, которая сортирует подмассив с l-го по r-й элемент можно представить следующим образом:
Подробнее о сортировке слиянием можно прочитать здесь.
Сортировка в C++
Для сортировки массива в большинстве случаев вовсе необязательно самостоятельно реализовывать алгоритмы сортировки. Дело в том, что многие языки программирования содержат встроенные средства сортировки данных. И язык C++ не является исключением. В библиотеке algorithm содержатся функции сортировки, которые вы можете использовать в своих программах. Так, приведем пример кода сортировки массива a[0..n-1], состоящего из n элементов на языке C++:
Следующий пример представляет собой целостный код программы на языке C++, реализующей чтение, сортировку и вывод элементов целочисленного массива:
