12

Lets' say we have list of items, each item has (unknown)number of 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.

Improve this question

3 Answers 3

Reset to default
15 
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 )

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

this is also O(knlogn), where k is the number of attributes and n is the number of elements, same bound as simply sorting k times.
the problem with this is that one criteria , A, has infinitely more weight than everything else. Say student is good at math, and i'm looking to have someone join my robotics team. But that students sucks in ethics, professionalisim, coding, have drug problems and more, but because math is starting important factor algo will suggest the best student is this at least he will be in top students
@MuhammadUmer - you want a scoring algorithm not a sorting algorithm. So, you'd want to generate a score for each student based on what you'd deem admirable, then you would sort by just that score.
9

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.

Improve this answer

4 Comments

prio(i) is the priority of the i'th attribute, where i=0 is least important in this example.
hey! I just saw your answer(in 2 years late..).. and I trying to understand it for almost two days.. Can you try to explain the algorithm or to link me to some reference?
@AlmogBaku I am currently traveling. please recomment in 10 days to remind me and i'll explain better.
@AlmogBaku The idea is basically to give a numeric value to each attribute such that the importance of the attribute is dominant in the number itself. For example, if you have object with 3 attributes, a,b,c such that a is most dominant and c is least dominant, and each is in range[0,9] you can give it the value val(a)*100 + val(b) * 10 + val(c). So if you have an object with a=3,b=0,c=9, you get a number of 309. Now, you can sort according to this number with regular sorting algorithm all objects.
1

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.

Improve this answer

2 Comments

This is also O(knlogn) worst case, [k is the number of attributes and n is the number of elements] since you need to check k elements in each comparison. same bound as sorting k times with stable algorithm.
true, and performance will probably be better then sorting k times, since you won't need all k comparisons for all elements, just pointing it will be asymptotically the same [at least for worst case analyzis]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.