Sorting arrays with cyclic compares (infinite loop?)

Question

Hi,

I have some objects that have 3 sorting options: quality, quatity and a compare against the other object, sorted by that order.

- (NSComparisonResult) compare: (MyObject *) obj {
if (self.quality > obj.quality)
return NSOrderedAscending;
else if (self.quality < obj.quality)
return NSOrderedDescending;

if (self.quantity > obj.quantity)
return NSOrderedAscending;
else if (self.quantity < obj.quantity)
return NSOrderedDescending;

if ([self betterThan: obj])
return NSOrderedAscending;

if ([obj betterThan: self])
return NSOrderedDescending;

return NSOrderedSame;
}

My problem is that, the betterThan: method might cause a cyclic compare if the objects have the same quality and quantity, and I want to return any sort order in that case.

For example, A, B and C have the same quality/quantity, but

A betterThan: B => YES
B betterThan: C => YES
C betterThan: A => YES

Solutions? Thanks.

Answer 1

You should have the betterThan: method return NSOrderedSame. All methods that return NSComparisonResult should always be able to return all three options.

Your method will never pass past the first if -block:

if (self.quality > obj.quality)
    return NSOrderedAscending;
else
    return NSOrderedDescending; //<== returns for both self.quality > obj.quality AND self.quality == obj.quality

Since the comparison must have one of three results but you only test for one, you will always return from the method in that if-block. None of the other logic will ever be used.

You will need to nest the if-blocks to get the filtering logic. Test if they are greater and lesser and return but if they are the same move to the next test. Repeat as needed.

- (NSComparisonResult) compare: (MyObject *) obj {
    if (self.quality > obj.quality)
        return NSOrderedAscending;
    else if (self.quality < obj.quality)
        return NSOrderedDescending; 
    else {
        if (self.quantity > obj.quantity)
            return NSOrderedAscending;
        else if (self.quantity < obj.quantity)
            return NSOrderedDescending;
        else {
            ... and so on
        }
    }

I think each attribute comparison should have its own method. Then you can combine them into one grand compare if you need to comprehensively compare two objects of the class.

It look like in this case that the betterThan: method is your actual class compare.

Answer 2

I'm a bit confused regarding your code and what your question is. The compare function you have looks like it will only compare the quality (both branches of the first if have returns in them). If you want to only use betterThan in your compare (which I think is what the problem your facing is..) I would do something like:

- (NSComparisonResult) compare: (MyObject *) obj {
    if ([self betterThan: obj])
        if ([obj betterThan: self])
            return NSOrderedSame
        else
            return NSOrderedAscending;
    else
        return NSOrderedDescending
}

Answer 3

Ok, I found out the bug had nothing to do with sorting (although it seemed to be caused by it).

Apparently this actually works. The system stops sorting if there's a deadlock.

Thanks for your time, anyway. :)