Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.06.2014, 12:47   #1
bayanist17
 
Регистрация: 01.11.2012
Сообщений: 4
По умолчанию Какой алгоритм сортировки сравнениями признается лучшим и наиболее эффективным?

1. Сортировка вставками
2. Сортировка деревом
3. Сортировка слиянием
4. Сортировка Шелла
5. Быстрая сортировка Хоара
bayanist17 вне форума Ответить с цитированием
Старый 18.06.2014, 16:01   #2
_-Re@l-_
C++, Java
Старожил
 
Аватар для _-Re@l-_
 
Регистрация: 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)).
_-Re@l-_ вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимальный алгоритм - получить список из 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