Введение - Сравнительный анализ времен сортировок

Используемые в настоящее время объемы данных достигают размеров, которые еще десятилетие назад казались почти невероятными. Чем большими становятся объемы перерабатываемых данных, тем актуальнее становится задача оптимизации используемых алгоритмов, в том числе и сортировки.

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

Целью проведенного исследования было сравнение времен наиболее распространенных алгоритмов сортировки данных в массивах.

Теоретическая часть

Алгоритм сортировки - это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки.

Важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

Рассмотрим методы сортировки:

    - пузырек; - отбор; - вставка; - Шелл; - быстрая.

Похожие статьи




Введение - Сравнительный анализ времен сортировок

Предыдущая | Следующая