Your skill will accomplishwhat the force of many cannot PerlMonks

### Numeric sorting WITHOUT <=>

 on Oct 09, 2012 at 21:48 UTC Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

I know how to sort with the spaceship/starship operator but I can't figure out the code for sorting numeric keys without it. This is what I have so far, which as you can see, I haven't gotten very far. Any help?

%jetsons = ( 7 => 'Judy', 10 => 'Jane', 11 => 'George', 2 => 'Elroy', 100=> 'Rosey', 1 => 'Astro', 19 => 'Mr. Spacely', 22 => 'Mr. Cogswell'); for (\$key = 0; \$key++; \$key>=100) { if (\$key == keys) { }

Replies are listed 'Best First'.
Re: Numeric sorting WITHOUT <=>
by AnomalousMonk (Bishop) on Oct 09, 2012 at 22:03 UTC

Why, oh why would you want to do numeric sorting without the numeric comparison operator? Interview question? Failure of communication? XY Problem? In any event, maybe something like this:

>perl -wMstrict -le "my %jetsons = ( 7 => 'Judy', 10 => 'Jane', 11 => 'George', 2 => 'Elroy', 100=> 'Rosey', 1 => 'Astro', 19 => 'Mr. Spacely', 22 => 'Mr. Cogswell' ); ;; my @sorted = sort non_spaceship keys %jetsons; print qq{@sorted}; ;; sub non_spaceship { return \$a < \$b ? -1 : \$a > \$b ? 1 : 0 } " 1 2 7 10 11 19 22 100

Not my idea, its for a class. That might work but he hinted at using nested loops to numerically sort the keys.

Ah: "Give a man a fish and he will eat for a day. Tell a man to beat the fish to death with a baseball bat and he will happily use a fishing hook and line for all the rest of his days."

If he's talking about nested loops, then you're probably not supposed to use the Perl sort function at all, but instead to implement a sorting algorithm from scratch. Hopefully, then, the class has already covered at least one sorting algorithm for you to implement. If not, google can provide explanations of how several sorting algorithms work, then it's just a matter of translating the algorithm's description into Perl code.
Re: Numeric sorting WITHOUT <=>
by roboticus (Chancellor) on Oct 10, 2012 at 02:52 UTC

Just look at the definition of the <=> operator, and you should be able to code it up easily: \$a <=> \$b is negative when \$a should precede \$b, positive if \$a should follow \$b, and zero if \$a and \$b could be the same position. So if you're sorting numbers, you could just use \$a - \$b, as it returns appropriate values. Using \$b - \$a would sort in reverse:

\$ cat ex_sort_odd.pl #!/usr/bin/perl use strict; use warnings; my @a; push @a, int(100*rand) for 1 .. 10; print "LIST: ", join(" ", @a), "\n"; my @b = sort { \$a - \$b } @a; print "ASC: ", join(" ", @b), "\n"; @b = sort { \$b - \$a } @a; print "DESC: ", join(" ", @b), "\n"; \$ perl ex_sort_odd.pl LIST: 27 78 66 70 19 37 48 82 67 90 ASC: 19 27 37 48 66 67 70 78 82 90 DESC: 90 82 78 70 67 66 48 37 27 19

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Re: Numeric sorting WITHOUT <=>
by GrandFather (Sage) on Oct 10, 2012 at 01:39 UTC

Don't use the C for loop, especially when you can't remember the order of the parts in the ()! Instead use a Perl for loop:

for my \$key (0 .. 100) {

which is not only clearer and shorter, but will actually do what you want.

True laziness is hard work
Re: Numeric sorting WITHOUT <=>
by kcott (Bishop) on Oct 09, 2012 at 22:24 UTC

<=> is the appropriate operator to use. Why do you want to write code without it? What were you hoping to use in its stead? Do you want to write your own sort routine?

I have no idea what you were hoping to achieve by posting this code:

for (\$key = 0; \$key++; \$key>=100) { if (\$key == keys) { }

It's wrong in more ways than I care to enumerate. Apart from the syntax and logic errors, it tells us nothing about what you are attempting to achieve.

My best guess at what you want does use the <=> operator:

say \$jetsons{\$_} for sort { \$a <=> \$b } keys %jetsons;

Please read the perl documentation to find out how to write a for loop (with three arguments) and the syntax for if statements and the keys function.

-- Ken

Re: Numeric sorting WITHOUT <=>
by jandrew (Chaplain) on Oct 09, 2012 at 22:53 UTC
Re: Numeric sorting WITHOUT <=>
by GrandFather (Sage) on Oct 10, 2012 at 01:43 UTC
my @sorted = sort {sprintf ('%09d', \$a) cmp sprintf ('%09d', \$b)} keys + %jetsons;
True laziness is hard work
Don't really need the explicit cmp:

my @sorted = sort map { sprintf '%09d', \$_ } keys %jetsons;

But that's nearly half the length so it can't be near half so good. :-)

True laziness is hard work
Re: Numeric sorting WITHOUT <=>
by BrowserUk (Pope) on Oct 10, 2012 at 05:46 UTC

@sertedNumbs = sort{ \$a-\$b } unsortedNumbs;

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
Re: Numeric sorting WITHOUT <=>
by BillKSmith (Prior) on Oct 10, 2012 at 03:31 UTC

Here is one bad way to do it! No comparisons at all.

use strict; use warnings; my %jetsons = ( 7 => 'Judy', 10 => 'Jane', 11 => 'George', 2 => 'Elroy', 100=> 'Rosey', 1 => 'Astro', 19 => 'Mr. Spacely', 22 => 'Mr. Cogswell' ); for my \$i (0..100) { print "\$i => \$jetsons{\$i}\n" if exists \$jetsons{\$i}; }
Bill

One may not know the minimum & maximum values without inspecting to use range operator, so ...

use strict; use warnings; use List::MoreUtils 'minmax'; my %hash = ( ... ); # Absurdity is to find end values in order to avoid # numeric comparison. my ( \$min , \$max ) = minmax keys %hash; for my \$i ( \$min .. \$max ) { ... }
Yes, this is indeed a "bad way" to do it! Compared with sort(), this will be slow (20..99) yield no result and it doesn't scale well. And I guess that you would in the general case, have to read every key to find the maximum key value.
Re: Numeric sorting WITHOUT <=>
by tobyink (Canon) on Oct 10, 2012 at 06:22 UTC
use Data::Dumper; WITHOUT_USING_SPACESHIP: { my @array = qw( 7 100 12 1 4 2 88 007 ); @array = sort { \$a>\$b ? 1 : -1 } @array; print Dumper \@array; } WITHOUT_USING_SORT_AT_ALL: { my @array = qw( 7 100 12 1 4 2 88 007 ); for my \$i (0 .. \$#array) { for my \$j (\$i .. \$#array) { @array[\$i, \$j] = @array[\$j, \$i] if \$array[\$i] > \$array[\$j] +; } } print Dumper \@array; }

What sorting algorithm is that? I can never remember their names. It may be bubble sort.

perl -E'sub Monkey::do{say\$_,for@_,do{(\$monkey=[caller(0)]->[3])=~s{::}{ }and\$monkey}}"Monkey say"->Monkey::do'

And here's a Perl 5.16 implementation of quicksort...

use v5.16; my @sorted = (sub { return @_ unless @_ > 1; my \$pivot = splice(@_, int(@_/2), 1); my (@small, @big); push @{ \$_ < \$pivot ? \@small : \@big }, \$_ for @_; return (__SUB__->(@small), \$pivot, __SUB__->(@big)) })->(@unsorted);

Can be made a little neater using List::MoreUtils...

use v5.16; use List::MoreUtils 'part'; my @sorted = (sub { return @_ unless @_ > 1; my \$pivot = splice(@_, int(@_/2), 1); my (\$small, \$big) = part { \$_ > \$pivot } @_; return (__SUB__->(@\$small), \$pivot, __SUB__->(@\$big)) })->(@unsorted);

In older Perls, without __SUB__ you can't recursively call a truly anonymous sub, so you need to have some kind of way of referring to the sub, such as assigning it to a lexical variable...

my @sorted = do { my \$SUB; \$SUB = sub { return @_ unless @_ > 1; my \$pivot = splice(@_, int(@_/2), 1); my (@small, @big); push @{ \$_ < \$pivot ? \@small : \@big }, \$_ for @_; return (\$SUB->(@small), \$pivot, \$SUB->(@big)) }}->(@array);
perl -E'sub Monkey::do{say\$_,for@_,do{(\$monkey=[caller(0)]->[3])=~s{::}{ }and\$monkey}}"Monkey say"->Monkey::do'
sort uses mergesort by default, not quicksort. That could be a more appropriate choice?

Your last snippet has a memory leak.

Re: Numeric sorting WITHOUT <=>
by ikegami (Pope) on Oct 10, 2012 at 01:55 UTC
my (\$min) = keys(%jetsons); my \$max = \$min; for (keys(%jetsons)) { \$max = \$_ if \$_ > \$max; \$min = \$_ if \$_ < \$min; } my @sorted; for (\$min..\$max) { push @sorted, \$_ if exists(\$jetsons{\$_}); }
my (\$min) = keys(%jetsons); This is the number of keys in %jetsons.
This is not the min.
my (\$min) = keys(%jetsons); This is the number of keys in %jetsons.

Actually, it's a randomly (insofar as the hashing algorithm is random) chosen key from the hash. The assignment is in list context and seeds the min/max finder loop that follows.

>perl -wMstrict -le "my %jetsons = qw(aa 1 bb 2 cc 3 dd 4 ee 5); my (\$min) = keys %jetsons; print \$min; " cc

Update: ikegami's code works. (Never doubt a Pope.)

No.
# keys in scalar context: Number of keys. my \$min = keys(%jetsons); # keys in list context: List of keys. First one is assigned my (\$min) = keys(%jetsons);
Thank you! This worked and it actually made it easier for me to understand how it was done instead of using the was my professor said we should!

This worked and it actually made it easier for me to understand how it was done

My code does NOT demonstrate how sorting is usually done. It takes a different and silly approach in response to your equally silly requirement. It would take forever for my solution to sort

my %jetsons = ( 0 => "a", 4000000000 => "b" );
Re: Numeric sorting WITHOUT <=>
by Marshall (Abbot) on Oct 10, 2012 at 03:41 UTC
If you want to sort by a numeric value, using the "spaceship" operator "<=>" is THE way to go!

If you sort by "ascii order" on a numeric field, then you have to have the same number of "ascii digits" or the sort will not work.

!/usr/bin/perl -w use strict; my %jetsons = ( 7 => 'Judy', 10 => 'Jane', 11 => 'George', 2 => 'Elroy', 100=> 'Rosey', 1 => 'Astro', 19 => 'Mr. Spacely', 22 => 'Mr. Cogswell'); foreach my \$key (sort { \$a<=>\$b } keys %jetsons) { printf "%-5s %s\n", \$key, \$jetsons{\$key}; } __END__ 1 Astro 2 Elroy 7 Judy 10 Jane 11 George 19 Mr. Spacely 22 Mr. Cogswell 100 Rosey
Use <=> to compare numeric values.
Use cmp to compare string values.

I often advocate date/time strings like this: 2010-10-03 0837
A string like that (YYYY-MM-DD HHMM) with leading zeros, can be compared against other date/times in a simple way (ASCII sort), but the leading zeroes are important! A simple ASCII sort order will work, but ONLY if the fields are of constant width and have leading zeroes.

Re: Numeric sorting WITHOUT <=>
by Tux (Abbot) on Oct 10, 2012 at 10:09 UTC

TIMTOWTDI

my @sorted_keys = map { unpack "l>", \$_ } sort map { pack "l>", \$_ } k +eys %jetsons;

Enjoy, Have FUN! H.Merijn
Re: Numeric sorting WITHOUT <=>
by ria1328 (Initiate) on Oct 10, 2012 at 17:11 UTC

Thank you to everyone else too, but ikigami's code worked best due to the fact that we aren't that far into our perl scripting yet so his was the easiest to understand for a beginner!

Create A New User
Node Status?
node history
Node Type: perlquestion [id://998088]
Approved by mbethke
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (10)
As of 2019-12-06 15:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Strict and warnings: which comes first?

Results (156 votes). Check out past polls.

Notices?