PDA

View Full Version : Page 363, Kochan 2.0 -- questions about sorting of arrays




mdeh
Feb 4, 2009, 11:05 AM
Hi all,

Program 15:13 gives an example of sorting an array, using the "sortUsingSelector" method. Because the array contains, as it's elements, AddressCards, ( which in turn contain 2 NSStrings), the "selector" chosen ( defined below) compares two NSStrings.
Some questions have arisen, which I would like to pose to the group.

Question 1: (Somewhat Indirectly associated with p 363). Arrays are ordered collections that can contain any sort of object (Collections Programming Topics for Cocoa, Apple documentation).
This is clearly ( well, I hope clearly) different from a **sorted** array, but how. Does "ordered" refer to the sequential allocation of elements?

Question 2: About the middle of the page:

When it needs to make such a comparison, it invokes the specified method, sending the message to the first element in the array (the receiver) to be compared against it's argument
If one compares this to a description of the term Comparator in "sortUsingSelector" The comparator message is sent to each object in the receiver and has as its single argument another object in the array. then I wonder if I am being nitpicky, or whether I am missing something here. In other words, the more generic description allows the compiler (??) to choose a quicksort/bubblesort etc, ie it does not decide **how** to sort, it simply says **sort these two things**

Last Question ( all these damned question!!!! :) )

The defintion for the compare method is thus.

-(NSComparisonResult) compareNames: (id) element
{


return [ name compare: [element name] ]

}

Why is "element" declared as type (id)?. Is this a requirement of the compare method of NSString? The name "element" is unique, or just an identifier chosen by the programmer.


thanks as usual



eddietr
Feb 4, 2009, 02:22 PM
This is clearly ( well, I hope clearly) different from a **sorted** array, but how. Does "ordered" refer to the sequential allocation of elements?


So it means that the array is in an order. It doesn't mean the order is meaningful or "sorted" in any particular way.

It just means there is a first element, a second element, and so on. And therefore it is possible to refer to the nth element of the array.


In other words, the more generic description allows the compiler (??) to choose a quicksort/bubblesort etc, ie it does not decide **how** to sort, it simply says **sort these two things**


Right, you are not defining the algorithm that NSArray will use in the sort. But it uses a comparison based algorithm meaning that as it goes through the array it needs to answer the question does this element "a" belong before or after this element "b". To answer that question it sends a message to "a" that looks sort of like this:



[a comparator:b]



Where b is the id of the element "b". So it is asking "a": "Do you belong before or after this other element b?"

Then the NSArray sort implementation will call that comparator as many times as needed to check that the every element is in the correct order.


Why is "element" declared as type (id)?. Is this a requirement of the compare method of NSString? The name "element" is unique, or just an identifier chosen by the programmer.


It is of type (id) because the NSArray sort implementation doesn't know and doesn't care really about the classes of objects in the Array. All it needs to do is ask each object how it compares to some other object. So it just passes an NSObject id to the comparator.

And yes, it's like any other method definition, you can name the parameter anything you want. That identifier "element" exists just within that scope.

Hope that helps?

mdeh
Feb 4, 2009, 02:41 PM
So it means that the array is in an order. It doesn't mean the order is meaningful or "sorted" in any particular way.

It just means there is a first element, a second element, and so on. And therefore it is possible to refer to the nth element of the array.

Ok...that makes perfect sense.



Right, you are not defining the algorithm that NSArray...............To answer that question it sends a message to "a" that looks sort of like this:



[a comparator:b]



/**snip**/

Then the NSArray sort implementation will call that comparator as many times as needed .....

Yes..that's what I figured. I was confused by the term "first" in Steve's description, as I thought that part was "black box" implementation.



It is of type (id) because the NSArray sort implementation doesn't know and doesn't care really about the classes of objects in the Array. All it needs to do is ask each object how it compares to some other object. So it just passes an NSObject id to the comparator.

Just to play devil's advocate, if I ( the programmer) **know** that the object is, say, an "AddressCard* " , would it be regarded as Poor programming to use that instead of type ID, or is it more than that.

For example:
-(NSComparisonResult) compareNames: (AddressCard * ) element
{
return [ [element name] compare: name ];
}

Thanks in advance for that illuminating response.
As always, appreciated.

eddietr
Feb 4, 2009, 03:00 PM
Just to play devil's advocate, if I ( the programmer) **know** that the object is, say, an "AddressCard* " , would it be regarded as Poor programming to use that instead of type ID, or is it more than that.

For example:
-(NSComparisonResult) compareNames: (AddressCard * ) element
{
return [ [element name] compare: name ];
}


Well, remember the code that is calling compareNames: doesn't know the type, though. (Because NSArrays can store any objects, and they don't have to even be of the same class).

In Java for example, you could say something like:

Collections.sort (someCollection, new Comparator<AddressCard> () {...});

and then the compare method in that Comparator would be something like:

int compare (AddressCard a1, AddressCard a2) {...}


That is using Java's generics feature, and it assumes that your collection is of type Collection<AddressCard>.

But Cocoa/ObjC doesn't have that feature, so all the sort code can do is assume that the objects being sorted are NSObjects. So all it can do is pass you an id.

Within your comparison, though, you can test that the object being passed to you is of a particular type, or responds to a certain selector(s) or whatever you need to make the comparison.

mdeh
Feb 4, 2009, 03:04 PM
thank you

skochan
Feb 4, 2009, 04:47 PM
thank you

I'm really impressed by all the participation in this forum and all the help everyone is willing to offer. You've all been doing such a great job with your careful explanations (Michael - mdeh - I'm sure will agree).

I've enjoyed standing back and letting someone else explain a concept because it is often more illuminating than having it explained the same way twice (it's not because I'm lazy -- really :))

Cheers,

Steve Kochan