C/C++

Почему не существует универсального алгоритма сортировки?

Потому, что для разных задач наиболее эффективны разные сортировки. Не существует алгоритма, одинаково хорошо работающего на любых данных и на любом железе.

Если у тебя мало данных, эффективнее использовать не "быструю", а "медленную" сортировку.

Если у тебя очень много данных, которые не влезают в оперативную память (база данных) - сортировка слиянием.

Если у тебя крайне мало оперативной памяти (IoT) - пирамидальная сортировка.

Если сортируется массив, содержащий небольшое кол-во многократно повторяющихся значений - сортировка подсчётом.

Если ты реализуешь алгоритм BWT - специальная сортировка, "заточенная" под этот алгоритм (любая стандартная сортировка для BWT будет дико медленной).
СМ
Саша Мингалёв
72 192
Лучший ответ
Потому же, почему не бывает универсального автомобиля.
Между прочим, даже для умножения двух чисел существует много алгоритмов, хотя в школе учат только один. А для устного умножения, например, полезнее другой. А в Китае и Японии применяют третий - https://oyla.xyz/article/umnozenie-po-kitajski . Есть и другие...
Саша Мингалёв "Китайское умножение" и "умножение в столбик" - это не два разных алгоритма, а две разных реализации идентичного алгоритма.
мне тут давеча потребовалось кучу бумажек отсортировать в порядке возрастания номеров страниц.
не, я, конечно, в курсе, что быстрая сортировка - самая эффективная, но применить её на реальных физических объектах оказалось чертовски неудобно.
на практике оказалось, что удобнее - комбинация сортировки вставками и сортировки слиянием.
Есть простые для понятия. Есть эффективные при определенных данных.
Быстрая сортировка по сути универсальна.
А отношение к быстродействию программ стало такое, что можно хоть пузырьковой сортировать, всем плевать на потребителя, мол подождет...или у тебя мол железо слабое.
Ну начнём с того, что данные бывают разные - числовые, строковые, какие-другие и им нужны отдельные сортировки.
Ну а дальше есть 4 параметра алгоритмов сортировки, между которыми надо лавировать.
Время - это быстродействие операций. Обычно обозначается при помощи О-нотации. Тут можно почитать
Память - сколько памяти потребуется
Устойчивость - это означает, будет ли алгоритм менять положения равных элементов
Естественность - как себя алгоритм будет вести себя при уже отсортированных или частично сортированных элементах.
И в зависимости от требуемых задач и в зависимости от данных, программист выбирает алгоритм. Может быть надо как можно быстрее, может быть где-то данных много и надо память экономить.
Максик =)
Максик =)
28 652
Зачем?