Programming Forums - Array Sorting

Page 1 of 2

Show 40 post(s) from this thread on one page

Programming Forums (http://www.programmingforums.org/forumindex.php)

- Software Design and Algorithms (http://www.programmingforums.org/forum64.html)

- - Array Sorting (http://www.programmingforums.org/showthread.php?t=15004)

grimpirate

Jan 22nd, 2008 7:23 PM

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.

Sane	Jan 22nd, 2008 7:45 PM

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
 
function cmp($a, $b)
{
    $primary = strcmp($a["lastName"], $b["lastName"]);
    if ($primary != 0)
        return $primary; 
    else
        return strcmp($a["firstName"], $b["firstName"]);
}
 
$table = array(
    array(
        'lastName' => 'ab', 'firstName' => 'cd'
    ),
    array(
        'lastName' => 'ef', 'firstName' => 'gh'
    )
);
 
usort($table, "cmp");
 
?>

Is that the sort of thing you were looking for?

grimpirate

Jan 23rd, 2008 11:16 AM

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:

function customSort($a, $b){
        global $sortBy;
 
        $retval = 0;
        reset($sortBy);
 
        do{
                $retval = strnatcmp($a[current($sortBy)], $b[current($sortBy)]);
        }while(!$retval && next($sortBy) !== false);
 
        return $retval;
}
?>

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.

Sane	Jan 23rd, 2008 12:09 PM

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?

mbd	Jan 23rd, 2008 1:11 PM

Re: Array Sorting

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

<?php
 
class OrderByComparer
{
        var $k;
 
        function OrderByComparer($k)
        {
                $this->k = $k;
        }
 
        function compare($a, $b)
        {
                foreach ($this->k as $k)
                {
                        $r = strcmp($a[$k], $b[$k]);
                        if ($r != 0)
                                return $r;
                }
                return 0;
        }
}
 
$people =
array(
        array(
                'first' => 'tom',
                'last' => 'brady'
                ),
        array(
                'first' => 'eli',
                'last' => 'manning'
                ),
        array(
                'first' => 'brett',
                'last' => 'favre'
                ),
        array(
                'first' => 'peyton',
                'last' => 'manning'
                ),
        array(
                'first' => 'matt',
                'last' => 'leinart'
                ),
        array(
                'first' => 'matt',
                'last' => 'hasselbeck'
                )
        );
 
$flobc = new OrderByComparer(array('first', 'last'));
$lfobc = new OrderByComparer(array('last', 'first'));
 
print_r($people);
usort($people, array($flobc, compare));
print_r($people);
usort($people, array($lfobc, compare));
print_r($people);
 
?>

grimpirate

Jan 23rd, 2008 2:13 PM

Re: Array Sorting

An array of the following structure Sane:

array(
        array(
                'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
                'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
        ),
        array(
                'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
                'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
        ),
        array(
                array(
                        'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
                        'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
                ),
                array(
                        'lastName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)),
                        'firstName' => preg_replace('/[0-9]*/iD', '', str_pad(dechex(crc32(uniqid())), 8, '0', STR_PAD_LEFT)
                )
        )
);

There's two doubly-nested arrays there which have the same keys as the singularly-nested arrays.

mbd	Jan 23rd, 2008 3:17 PM

Re: Array Sorting

how do you compare apples to oranges?

Sane	Jan 23rd, 2008 3:24 PM

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:

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

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?

grimpirate

Jan 24th, 2008 9:30 AM

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:

function makeSortFunction($sortBy, $reverse = false){
        $code = '$sortBy = array(';
        foreach($sortBy as $value){
                $code .= "'" . $value . "', ";
        }
        $code = substr($code, 0, -2);
        $code .= ');';
        if($reverse) $code .= '$reverse = -1;';
        else $code .= '$reverse = 1;';
        $code .= '$retval = 0;';
        $code .= 'foreach($sortBy as $values){';
        $code .= '$retval = strnatcmp($a[$values], $b[$values]);';
        $code .= '$retval *= $reverse;';
        $code .= 'if($retval) break;';
        $code .= '}';
        $code .= 'return $retval;';
        return create_function('$a, $b', $code);
}

Sane	Jan 24th, 2008 9:56 AM

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...

All times are GMT -5. The time now is 3:33 AM.

Page 1 of 2

Show 40 post(s) from this thread on one page