Results 1 to 4 of 4

Thread: Sort Logic

  1. #1
    FallenBlade is offline Member
    Join Date
    Mar 2010
    Posts
    31
    Rep Power
    0

    Default 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. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default 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
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    FallenBlade is offline Member
    Join Date
    Mar 2010
    Posts
    31
    Rep Power
    0

    Default 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. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,651
    Blog Entries
    7
    Rep Power
    21

    Default Re: Sort Logic

    Quote Originally Posted by FallenBlade View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Where's the logic?
    By diamonddragon in forum New To Java
    Replies: 11
    Last Post: 01-28-2012, 04:16 AM
  2. need a logic for this
    By rajivjoshi in forum New To Java
    Replies: 4
    Last Post: 06-12-2010, 02:18 PM
  3. Using Merge Sort to sort an ArrayList of Strings
    By coldfire in forum New To Java
    Replies: 3
    Last Post: 03-13-2009, 01:03 AM
  4. How to sort a list using Bubble sort algorithm
    By Java Tip in forum Algorithms
    Replies: 3
    Last Post: 04-29-2008, 08:04 PM
  5. Cant get the logic right
    By jermaindefoe in forum New To Java
    Replies: 4
    Last Post: 03-11-2008, 12:22 AM

Posting Permissions

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