Группировка быстрее сортировки
От: PlushBeaver  
Дата: 13.08.21 20:04
Оценка:
Задача: дан массив длиной N из объектов, у которых есть признак-целое число; нужно получить группы объектов, у которых значения признака равны.

Очевидно, задача решаема сортировкой. Но задумался, может ли в принципе быть более быстрое решение за счет того, что порядок групп и объектов в группе не задан наперед. Последнее, например, позволяет использовать нестабильные сортировки. Эквивалентна ли эта задача сортировке? Я вижу отличие в том, что ключ сортировки не задан наперед, а выбирается алгоритмом. Например, пусть есть массив [a, a, b, b]. Если использовать сортировку и присвоить ключи a=10, b=20, то перестановок не нужно, а если a=20, b=10, то нужны. С другой стороны, у выбора ключей есть какая-то сложность, и можно сказать, что ключи зависят от всего массива.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.