ios - How is the sortedArrayUsingComparator method implemented?

I was trying to rewrite the official sortedArrayUsingComparator: method in Objective-C. How can I do this?

In the NSArray class, how are the elements actually stored in the array? What is the type (in the code: type?) in the for-loop? Generics do not seem to exist in Objective-C. How does the compare: method work?

- (NSArray *)recentQuestions {
    return [questions sortedArrayUsingComparator: ^(id obj1, id obj2) {
        Question *q1 = (Question *)obj1; 
        Question *q2 = (Question *)obj2; 
        return [q2.date compare: q1.date];
}]; }

//class NSArray

//? NSArray* selfArray = @[];
-(...) sortedArrayUsingComparator : (void (^)(id obj1, id obj2) ) blockName{
    for ( int i=0; i<selfArray.count-1; i++){ 
        for ( int j=i+1; j<selfArray.count; j++){ 
            type? *bigger = blockName(selfArray[i], selfArray[j]);          
            //move items if j>i
            if (bigger isEqual:selfArray[j]) {
                int tempValue = newArray[i];
                newArray[i] = newArray[j];
                newArray[j] = tempValue;
            }
        }
    }
}

2 Answers

  1. Kenny- Reply

    2019-11-14

    I'll attempt to answer the questions you have asked.


    In the NSArray class, how are actually store the elements added to the array?

    I think you're asking how to add new elements or modify the order of elements within an NSArray. This is not possible. You should be using an NSMutableArray if you need to mutate the contents of the array. With an NSMutableArray, the following is possible:

    id tempValue = newArray[i];
    newArray[i] = newArray[j];
    newArray[j] = tempValue;
    

    What is the type (in the code: type?) in the for-loop? Generics does not seem to exist in objective-c.

    The type that you should expect there is whatever return type you have from your block. In your case, the block you have specified has a void return type, meaning that you really shouldn't be trying to assign a variable from its result. Below, you will see the return type should be listed as NSComparisonResult.

    In my answer to the first question, you may have noticed how a generic pointer is treated in objective-c: id. Every non-primitive object can be held in an id variable.


    How does the compare method work?

    -(...) sortedArrayUsingComparator : (void (^)(id obj1, id obj2) ) blockName{
    

    You should specify a return type for sortedArrayUsingComparator. I suggest NSArray. Your block should also have a return type of NSComparisonResult.

    -(NSArray *) sortedArrayUsingComparator : (NSComparisonResult (^)(id obj1, id obj2) ) blockName{
    

    Now when you invoke the block, you'll get a value representing the result of comparing two objects. This will be one of NSOrderedSame, NSOrderedDescending, or NSOrderedAscending.


    I'm unclear what your selfArray and newArray values are intended to be here. It looks like you're comparing values within selfArray, but then changing the order of newArray based on that comparison. It didn't sound like you were asking about the algorithm used to sort things, so I'll just leave that alone.

  2. Kevin- Reply

    2019-11-14

    A class can use itself as soon as it is defined. There-for it can be used inside it.

    It is possible that NSArray uses NSMutableArray in its implementation, but this would be awkward as NSArray is a superclass of NSMutableArray and it is considered bad design if a superclass depends on knowledge subclasses.

    but…

    Actually we are never dealing with NSArrays, nor with NSMutableArrays, which are class clusters that creates, when instantiated, yet other subclasses as __NSArrayI (immutable) and __NSArrayM (mutable). it is absolutely fine if both of them knows the public NSMutableArray interface.

    There-for probably the method just double-loops (more-likely some better sorting algorithm. or even several for different memory situations) over the array and fill a NSMutableArray before a immutable copy is returned.


    A basic implementation with runtime complexity O(n2) and memory usage of O(1) could look like this:

    @interface NSArray (Comparator)
    -(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator;
    @end
    
    @implementation NSArray (Comparator)
    
    -(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator
    {
        NSMutableArray *array = [self mutableCopy];
        if ([array count] > 1) {
            for (NSUInteger i = 0; i < [array count] - 1; ++i) {
                for (NSUInteger j  = i; j < [array count]; ++j) {
                    if (comparator(array[i], array[j]) == NSOrderedDescending) {
                        [array exchangeObjectAtIndex:i withObjectAtIndex:j];
                    }
                }
            }
        }
        return [array copy];
    }
    @end
    

    Usage:

    NSArray *array = @[@4, @9, @2, @1, @7];
    
    array = [array vs_sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
        return  [obj1 compare:obj2];
    }];
    

    Results in

    (
        1,
        2,
        4,
        7,
        9
    )
    

    A faster implementation with runtime complexity O(n log n) , though requires more memory (average: O(log(n))) would be quicksort where comparison between object and pivot element is performed by the comparator block:

    @interface NSArray (Comparator)
    -(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator;
    @end
    
    @implementation NSArray (Comparator)
    -(NSArray *) quicksortUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator
    {
        NSArray *array = [self copy];
    
        if ([array count]<2) return [array copy];
    
        id pivot = [array randomElement];
        NSMutableArray *array2= [NSMutableArray array];
    
        array = [array arrayByPerformingBlock:^id  (id element) { return element;}
                          ifElementPassesTest:^BOOL(id element) { return comparator(element, pivot) == NSOrderedAscending;}
                             elsePerformBlock:^    (id element) { if (element!=pivot) [array2 addObject:element];}
                ];
        return [[[array quicksortUsingComparator:comparator]
                                        arrayByAddingObject:pivot]
                                            arrayByAddingObjectsFromArray:[array2 quicksortUsingComparator:comparator]];
    }
    
    -(NSArray *)vs_sortedArrayUsingComparator:(NSComparisonResult(^)(id obj1, id obj2))comparator
    {
        return [self quicksortUsingComparator:comparator];
    }
    @end
    

    As in both implementation only vs_sortedArrayUsingComparator: is presented to the public, it is easy to imagine that behind the scene different algorithms might be used under different circumstances. Quicksort is a very fast one but for very big list it might create an stack overflow. In such a case it could be better to switch to another algorithm that might be slower but implements in-place sorting.


    The full implementation of the Quicksort example can be found here: http://vikingosegundo.github.io/2015/02/05/implement-comparator/

    Including

    - (NSArray *)arrayByPerformingBlock:(id   (^)(id element))performBlock 
                    ifElementPassesTest:(BOOL (^)(id element))testBlock
                       elsePerformBlock:(void (^)(id element))elseBlock;
    

    and

    -(id)randomElement;
    

    What is the type (in the code: type?) i

    id, which translates to «a pointer to any object». You can abbreviate it to «any object», as all objects in Objective-C are only accessible through pointers.

Leave a Reply

Your email address will not be published. Required fields are marked *

You can use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>