Сортировка — это процесс упорядочивания информации по определенному признаку.
Цель сортировки — облегчение последующего поиска элементов. Существует большое количество методов сортировки и, соответственно, алгоритмов их реализации, которые имеют свои достоинства и недостатки. При выборе алгоритма, реализующего определенный метод, следует выполнить анализ его производительности в определенных условиях .
В качестве оценки производительности метода обычно используют функциональную зависимость времени работы программы от размерности исходного массива t(n). При анализе алгоритма в первую очередь интерес представляет характер зависимости при достаточно большой размерности массива (n).
В программировании порядок зависимости времени выполнения программы, реализующей некоторый метод, от размерности исходных данных n называют вычислительной сложностью данного метода.
Вычислительная сложность O(const) означает, что время решения задачи данным методом не зависит от размерности, O(n) — время работы пропорционально размерности задачи, O(n2) — время работы пропорционально квадрату размерности задачи и т.д.
Временную сложность можно оценивать, используя в качестве единицы измерения временные единицы (мкс, с и т.д.), а можно - используя время выполнения основных, характеризующих процесс операций, количество которых соответствует количеству итераций цикла, например, операций сравнения, операций пересылки. Время выполнения этих операций можно считать постоянным. Следовательно, функциональная зависимость выполняемых операций от размерности задачи по характеру будет совпадать с временной зависимостью.
На практике интересны методы сортировки, которые позволяют экономно использовать оперативную память, поэтому целесообразно рассматривать методы, не требующие использования дополнительных массивов. Такие методы называют прямыми.
Самыми простыми из прямых методов являются: