Jump to content
Larry Ullman's Book Forums

Chapter 1, Sorting Multidimensional Arrays, Pg. 6 Function


Recommended Posts

Could someone please explain to me how this function actually does what it does?

 

1. If I get this right, the following function takes two elements of the top level array and compares the elements of sub-array alphabetically:

 

 

function name_sort($x, $y) {
return strcasecmp($x['name'], $y['name']);
}

 

According to the book, it will return a negative number if the first string comes before second alphabetically, a 0 if they are the same, and a positive value of the second string comes before first alphabetically.

 

My questions:

 

a) The function deals with two variables, $x and $y. But the array in the book has more than two elements! How does the function compare multiple elements of an array? It may be a very silly question, but I can't understand from the structure of the function how it can sort an array containing more than two sub-arrays.

 

b ) What would happen to sorting the array by name if the values of the name were exactly the same (for example 'Stephen' and 'Stephen')?

 

Thank you in advance for helping me to understand this!

Link to comment
Share on other sites

I don't have the 3rd edition of the book, so I can't easily reference what you're talking about, but in short, both $x and $y are arrays, but $x['name'] and $y['name'] are strings within the arrays. That's the key, you're not comparing two arrays ($x and $y), you're comparing two strings within arrays (i.e., $x['name'] and $y['name']). As such, the function is fine.

 

Also, like Larry said, if both $x['name'] and $y['name'] are 'Stephen', then 0 is returned. For more info on the function, please see the following:

http://php.net/manual/en/function.strcasecmp.php

  • Upvote 2
Link to comment
Share on other sites

Hey HartleySan, Merry Christmas and Happy Holidays!

 

I absolutely understand everything you're saying, actually, what you're saying is pretty much another way of saying what I wrote in my question.

 

I also understand (I think) the purpose of strcasecmp() function.

 

What I don't understand is how the custom function can handle an array that has not two elements $x and $y, but an unknown number of elements $a, $b, $c, $d ... $x, $y, $z etc.

 

I'm not sure if I'm formulating my question coherently, but I just don't understand how the structure of a custom function that refers explicitly to two items, $x and $y, can be applied to an entity that contains more than two items.

 

As I said, I'm sure it's a silly question to a knowledgeable person, but I'm utterly perplexed.

 

Would be grateful for clarification!

Link to comment
Share on other sites

The function doesn't handle an unknown number of elements. Unfortunately, I cannot comment much beyond that because I don't have the 3rd edition of the book and I cannot see the surrounding code. At the moment, the function only compares the 'name' element of two arrays. If you had an unknown number of arrays, you could handle that by using various loop structures, but that would all be handled outside of the function.

Larry may address such things in the book, but with only the function code provided, I cannot comment on that conclusively.

  • Upvote 1
Link to comment
Share on other sites

Dimitri, that's not the problem. The problem is that you're not sharing the relevant code around the function. The function is one line of code and very straightforward.

 

Unless you can share the code used with the function or explain exactly what you want to do, we can't help you.

Like I said, if you want to handle an unknown number of arrays, you need a loop structure of some sort.

Link to comment
Share on other sites

Well, HartleySan, this particular forum is supposed to be for the third edition of this book, so I think I was fair to assume that it's available to the members of the forum. I still appreciate your promptly reacting to my question, I just wish you had that book.

 

Larry, being the author, should have a copy - that's why I invoked Him.

 

My concern regarding your suggesting to show the entire code is that I'm not sure if posting the code from the whole section of Larry's book would be very welcomed by the author, but one the other hand, he can always delete a thread if it's revealing too much, so let me try (but only because you insisted, HartleySan!)

 

So, first we define the two-dimensional array, which contains arbitrarily chosen id numbers for students as indexes of the outer array, and inner arrays of names and grades as values, like so:

 

 

$students = array( 

256 => array('name' => 'Jon', 'grade' => 98.5), 
2 => array('name' => 'Vance', 'grade' => 85.1),
9 => array('name' => 'Stephen', 'grade' => 94.0), 
364 => array('name' => 'Steve', 'grade' => 85.1), 
68 => array('name' => 'Rob', 'grade' => 74.6)

);

 

Then we define the function for sorting students by name (the one I was asking about):

 

 

function name_sort($x, $y) {

return strcasecmp($x['name'], $y['name']);
}

 

Then we define the function for sorting students by grade:

 

 

function grade_sort ($x, $y) {

return ($x['grade'] < $y['grade']);

}

 

Finally we output the array sorted by name --

 

uasort($students, 'name_sort');
echo '<h2>Array Sorted By Name</h2><pre>' . print_r($students, 1) . '</pre>';

 

-- and sorted by grade:

 

 

uasort($students, 'grade_sort');
echo '<h2>Array Sorted By Grade</h2><pre>' . print_r($students, 1) . '</pre>';

 

Now, back to my original question: the custom-defined function for comparing strings $x['name'] and $y['name'] is dealing with two strings only. The array contains more than two elements. How can that function sort the entire array, if it only compares two items?

 

I am sure that the secret lies in the way uasort() function handles the result of the custom function, but I do not understand how it works, and am in need of an explanation. One way or another, I don't see any loops in that code...

Link to comment
Share on other sites

Yeah, I know it's for the 3rd edition, but being Christmas and all, I just assumed that no one (including Larry) was going to respond soon, which is why I jumped in (even though I only have the 4th edition of the book).

Anyway, I do apologize in that I completely forgot that Larry offers all the code in his books for free on his site. I should have downloaded the code and looked at it, so that's my fault.

The good news though is that because all the code is available for free, you don't have to worry about Larry or anyone getting upset for posting code from the book on the forum.

 

Now, to answer your question, pretty much exactly as you have assumed, the uasort function does contain some kind of loop construct that goes through each of the arrays in the students array, and sorts them accordingly.

I think where there's a misunderstanding is in what's being sorted and how. The arrays in the students array are being sorted, not the individual values in the subarrays in the students array. However, in order to sort the subarrays, values within those subarrays (i.e., name and grade) are used.

 

When using the uasort function, the function called from that function always accepts two arguments, and those arguments are always two values in the array provided as the first argument of the uasort function.

The twist that Larry's putting on all this is that instead of the students array containing scalar values (like numbers or strings), it contains arrays.

 

I'd check out the uasort function on PHP.net for details.

  • Upvote 1
Link to comment
Share on other sites

It compares all values in the array, but that happens internally. This is a pattern called a compator, and is used to compare collections structures like this PHP array (The array structure implements an Interface that makes it Comparable for a Comparator). To use more known examples, the reason why you can use a while loop on a MySQL(i) result object, is that this structure is built on a pattern called an iterator. This is also why arrays support foreach statements. (You can build this into your own classes)

 

This pattern is often tied to lists of objects in other languages. Let's say you have a Person class. A PersonList would be a class that handles a list of Person objects (Using an array internally). This class can have methods for looping, adding, removing, sorting and a lot of other things. Such classes are called a Collection in other languages, and is a definition for lists, (that's normal arrays in most languages) linkedLists, stacks, queques and other fun data structures, including Hash maps (associative array keys are implemented as a Hash map). In PHP, all of these data structures are defined as ARRAY........ Let that sink in.

 

The point here is that arrays in PHP is not arrays as you find them in other languages. That is not all bad, and also some of the reason why PHP is so awesome at times. The problem is that it makes it very hard to understand a lot of concepts for PHP developers as they don't understand the data structures strengths and weaknesses. Because we "have it all", very few developers has to think about how sorting, iterating and CRUD operations actually work.

 

The reason why your examples work is because of this. The standard, built in internal way of ordering arrays is by a method most often call compareTo() in other languages. This method could be implemented in the Person example class of ours through an interface often called Comparable. When that is done, the PersonList can easily compare each Person found in the list and thus sort the array of Person objects. What you basicly do here is to say that PHP's Array structure (A PersonList) should compare all keys called name found in an element (A Person), using either the standard compareTo function defined in the Element or a function you define yourself. (And that function then takes the job of the compareTo function instead)

 

This is both pretty advanced and pretty simple stuff at the same time. You cannot really understand all this at once, but that is approximaly how it should work. I cannot fully gurantee that's how PHP has actually implemented it, but these are well known patterns in object oriented programming. It can be defined as theory as much as implemented in practice. Once recommendation is to read about data structures if your interested, but if not then just take my word for it. Don't try to understand your toaster, just learn how to use it. ;)

 

Edit: Sorry about the poor English here, might clean it up a bit tomorrow. Been a great christmas with family, good food and a local liquor called "Akevit". (Aqua vita - water of life) It's a scandinavic speciality liquor that's great with fat food. Try it if you ever visit Denmark, Sweden or Norway. We take great pride in it, but mostly drink it around chirstmas time.

  • Upvote 3
Link to comment
Share on other sites

Thanks to everyone for their help here, as always. And Merry Christmas/Happy Holidays to all! Yes, as Hartley suggested, I'm on holiday myself and trying not to work. But I'm at my parents house and the kids woke up too early and there are few things to do, so...

Link to comment
Share on other sites

Gents:

Can anyone recommend a primer on Data Structures that delves into the principles of comparator, iterator, etc. classes (in other languages). I, too, have struggled with the same concept posted by Dimitri. Thanks.

 

Best regards and Happy New Year,

Link to comment
Share on other sites

I searched for the title we used in my university course. Upon that, I found a video series you can watch for free. It's found on iTunes, but I bet you'll find it on vimeo/Youtube/similar to.

 

The book we used is Data Structures and Problem Solving in Java, by Mark A. Weiss. I think it was a pretty good book on the subject, while some parts could definitely be improved upon. It will teach you Big O analysis, several search/sort algorithms, pretty much all data structures and core coding concepts including Iterators, Comparators, Generic Type (You need to know this for extending main parts of Java in a good way), good exception handling, private classes, advanced object scoping, recursion, static classes and functions, etc.

 

As this is pretty much my only source for learning these concepts, I can't really make comparisons. You should, however, be able to understand this concepts, when to apply them, and how to implement them. The book is often starting out with simplified versions of a concept, and improves upon them though the chapters. Therefor, you can't use it as a straight reference, but need to make sure the implementation suits your need. As an example, three structures are seriously improved upon as the pages fly.

 

The book requires a great understanding of basic-to-advanced object-oriented concepts, and you need to implement the solutions themselves to make the information stick. It's not by any means an easy read-though, and requires time and dedication. It has very good rating on Amazon, with 5 stars being the majority by a mile.

 

As a head up, I would ignore much of the thesis and proves in general when it comes to this kind of stuff. It's not really relevant unless you want to do research mathematically/look for improvements on the algorithms. The important thing is to understand the concepts, being able to use them yourself, and understanding when to use them. That way, the things you learn about data structures and algorithms is pretty language agnostic, and Weiss also says this himself. You should be able to use these concepts in other languages like C# without problems, with some extra research and information about the languages core libraries. In the end, you'll know very much about how Java works.

 

Hope that helps you out.

 

Edit: Some video sources:

- http://www.youtube.com/user/MIT

- http://video.mit.edu/

 

Edit: Algorithm analysis series: (Skip to 17 min)

- http://www.youtube.com/watch?v=JPyuH4qXLZ0&list=EC8B24C31197EC371C

  • Upvote 1
Link to comment
Share on other sites

 Share

×
×
  • Create New...