Внутренняя сортировка

Общие понятия

Сортировку следует понимать как процесс перегруппировкой однотипных элементов структуры данных в некотором определенном порядке. Цель сортировки — облегчить последующий поиск, обновление, исключение, включение элементов в структуру данных. На отсортированных данных легче определить имеются ли пропущенные элементы, все ли элементы проверены, легче найти общие элементы двух однотипных структур слить их воедино. Сортировка является важным средством для ускорения работы практически любого алгоритма, в которой требуется частое обращение к определенным элементам структуры данных.

Разработано множество алгоритмов сортировки, однако нет алгоритма, который был бы наилучшим в любом случае. Эффективность алгоритма сортировки может зависеть от ряда факторов, таких, как: число сортируемых элементов; диапазон и распределение значений сортируемых элементов; степень отсортированности элементов; характеристики алгоритма (сложность требования к памяти и т.п.); место размещения элементов (в оперативной памяти или на ВЗУ).

В зависимости от последнего фактора все методы сортировки разбивают на два класса: внутренняя сортировка (сортировка массивов) и внешняя сортировка (сортировка файлов, или сортировка последовательностей).

Сортируемые элементы часто представляют собой записи данных определенной структуры. Каждая запись имеет поле ключа по значению которого осуществляется сортировка, и поля данных При рассмотрении алгоритмов сортировки нас интересует только поле ключа, поэтому другие поля опускаются из рассмотрения.

Метод сортировки называется устойчивым, если в процессе сортировки относительное расположение элементов с одинаковыми (равными) ключами не изменяется. Устойчивость сортировки желательна, если речь идет об элементах, уже отсортированных по некоторым другим ключам (свойствам), не влияющим на ключ, по которому сейчас осуществляется сортировка.

Основными требованиями к алгоритмам сортировки, как и ко всяким алгоритмам, являются требования по памяти и по времени выполнения. Это предполагает, что сортировка элементов массива выполняется на месте, без передачи их в результирующий массив. Хорошей мерой эффективности алгоритма по времени могут быть число необходимых сравнений ключей С и число пересылок М, которые зависят от числа элементов п.

Самыми простыми методами сортировки являются так называемые прямые методы, они требуют порядка О(п²) сравнений ключей. Быстрые (улучшенные) методы сортировки в самом благоприятном случае требуют порядка O (n * 1оg2n) сравнений, имеются многочисленные варианты прямых и быстрых методов сортировки.

Прямые методы сортировки, не требующие дополнительной памяти, можно разбить на три категории:

• сортировка методом прямого включения;

• сортировка методом прямого выбора;

• сортировка методом прямого обмена (сортировка методом пузырька).

Быстрые методы сортировки являются улучшением прямых методов сортировки.

Дата добавления: 2017-01-14