Эффективность прямых методов сортировки оценивается количеством необходимых элементарных операций и числом перестановок элементов в процессе сортировки. Как в среднем, так и в худшем случае, количество элементарных операций для всех прямых методов сортировки имеет порядок O(n2). Однако, если размер записи большой, то операция перестановки пары элементов местами, которая присутствует во всех алгоритмах, будет занимать больше времени, чем другие операции.
Поэтому целесообразно сравнить алгоритмы сортировки по количеству перестановок. Для алгоритмов сортировки обменами и вставками среднее число перестановок оценивается как n2/4. Сортировка выбором предполагает n-1 перестановку, что делает этот алгоритм более эффективным для наихудшего случая, когда элементы исходного массива расположены в обратном порядке.
В целом экспериментальные исследования показывают, что для случайного порядка элементов сортировка выбором по эффективности незначительно уступает сортировке простыми вставками. Однако, чем ближе массив к отсортированному виду, тем более эффективной становится сортировка простыми вставками. Алгоритм сортировки обменами является наихудшим.
В общем случае, если необходимо упорядочить длинные записи, целесообразно работать не с массивом записей, а с массивом указателей на записи. После упорядочения массива указателей сами записи можно расположить в нужном порядке за время пропорциональное этому количеству записей.
Опубликовал Kest
January 22 2010 16:34:47 ·
0 Комментариев ·
9217 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
