Which Multiple-Criteria Sorting algorithm to use?

Lets' say we have list of items, each item has (unknown)number o开发者_运维技巧f attributes. Sorting by single attribute is a simple sort algorithm. The question is: how to sort the same list ordering by all attributes? Each attribute has a weight, so we might sort by least important attribute first and then by more important attribute using stable sort algorithm and so on, but this is clearly not efficient.

Thanks.

SORT BY A,B,C

Your comparison inside the sort will: A,B,C are in highest to lowest prioerity

• Compare Element 1's A with Element 2's A
• • If greater or less return result
• • Else Compare B
• • • If greater or less return result
• • • Else Compare C return result

This can be extrapolated to A..n criteria with a simple loop.

• For Each Criteria in list of Criteria
• • Compare Element 1's Criteria with Element 2's
• • • If greater or less return result
• • • Else continue // for clarity
• Return equal

The above both assume your Comparison function is Compare ( Element1, Element2 )

create a function f:A1xA2x..->R [i.e. give a value to each element based on the priorities and attributes]. the function is very dependent on the attributes [for example, if the attributes values are in the range (0,9) giving a value is simple: Sigma[val(i)*10^prio(i)] for each attribute i.

Iterate the list, calculate the function value, and cache this function result, and sort according to it. complexity will be O(nk+nlogn) where k is the number of attributes, n is the number of elements.

Most sort algorithms can take as an input a single comparison function, which can combine several sort criteria.

In the end, in order to be able to sort at all, there must be a single ordering relation between all elements (e.g. A is definitely ahead of element B, or vice versa, or the two are equivalent; the relation must satisfy transitive/symmetric/reflexive properties), so this implies it must be possible to sort with one pass of a sorting algorithm, given a valid comparison function.