Позволяет сказать, что у нас есть список элементов, каждый элемент имеет (неизвестное) количество атрибутов. Сортировка по одному атрибуту - простой алгоритм сортировки. Возникает вопрос: как отсортировать порядок номеров по всем атрибутам? Каждый атрибут имеет вес, поэтому мы можем сначала отсортировать наименее важный атрибут, а затем более важный атрибут, используя стабильный алгоритм сортировки и т.д., Но это явно неэффективно.
Спасибо.
создайте функцию f: A1xA2x..- > R [т.е. дать значение каждому элементу на основе приоритетов и атрибутов]. функция сильно зависит от атрибутов [например, если значения атрибутов находятся в диапазоне (0,9), давая значение просто: Sigma[val(i)*10^prio(i)] for each attribute i.
Итерировать список, вычислить значение функции и кешировать этот результат функции и отсортировать по нему. сложностью будет O (nk + nlogn), где k - количество атрибутов, n - количество элементов.
SORT BY A,B,C
Ваше сравнение внутри сортировки будет: A, B, C находятся в наивысшем до наименьшего приоритета
Это можно экстраполировать на критерии A..n с помощью простого цикла.
Вышеупомянутые оба предполагают, что ваша функция сравнения - Compare (Element1, Element2)
Большинство алгоритмов сортировки могут принимать в качестве входных данных одну функцию сравнения, которая может сочетать несколько критериев сортировки.
В конце концов, чтобы иметь возможность сортировать вообще, должно быть одно отношение упорядочения между всеми элементами (например, A определенно опережает элемент B или наоборот, или два эквивалентны; отношение должно удовлетворяют переходным/симметричным/рефлексивным свойствам), поэтому это означает, что нужно иметь возможность сортировать с одним проходом алгоритма сортировки с учетом действительной функции сравнения.