Методы сортировки

  • Автор темы Milashka
  • Дата начала
Статус
Закрыто для дальнейших ответов.
M

Milashka

Гость
#1
Скажите, какие методы сортировки на С++ и VB самые быстрые?
 
D

deeka

Гость
#2
А таинственное слово "СОРТИРОВКИ" наверное, означает "Упорядочивание массивов по возрастанию (убыванию)"?
И причем тут язык?
И в смысле САМЫЕ БЫСТРЫЕ? Все зависит от реализации, размеров входного массива, показателя производительности/загруженности системы....
А вообще - самый быстрый АЛГОРИТМ СОРТИРОВКИ - так называемый алгоритм быстрой сортировки...
 
?

????

Гость
#3
В этом разделе будет рассмотрен знаменитый алгоритм «быстрой» сортировки, по праву считающийся самым быстрым среди неспециализированных алгоритмов сортировки. Для сравнения мы также рассмотрим один из алгоритмов сортировки, имеющих более низкую эффективность, но и более простых алгоритмов – сортировку вставками.
читать дальше...
 

Гость
#4
Известный факт, что теоретический предел времени сортировки - это O(N*log(N)) (естественно, в среднем).

Сортировка пузырьком (bubble sort) тратит O(N*N) времени и является примером "как не надо делать".

Быстрая сортировка (quick sort) даёт O(N*log(N)) в среднем, но на "плохих" наборах вырождается в пузырьковую. (иначе говоря, у времени работы большая дисперсия).
Как ни странно, самый плохой набор для быстрой сортировки - это уже упорядоченный массив.
Чтобы избежать такой неожиданной подлянки, прибегают к ухищрениям: например, предварительно перемешивают массив случайным образом (что занимает O(N)).

Помимо быстрой сортировки, есть и другие алгоритмы с асимптотикой O(N*log(N)).
Сортировка слиянием (merge sort) требует O(N) дополнительной памяти.
Пирамидальная сортировка (heap sort) в два раза медленнее средней скорости быстрой сортировки, однако её дисперсия незначительна.

В некоторых случаях, например, для реализации очереди с приоритетами, удобно использовать именно пирамидальную сортировку, так как добавление элемента в пирамиду (размещённую в массиве) и извлечение максимального значения из пирамиды занимает O(log N), в то время как добавление в линейно упорядоченный массив - O(N): приходится сдвигать целиком хвост массива от точки вставки.

Подробнее о сортировке - смотрите Дональда Кнута "Искусство программирования".
Алгоритмы и немного теории - есть на сайте algolist.manual.ru
Ну и поиск по ключевым словам в гугле, естественно...
 
M

Milashka

Гость
#5
Спасибо вам за столь подробное объяснение! :)
 
Статус
Закрыто для дальнейших ответов.