|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
18.06.2014, 12:47 | #1 |
Регистрация: 01.11.2012
Сообщений: 4
|
Какой алгоритм сортировки сравнениями признается лучшим и наиболее эффективным?
1. Сортировка вставками
2. Сортировка деревом 3. Сортировка слиянием 4. Сортировка Шелла 5. Быстрая сортировка Хоара |
18.06.2014, 16:01 | #2 |
C++, Java
Старожил
Регистрация: 10.04.2010
Сообщений: 2,665
|
Определить, насколько сортировка хороша(необязательно сортировка - любой алгоритм), можно оценив её временную сложность в наихудшем и среднем случаях в О-символике.
В данном случае ситуация такова: 1) Сортировка вставками - простая в реализации и понимании, но плохая с точки зрения сложности. O(N^2) 2) Сортировка двоичным деревом(если это то, что вы имели в виду) - не такая уж и простая в реализации(в смысле для новичка). На относительно "хороших" наборах данных сложность O(N * log(N)). Проблема в том, что "хорошие" наборы данных случаются не часто и общая сложность этого алгоритма O(N^2). Однако, если использовать самобалансирующиеся деревья, то сложность будет O(N * log(N)). 3) Сортировка слиянием - относительно простая в понимании, с очень хорошей гарантированной сложностью O(N * log(N)). 4) Сортировка Шелла - несколько изменённая сортировка вставками. Стандартная сложность - O(N^2), при различных реализациях - O(N^(3/2)). 5) Быстрая сортировка - не совсем проста в понимании; однако, достаточно проста в реализации и имеет хорошую сложность в среднем случае - O(N * log(N)), однако при стандартной реализации можно подобрать такие наборы входных данных, когда её сложность будет O(N^2), т.е. намного хуже. Существует ещё много всяких различных сортировок, таких как пирамидальная сортировка, и т.д. Выбирать вам. Если не знаете, что такое сложность алгоритма: грубо говоря, это функция, выражающая зависимость количества операций, которые будут выполнены алгоритмом от количества входных данных. Очевидно, что при больших значениях N значение N * log(N) много меньше, чем N^2. Ну и ещё: наилучшая достижимая сложность алгоритмов сортировок с помощью сравнений - O(N * log(N)). |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Оптимальный алгоритм - получить список из N наиболее часто встречающихся элементов | vedro-compota | Общие вопросы по программированию, компьютерный форум | 34 | 09.12.2012 13:11 |
Алгоритм поиска наиболее подходящих | LynXzp | Общие вопросы C/C++ | 18 | 06.12.2012 01:20 |
Какой язык программирования наиболее перспективен? | Ms.Burns | Помощь студентам | 5 | 19.04.2008 21:27 |
Какой из языков программирования наиболее гибкий? | LAN | Свободное общение | 15 | 07.11.2007 14:35 |
Какой из языков программирования наиболее жёсткий? | JTG | Свободное общение | 10 | 07.11.2007 14:30 |