Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11634
Последний выпуск: 19.06.2015

Сравнение методов

В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации:

  • Устойчивость. Напомним, что устойчивая сортировка не меняет взаимного расположения элементов с равными ключами. Сортировка вставками - единственный из рассмотренных алгоритмов, обладающих этим свойством.
  • Память. Сортировке на месте не требуется дополнительная память. Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке требуется стек для организации рекурсии. Однако, требуемое этому алгоритму место можно сильно уменьшить, повозившись с алгоритмом.
  • Время. Время, нужное для сортировки наших данных, легко становится астрономическим (см. таблицу 1.1). Таблица 2.2 позволяет сравнить временные затраты каждого из алгоритмов по количеству исполняемых операторов. Время, затраченное каждым из алгоритмов на сортировку случайного набора данных, представлено в таблице 2.3.
  • Простота. Количество операторов, выполняемых каждым алгоритмом, приведено в таблице 2.2. Более простые алгоритмы вызывают меньше ошибок при программировании.
метод кол-во 
операторов
ср. время время для 
наихудшего 
случая
сортировка 
вставками
9 O(n2) O(n2)
сортировка 
Шелла
17 O(n1.25) O(n1.5)
быстрая 
сортировка
21 O(n lg n) O(n2)
Таблица 2.2:Сравнение методов сортировки
кол-во 
элементов
вставки Шелл quicksort
16 39 чs 45 чs 51 чs
256 4,969 чs 1,230 чs 911 чs
4,096 1.315 sec .033 sec .020 sec
65,536 416.437 sec 1.254 sec .461 sec
Таблица 2.3: Время сортировки

Оглавление

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог