1. Member
Join Date
Mar 2010
Posts
30
Rep Power
0

## Sort Logic

This isn't exactly specific to Java, but more asking for advice on the logic of a sort I'm trying to implement.

I have a list of objects that have been compared to each other. There are "Winners" and "Losers".

So my list might be something like:
A beats B
B beats C
B beats D
D beats C
E beats A

And I want to sort them, so the "best" are at the top, so in that example the list would be sorted to:
E, A, B, D, C

I'm unsure how to tackle this logically. I've been thinking about every time I encounter a new element, looking up all the "rules" it's a part of, and then adding it to my "sorted" array based on those rules and the elements that are already in there.

I can't help feel there must be a better way and even with the above method I'm not sure how I would program it. Any advice would be awesome. Cheers.

2. ## Re: Sort Logic

Your problem can not be solved in general; e.g.

A beats B
B beats C
C beats A

kind regards,

Jos

3. Member
Join Date
Mar 2010
Posts
30
Rep Power
0

## Re: Sort Logic

I want to try and add validation to the input to try and stop this from happening, so for now I'm assuming that this conflict won't happen, or I'll implement some kind of conflict resolution when it encounters this.

4. ## Re: Sort Logic

I want to try and add validation to the input to try and stop this from happening, so for now I'm assuming that this conflict won't happen, or I'll implement some kind of conflict resolution when it encounters this.
A precedence matrix might come in handy then; create a square matrix of booleans; the rows and columns are labeled with the names of the competitors; if 'i' beats 'j' set entry M[ i ][ j ] to true; after you have done this for all competitors, try to rearrange the rows such that no entry M[ i ][ j ] is true for i >= j. If you can do that, there is no circularity in the accompanying graph and the relation 'beats' is a PTO (Partial Total Ordering) and you can find all the information in matrix M.

kind regards,

Jos

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•