- Статус
А таинственное слово "СОРТИРОВКИ" наверное, означает "Упорядочивание массивов по возрастанию (убыванию)"?
И причем тут язык?
И в смысле САМЫЕ БЫСТРЫЕ? Все зависит от реализации, размеров входного массива, показателя производительности/загруженности системы....
А вообще - самый быстрый АЛГОРИТМ СОРТИРОВКИ - так называемый алгоритм быстрой сортировки...
И причем тут язык?
И в смысле САМЫЕ БЫСТРЫЕ? Все зависит от реализации, размеров входного массива, показателя производительности/загруженности системы....
А вообще - самый быстрый АЛГОРИТМ СОРТИРОВКИ - так называемый алгоритм быстрой сортировки...
Известный факт, что теоретический предел времени сортировки - это 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): приходится сдвигать целиком хвост массива от точки вставки.
Подробнее о сортировке - смотрите Дональда Кнута "Искусство программирования".
Алгоритмы и немного теории - есть на сайте
Ну и поиск по ключевым словам в гугле, естественно...
Сортировка пузырьком (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): приходится сдвигать целиком хвост массива от точки вставки.
Подробнее о сортировке - смотрите Дональда Кнута "Искусство программирования".
Алгоритмы и немного теории - есть на сайте
Скрыто от гостей
Ну и поиск по ключевым словам в гугле, естественно...
- Статус
| Мы в соцсетях: |       |