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 Сравнение методов:
-
Автоматизация -
Гидрология -
Документоведение, делопроизводство -
Информационные системы -
Коммуникации -
Криптография -
Машиностроение -
Метрология -
Механика -
Микроэлектроника -
Нефтегазовое дело -
Пищевая промышленность -
Приборостроение -
Программирование -
Системный анализ, управление и обработка информации -
Строительство -
Технология и оборудование механической и физико-технической обработки -
Электрическая энергия -
Энергетика -
-
Архитектура и строительство -
Безопасность жизнедеятельности -
Библиотечное дело -
Бизнес -
Биология -
Военные дисциплины -
География -
Геология -
Демография -
Диссертации России -
Естествознание -
Журналистика и СМИ -
Информатика, вычислительная техника и управление -
Искусствоведение -
История -
Культурология -
Литература -
Маркетинг -
Математика -
Медицина -
Менеджмент -
Педагогика -
Политология -
Право России -
Право України -
Промышленность -
Психология -
Реклама -
Религиоведение -
Социология -
Страхование -
Технические науки -
Учебный процесс -
Физика -
Философия -
Финансы -
Химия -
Художественные науки -
Экология -
Экономика -
Энергетика -
Юриспруденция -
Языкознание -