Теоретические сведения. Сортировка (Sorting) – это упорядочение элементов списка по какому-либо критерию

Сортировка (Sorting) – это упорядочение элементов списка по какому-либо критерию.

В качестве критерия сортировки могут выступать как числа, так и другие показатели. Например, символы, слова, биты и т.д. Критерии сортировки часто называют ключами (key).

Все алгоритмы сортировки оцениваются по вычислительной сложности и по затратам оперативной памяти компьютера.

Вычислительная сложность – это время, необходимое для выполнения алгоритма сортировки. Она оценивается в зависимости от количества исходных данных и их начального состояния с учетом затрат времени как на перестановку элементов, так и на их сравнение друг с другом.

Затраты памяти – это дополнительный объем физической памяти компьютера, необходимой для выполнения алгоритма сортировки. При оценке этого показателя не учитывается место, которое занимает исходный массив данных, и независящие от исходных данных затраты на реализацию алгоритма, например, на хранение кода программы.

Алгоритмы сортировки, которые не требуют дополнительных затрат памяти, называются сортировкой на месте.

В зависимости от сферы применения алгоритмы сортировки бывают:

1. Внутренняя сортировка – оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любому элементу. Данные обычно упорядочиваются на том же месте, без дополнительных затрат памяти.

2. Внешняя сортировка – оперирует с данными, которые расположены на периферийных устройствах с последовательным доступом. Например, сортировка в файлах, дисках, флеш-накопителях. Невозможность произвольного доступа к любому элементу из-за большого объема данных, которые нельзя поместить в оперативной памяти компьютера, накладывает некоторые дополнительные ограничения на алгоритмы и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

Кроме этих показателей используют и другие характеристики алгоритмов сортировок:

Устойчивость (Stability) – отсутствие перестановок равных элементов.

Естественность – повышение эффективности алгоритма при обработке уже упорядоченных, или частично упорядоченных данных.

Сравнимость – наличие только операций сравнений элементов друг с другом, без дополнительной информации о них. Существуют более эффективные алгоритмы для определенных типов данных, которые используют не только сравнения элементов. Например, блочная или карманная сортировка (Bucket sort).

На практике чаще всего используют алгоритмы внутренней сортировки на месте.