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

[Milashka]

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

 

[deeka]

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

 

[????]

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

Ссылка скрыта от гостей

 

[Guest]

Известный факт, что теоретический предел времени сортировки - это 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): приходится сдвигать целиком хвост массива от точки вставки.

Подробнее о сортировке - смотрите Дональда Кнута "Искусство программирования".
Алгоритмы и немного теории - есть на сайте

Ссылка скрыта от гостей

Ну и поиск по ключевым словам в гугле, естественно...

 

[Milashka]

Спасибо вам за столь подробное объяснение!