Programming Forums
User Name Password Register
 

RSS Feed
FORUM INDEX | TODAY'S POSTS | UNANSWERED THREADS | ADVANCED SEARCH

Reply
 
Thread Tools Display Modes
Old Jan 22nd, 2008, 7:23 PM   #1
grimpirate
King of Portal
 
grimpirate's Avatar
 
Join Date: Sep 2005
Posts: 403
Rep Power: 3 grimpirate is on a distinguished road
Send a message via Yahoo to grimpirate
Question Array Sorting

I know how to sort an array by comparing each of the values in the array and then sorting them according to less than, greater than or equal to each other. However, given the case where I had an array of arrays (an n-dimensional array). How would I sort? Take this example:
Quote:
array(
array(
'lastName' => 'ab', 'firstName' => 'cd'
),
array(
'lastName' => 'ef', 'firstName' => 'gh'
),
array()
....)
How would I sort it according to the lastName and then maintaining that order sort it according to the firstName? Can anybody point me to some references to this or tell me what this type of sorting is called? I'm not sure what to even type into Google.
__________________
Lo, there do I see my father. 'Lo, there do I see My mother, and my sisters, and my brothers. 'Lo, there do I see The line of my people... Back to the beginning. 'Lo, they do call to me. They bid me take my place among them. In the halls of Valhalla... Where the brave... May live... ...forever.. GrimBB | Mimesis
grimpirate is offline   Reply With Quote
Old Jan 22nd, 2008, 7:45 PM   #2
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Posts: 1,799
Rep Power: 5 Sane will become famous soon enough
Re: Array Sorting

So if I understand correctly, the primary sort is on the last name? Then if there's a tie between two keys, the tie is broken by the first name?

There's no "special" algorithm for this. It's just a normal sort. In fact, something like this is so common that PHP supports a function that let's you, the programmer, specify the comparison function.

usort(array, callback)

You pass through your own callback function that will determine whether two values are less than, equal, or greater than eachother. In the event that your last name is equal, you can return the value corresponding to a second comparison of the first names.

Warning: Untested.

PHP Syntax (Toggle Plain Text)
  1. <?php
  2.  
  3. function cmp($a, $b)
  4. {
  5. $primary = strcmp($a["lastName"], $b["lastName"]);
  6. if ($primary != 0)
  7. return $primary;
  8. else
  9. return strcmp($a["firstName"], $b["firstName"]);
  10. }
  11.  
  12. $table = array(
  13. array(
  14. 'lastName' => 'ab', 'firstName' => 'cd'
  15. ),
  16. array(
  17. 'lastName' => 'ef', 'firstName' => 'gh'
  18. )
  19. );
  20.  
  21. usort($table, "cmp");
  22.  
  23. ?>

Is that the sort of thing you were looking for?
Sane is offline   Reply With Quote
Old Jan 23rd, 2008, 11:16 AM   #3
grimpirate
King of Portal
 
grimpirate's Avatar
 
Join Date: Sep 2005
Posts: 403
Rep Power: 3 grimpirate is on a distinguished road
Send a message via Yahoo to grimpirate
Re: Array Sorting

That was what I suspected but I wasn't quite sure how to implement. I actually find a great tutorial http://www.the-art-of-web.com/php/sortarray/ which is exactly like what you're stating, I came up with the following:
PHP Syntax (Toggle Plain Text)
  1. function customSort($a, $b){
  2. global $sortBy;
  3.  
  4. $retval = 0;
  5. reset($sortBy);
  6.  
  7. do{
  8. $retval = strnatcmp($a[current($sortBy)], $b[current($sortBy)]);
  9. }while(!$retval && next($sortBy) !== false);
  10.  
  11. return $retval;
  12. }
  13. ?>
Where the variable $sortBy is actually an array containing the order of keys in which a user would wish to perform the sorting so in the example I gave something like $sortBy = array('lastName', 'firstName'); What I'm trying to figure out now is how I could do it recursively assuming there were repeating keys within a nested array.
__________________
Lo, there do I see my father. 'Lo, there do I see My mother, and my sisters, and my brothers. 'Lo, there do I see The line of my people... Back to the beginning. 'Lo, they do call to me. They bid me take my place among them. In the halls of Valhalla... Where the brave... May live... ...forever.. GrimBB | Mimesis
grimpirate is offline   Reply With Quote
Old Jan 23rd, 2008, 12:09 PM   #4
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Posts: 1,799
Rep Power: 5 Sane will become famous soon enough
Re: Array Sorting

I understand everything you're saying up until this point:

Quote:
What I'm trying to figure out now is how I could do it recursively assuming there were repeating keys within a nested array.
Do what recursively?
Repeated keys?

Maybe it would be helpful to explain the problem objectively, and why the solution you posted is insufficient?
Sane is offline   Reply With Quote
Old Jan 23rd, 2008, 1:11 PM   #5
mbd
Programmer
 
Join Date: Nov 2007
Posts: 86
Rep Power: 1 mbd is on a distinguished road
Re: Array Sorting

I wrote a class which you might be able to use and a sample:

php Syntax (Toggle Plain Text)
  1. <?php
  2.  
  3. class OrderByComparer
  4. {
  5. var $k;
  6.  
  7. function OrderByComparer($k)
  8. {
  9. $this->k = $k;
  10. }
  11.  
  12. function compare($a, $b)
  13. {
  14. foreach ($this->k as $k)
  15. {
  16. $r = strcmp($a[$k], $b[$k]);
  17. if ($r != 0)
  18. return $r;
  19. }
  20. return 0;
  21. }
  22. }
  23.  
  24. $people =
  25. array(
  26. array(
  27. 'first' => 'tom',
  28. 'last' => 'brady'
  29. ),
  30. array(
  31. 'first' => 'eli',
  32. 'last' => 'manning'
  33. ),
  34. array(
  35. 'first' => 'brett',
  36. 'last' => 'favre'
  37. ),
  38. array(
  39. 'first' => 'peyton',
  40. 'last' => 'manning'
  41. ),
  42. array(
  43. 'first' => 'matt',
  44. 'last' => 'leinart'
  45. ),
  46. array(
  47. 'first' => 'matt',
  48. 'last' => 'hasselbeck'
  49. )
  50. );
  51.  
  52. $flobc = new OrderByComparer(array('first', 'last'));
  53. $lfobc = new OrderByComparer(array('last', 'first'));
  54.  
  55. print_r($people);
  56. usort($people, array($flobc, compare));
  57. print_r($people);
  58. usort($people, array($lfobc, compare));
  59. print_r($people);
  60.  
  61. ?>

Last edited by mbd; Jan 23rd, 2008 at 1:26 PM. Reason: made the example better
mbd is offline   Reply With Quote
Old Jan 23rd, 2008, 2:13 PM   #6
grimpirate
King of Portal
 
grimpirate's Avatar
 
Join Date: Sep 2005
Posts: 403
Rep Power: 3 grimpirate is on a distinguished road
Send a message via Yahoo to grimpirate
Re: Array Sorting

An array of the following structure Sane:
PHP Syntax (Toggle Plain Text)
  1. array(
  2. array(
  3. 'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
  4. 'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
  5. ),
  6. array(
  7. 'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
  8. 'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
  9. ),
  10. array(
  11. array(
  12. 'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
  13. 'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
  14. ),
  15. array(
  16. 'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
  17. 'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
  18. )
  19. )
  20. );
There's two doubly-nested arrays there which have the same keys as the singularly-nested arrays.
__________________
Lo, there do I see my father. 'Lo, there do I see My mother, and my sisters, and my brothers. 'Lo, there do I see The line of my people... Back to the beginning. 'Lo, they do call to me. They bid me take my place among them. In the halls of Valhalla... Where the brave... May live... ...forever.. GrimBB | Mimesis
grimpirate is offline   Reply With Quote
Old Jan 23rd, 2008, 3:17 PM   #7
mbd
Programmer
 
Join Date: Nov 2007
Posts: 86
Rep Power: 1 mbd is on a distinguished road
Re: Array Sorting

how do you compare apples to oranges?
mbd is offline   Reply With Quote
Old Jan 23rd, 2008, 3:24 PM   #8
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Posts: 1,799
Rep Power: 5 Sane will become famous soon enough
Re: Array Sorting

Oh! The number of dimensions is dynamically changing! ... Wow ...

Okay. So, now I would say it depends on the fine specifics of how you need it sorted. I can think of at least 3 ways right now given your structure. I am guessing you want each depth sorted with respect to itself, like so:

(
    ( 
        6, 
        6, 
        6, 
        6 
    ),

    ( 
        5, 
        5, 
        5, 
        5 
    ),

    (
        ( 
            6, 
            6, 
            6, 
            6 
        ),

        (
            4, 
            4, 
            4, 
            4 
        )
    )
)

Sorting on the 1st, 2nd, 3rd or 4th key. Doesn't matter. They are all the same.

(
    ( 
        5, 
        5, 
        5, 
        5 
    ),

    ( 
        6, 
        6, 
        6, 
        6
    ),

    (
        (
            4, 
            4, 
            4, 
            4
        ),

        ( 
            6, 
            6, 
            6, 
            6
        )
    )
)

So. Recursion. In your compare callback, while you're comparing each type, if you find that it's an array, call "usort" for that array from within the callback.

But you're going to have to let the callback function consistently know that an array of arrays should be considered greater than everything else (to get them all at the bottom).

Shouldn't have to tweak the usort that much.

But if you want everything sorted globally, which could potentially splice all your arrays into tiny bits... then why not just flatten it first?
Sane is offline   Reply With Quote
Old Jan 24th, 2008, 9:30 AM   #9
grimpirate
King of Portal
 
grimpirate's Avatar
 
Join Date: Sep 2005
Posts: 403
Rep Power: 3 grimpirate is on a distinguished road
Send a message via Yahoo to grimpirate
Re: Array Sorting

Yeah... I know... recursion... T_T The bane of my existence. I've written about one recursive function in my life that I've understood lol. Not sure what you mean by your last sentence though. In any case I modified the sorting function to the following:
php Syntax (Toggle Plain Text)
  1. function makeSortFunction($sortBy, $reverse = false){
  2. $code = '$sortBy = array(';
  3. foreach($sortBy as $value){
  4. $code .= "'" . $value . "', ";
  5. }
  6. $code = substr($code, 0, -2);
  7. $code .= ');';
  8. if($reverse) $code .= '$reverse = -1;';
  9. else $code .= '$reverse = 1;';
  10. $code .= '$retval = 0;';
  11. $code .= 'foreach($sortBy as $values){';
  12. $code .= '$retval = strnatcmp($a[$values], $b[$values]);';
  13. $code .= '$retval *= $reverse;';
  14. $code .= 'if($retval) break;';
  15. $code .= '}';
  16. $code .= 'return $retval;';
  17. return create_function('$a, $b', $code);
  18. }
__________________
Lo, there do I see my father. 'Lo, there do I see My mother, and my sisters, and my brothers. 'Lo, there do I see The line of my people... Back to the beginning. 'Lo, they do call to me. They bid me take my place among them. In the halls of Valhalla... Where the brave... May live... ...forever.. GrimBB | Mimesis
grimpirate is offline   Reply With Quote
Old Jan 24th, 2008, 9:56 AM   #10
Sane
Programming Guru
 
Sane's Avatar
 
Join Date: Apr 2005
Posts: 1,799
Rep Power: 5 Sane will become famous soon enough
Re: Array Sorting

Zoh! What the hank are you doing all that for!? Seems like horrible coding practice to me.


What I meant by my last sentence, is if you wanted everything sorted as though the depth of the arrays didn't matter, why not flatten it into one level, then sort it? I don't see at all why you'd possibly want to sort an array like this, and which of the many ways you could have it sorted, you want.

You could have everything sorted as though the depth did not matter. You could have each branch sorted separately. You could do the latter, and order the remaining multidimensional arrays by depth. You could do the latter, and order each array by how the first entry compares to the last entry in the last multidimensional array. You could have each level sorted (as opposed to branch). Then all the corresponding permutations that go along with that... So on and so forth...

Last edited by Sane; Jan 24th, 2008 at 10:08 AM.
Sane is offline   Reply With Quote
Reply

Bookmarks

« Previous Thread in Forum | Next Thread in Forum »

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
tasm sorting 5 integers with array akioshin Assembly 15 Oct 30th, 2007 1:45 AM
sorting an array by field cwl157 C 4 Apr 4th, 2007 2:48 PM
Sorting an array of objects oNe8 Java 2 Feb 22nd, 2006 10:59 PM
Sorting a Numeric Array little_valaree Java 2 Nov 21st, 2005 11:00 AM
Installing IPB 2.03 bh4575 Other Web Development Languages 0 Apr 23rd, 2005 2:36 AM




DaniWeb IT Discussion Community
All times are GMT -5. The time now is 5:36 PM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC