2.4 Сравнение методов
В данном разделе мы сравним описанные алгоритмы сортировки: вставками, Шелла и быструю сортировку. Есть несколько факторов, влияющих на выбор алгоритма в каждой конкретной ситуации: Устойчивость.
Напомним, что устойчивая сортировка не меняет взаимного расположения элементов с равными ключами. Сортировка вставками – единственный из рассмотренных алгоритмов, обладающих этим свойством. Память. Сортировке на месте не требуется дополнительная память. Сортировка вставками и Шелла удовлетворяют этому условию. Быстрой сортировке требуется стек для организации рекурсии. Однако, требуемое этому алгоритму место можно сильно уменьшить, повозившись с алгоритмом. Время. Время, нужное для сортировки наших данных, легко становится астрономическим (см. таблицу 1.1). Таблица 2.2 позволяет сравнить временные затраты каждого из алгоритмов по количеству исполняемых операторов..| Method | statements | average time | worst-case time |
| insertion sort | 9 | O(n2) | O(n2) |
| shell sort | 17 | O(n1.25) | O(n1.5) |
| quicksort | 21 | O(n lg n) | O(n2) |
Таблица 2.2:Сравнение методов сортировки Время, затраченное каждым из алгоритмов на сортировку случайного набора данных, представлено в таблице 2.3.
| count | insertion | shell | quicksort |
| 16 | 39 ms | 45 ms | 51 ms |
| 256 | 4,969 ms | 1,230 ms | 911 ms |
| 4,096 | 1.315 sec | .033 sec | .020 sec |
| 65,536 | 416.437 sec | 1.254 sec | .461 sec |
Таблица 2.3: Время сортировки
Еще по теме 2.4 Сравнение методов:
- Сравнение выгод, получаемых при переходе на метод ЛИФО с метода ФИФО и средних цен
- 3.5 Сравнение методов
- 4.1. Compare Means - простые параметрические методы сравнения средних
- 10. Для решения каких исследовательских вопросов могут быть использованы качественные методы? В каких случаях они должны быть использованы? Их достоинства и ограничения по сравнению с количественными методами.
- 2.1.4. Сравнение темпов роста доходов СЭО в сравнении с темпами роста средней заработной платы населения и инфляции.
- 1.4. Метод теории государства и права. Принципы научного познания. Общенаучные методы. Частнонаучные методы
- Экспериментальный метод – как центральный метод среди эмпирических методов психологического исследования.
- Сравнение
- 1. Понятие и значение сравнения
- 2.1.3. Эксплицитное и имплицитное сравнение
- Функциональное сравнение
- Методы психогенетических исследований. Генеалогический метод. Семейные исследования. Метод приемных детей.
- § 47. Степени сравнения
- Лабораторная работа № 9 Сравнения - ой степени по составному модулю.
-
Автоматизация -
Гидрология -
Документоведение, делопроизводство -
Информационные системы -
Коммуникации -
Криптография -
Машиностроение -
Метрология -
Механика -
Микроэлектроника -
Нефтегазовое дело -
Пищевая промышленность -
Приборостроение -
Программирование -
Системный анализ, управление и обработка информации -
Строительство -
Технология и оборудование механической и физико-технической обработки -
Электрическая энергия -
Энергетика -
-
Архитектура и строительство -
Безопасность жизнедеятельности -
Библиотечное дело -
Бизнес -
Биология -
Военные дисциплины -
География -
Геология -
Демография -
Диссертации России -
Естествознание -
Журналистика и СМИ -
Информатика, вычислительная техника и управление -
Искусствоведение -
История -
Культурология -
Литература -
Маркетинг -
Математика -
Медицина -
Менеджмент -
Педагогика -
Политология -
Право России -
Право України -
Промышленность -
Психология -
Реклама -
Религиоведение -
Социология -
Страхование -
Технические науки -
Учебный процесс -
Физика -
Философия -
Финансы -
Химия -
Художественные науки -
Экология -
Экономика -
Энергетика -
Юриспруденция -
Языкознание -