Can associative arrays be sorted?

[Shikha Ghosh Gottfried]

I have an associative array that contains names as keys and dates
(just strings) as values. Is there a way to sort the array by the
dates so that I can print out the array in descending date order? Also please
note that the dates must be the values, not the keys, and they are
not necessarily unique.
The standard way of sorting (@sorted = sort datecmp keys %mylist)
seems to only allow me to sort an associative array by key (or by
value) and puts the result into a scalar array, but I lose the second
part of each key/value pair if I do this.
Any suggestions would be appreciated.

Thanks,

Shikha

[Philip Guenther]

Given an associative array %foo whose values are dates, and a function
datecmp() that takes two dates as arguments, compares them and returns -1,
0, or 1:

@keys = sort { datecmp(@foo{$a,$b}) || $a cmp $b } keys %foo

@keys now contains the keys of %foo, in such an order that the hash-slice
@foo{@keys} has the values in sorted order. The trick is to sort the
keys, but 'compare' them by comparing their respective values. The
'|| $a cmp $b' bit causes keys with the same value to be sorted lexically,
thus providing a guaranteed order. At this point you can iterate through
@keys in order, doing whatever you need to do.

For efficiency, you may want to inline the call to datecmp in the sort
block.

Philip Guenther

----------------------------------------------------------------
Philip Guenther UNIX Systems and Network Administrator
Internet: guen...@gac.edu Phonenet: (507) 933-7596
Gustavus Adolphus College St. Peter, MN 56082-1498
I am _not_ a representative sample of the Gustavus Community. Yeah, right...
Source code never lies (it just misleads). (Programming by Purloined Letter?)

[Tom Christiansen]

[courtesy cc sent via email]

In comp.lang.perl.misc,

gott...@grace.CS.ORST.EDU (Shikha Ghosh Gottfried) writes:
: I have an associative array that contains names as keys and dates
:(just strings) as values. Is there a way to sort the array by the
:dates so that I can print out the array in descending date order? Also please
:note that the dates must be the values, not the keys, and they are
:not necessarily unique.
: The standard way of sorting (@sorted = sort datecmp keys %mylist)
:seems to only allow me to sort an associative array by key (or by
:value) and puts the result into a scalar array, but I lose the second
:part of each key/value pair if I do this.

Um, you do??? I don't think so....

Assuming unix-style epochdates for values....

for (sort {
$mylist{$b} <=> $mylist{$a}
||
$a cmp $b
} keys %mylist)
{
printf "%-12s %s\n", $_, scalar localtime $mylist{$_};
}

See

ftp://mox.perl.com/pub/perl/info/everything_to_know/sorting

for some extra bits.

--tom
--
Tom Christiansen Perl Consultant, Gamer, Hiker tch...@mox.perl.com

A programmer is a machine for converting coffee into code.

[Jan Schipmolder]

gott...@grace.CS.ORST.EDU (Shikha Ghosh Gottfried) writes:
: I have an associative array that contains names as keys and dates
: (just strings) as values. Is there a way to sort the array by the
: dates so that I can print out the array in descending date order? Also please

Please refer to

5.6) How can I sort an associative array by value instead of by key?

in the FAQ.

--
--
Congratulations, a attention good have pretty span. you
jan b schipmolder
sc...@lmsc.lockheed.com

[Bennett Todd]

In article <GUENTHER.95...@lunen.gac.edu>,
Philip Guenther <guen...@gac.edu> wrote:
>[...]

> @keys = sort { datecmp(@foo{$a,$b}) || $a cmp $b } keys %foo

>[...]

>For efficiency, you may want to inline the call to datecmp in the sort
>block.

Or for possibly more efficiency, ensure that the calls only happen once per
record, rather than approximately NlogN times, with the Schwartz
transformation:-)

@keys = map { $_->[0] }
sort { $a->[1] <=> $b->[1] or $a cmp $b }
map { [ $_, datexform($foo{$_}) ] } keys %foo;

Note that datexform turns the values of $foo into easily-compared scalar
values; I'd turn 'em into Unix-style seconds-since-the-epoch. Indeed, I'd
try to ensure that they were already in that format, in which case the
datexform() would disappear leaving

@keys = map { $_->[0] }
sort { $a->[1] <=> $b->[1] or $a cmp $b }
map { [ $_, $foo{$_} ] } keys %foo;

which would likely be slower than the more straightforward

@keys = sort { $foo{$a} <=> $foo{$b} or $a cmp $b } keys %foo;

Randal's amazingly cryptic idiom is beautifully explained in Tom
Christiansen's

ftp://ftp.perl.com/pub/perl/doc/everything_to_know/sorting

But for a quick precis, where the original just sorts an array of keys, with
a __slow__ sort function, this thing sorts an array of references to
anonymous arrays; each anonymous array contains the original key and the
desired derived sort key. Then it pulls the (sorted) keys out of the
(sorted) array of references to anonymous arrays. The first map is pulling
the keys back out; the second map is building the array of references to
anonymous arrays.

-Bennett
b...@mordor.com

[Randal L. Schwartz]

>>>>> "Bennett" == Bennett Todd <b...@ritz.mordor.com> writes:

Bennett> Or for possibly more efficiency, ensure that the calls only happen once per
Bennett> record, rather than approximately NlogN times, with the Schwartz
Bennett> transformation:-)

Bennett> @keys = map { $_->[0] }
Bennett> sort { $a->[1] <=> $b->[1] or $a cmp $b }
Bennett> map { [ $_, datexform($foo{$_}) ] } keys %foo;

That last piece in the sort expression means that your fall back is
the stringification of the listref. Do you really want that? I'd
settle for:

@keys = map { $_->[0] }

sort { $a->[1] <=> $b->[1] or $a->[0] cmp $b->[0] }

map { [ $_, datexform($foo{$_}) ] } keys %foo;

since then what you are sorting by is the original keys, guaranteed
unique, and even "desk computable" (one of my programming criteria).

print "Just another Perl hacker," # but not what the media calls "hacker!" :-)
# legal fund: $5288.56 collected, $112379.50 spent; email fu...@stonehenge.com for details
--
Name: Randal L. Schwartz / Stonehenge Consulting Services (503)777-0095
Keywords: Perl training, UNIX[tm] consulting, video production, skiing, flying
Email: <mer...@stonehenge.com> Snail: (Call) PGP-Key: (finger mer...@ora.com)
Web: <A HREF="http://www.teleport.com/~merlyn/">My Home Page!</A>
Quote: "I'm telling you, if I could have five lines in my .sig, I would!" -- me

[Mark P Conmy]

In article <41tdho$1...@engr.orst.edu> gott...@grace.CS.ORST.EDU (Shikha Ghosh Gottfried) writes:

>>>>> "S" == Shikha Ghosh Gottfried <gott...@grace.CS.ORST.EDU> writes:
S> I have an associative array that contains names as keys and
S> dates (just strings) as values. Is there a way to sort the array by
S> the dates so that I can print out the array in descending date
S> order? Also please note that the dates must be the values, not the
S> keys, and they are not necessarily unique. The standard way of
S> sorting (@sorted = sort datecmp keys %mylist) seems to only allow
S> me to sort an associative array by key (or by value) and puts the
S> result into a scalar array, but I lose the second part of each
S> key/value pair if I do this.

Use "values" instead of "keys"? ;-)

Mark Conmy
Support Team, School of Computer Studies,
University of Leeds, U.K.