The stupid question is the question not asked PerlMonks

### Check if sort has changed order

by HYanWong (Acolyte)
 on May 10, 2013 at 09:31 UTC Need Help??
HYanWong has asked for the wisdom of the Perl Monks concerning the following question:

Hi all, Is there a simple way to check if a call to sort has changed the order of a list? Or do I have to actually compare the lists before and after the sort (e.g. using ~~)?

Replies are listed 'Best First'.
Re: Check if sort has changed order
by davido (Archbishop) on May 10, 2013 at 15:07 UTC

Sorting is an O(n log n) operation. Testing a list for sortedness is an O(n) operation. Test first, then sort if necessary.

```use strict;
use warnings;
use List::Util qw( first );

my @x = qw( 1 3 2 4 5 );

if( defined first { \$x[\$_] > \$x[\$_+1] } 0 .. \$#x - 1 ) {
@x = sort { \$a <=> \$b } @x;
}

Strategies for testing whether a change has been made after sorting has been applied will either involve a checksum of some type (ie, take an MD5 of the list's contents before and again after), or keeping a copy of the pre-sorted list for comparison. One way you're throwing CPU cycles at the problem, and the other way, you're throwing memory at it. If you can just check whether sorting is necessary ahead of time, you conserve both.

Dave

If you can just check whether sorting is necessary ahead of time, you conserve both.

I think I agree with you :)

I thought maybe its detectible from within sort callback if order has changed, but it doesn't look that way

Re: Check if sort has changed order
by LanX (Chancellor) on May 10, 2013 at 12:39 UTC
> Or do I have to actually compare the lists before and after the sort (e.g. using ~~)?

Yes!

But could you please explain your use case? I'm smelling an XY question... =)

Cheers Rolf

( addicted to the Perl Programming Language)

Re: Check if sort has changed order (eq)
by Anonymous Monk on May 10, 2013 at 09:38 UTC
```my @f = ( 4, 2 );
my @g = sort @f;
if( "@f" eq "@g" ){
die "already sorted, can't have that\n"
}

Ha, stupid memory allocation tricks

```my @f = ( 4, 2 );
print join ' ', int \\$_, \\$_, "\$_\n" for @f;print "\n";
@f = sort @f;
print join ' ', '#', int \\$_, \\$_, "\$_\n" for @f;print "\n";
my \$prev = 0;
for my \$next ( @f ){
if( \$prev ){
die "BEEN SORTED" if \$prev > \\$next;
}
\$prev = \\$next;
}
__END__
\$ perl fa
4165804 SCALAR(0x3f90ac) 4
4165980 SCALAR(0x3f915c) 2

# 4165980 SCALAR(0x3f915c) 2
# 4165804 SCALAR(0x3f90ac) 4

BEEN SORTED at fa line 8.
That won't work for whatever sort condition.

I'd probably rather compare the MD5 checksum of the scalar references in the list before and after the sort.

This seems to be a very clever way "to actually compare the lists."
Bill
Re: Check if sort has changed order
by hdb (Prior) on May 10, 2013 at 14:22 UTC

Why don't you test if the array needs sorting first? This probably takes as much time as comparing the result to the original. And you might save the sorting if not needed.

Re: Check if sort has changed order
by johngg (Abbot) on May 10, 2013 at 15:47 UTC

Use Digest::MD5 to see if something has changed. The md5_hex() function will concatenate its arguments then operate on the concatenated string.

```\$ perl -Mstrict -Mwarnings -MDigest::MD5=md5_hex -E '
my @arr1 = qw{ tiger bear shark lion };
say md5_hex( @arr1 );
say md5_hex( sort @arr1 );'
4c15f2e87b25ac112649edfd426d5082
27f304e4e99072211806f923bbb39705
\$ perl -Mstrict -Mwarnings -MDigest::MD5=md5_hex -E '
> my @arr1 = qw{ antelope cow deer sheep };
> say md5_hex( @arr1 );
> say md5_hex( sort @arr1 );'
1f0210f9b5d6dababea92da7018905da
1f0210f9b5d6dababea92da7018905da
\$

I hope this is of interest.

Cheers,

JohnGG

Re: Check if sort has changed order
by Anonymous Monk on May 10, 2013 at 14:22 UTC

Well, I had the hair-ball idea of cooking the sort-compare function to detect if it actually produced a particular result-type during the sort ... but it didn’t work.   Oh, well.

Re: Check if sort has changed order
by Rahul6990 (Beadle) on May 10, 2013 at 10:54 UTC

Actually it will not!

The SO question is about comparing unordered sets, while the OP explicitly needs to assure that the order of identical sets didn't change.

Cheers Rolf

( addicted to the Perl Programming Language)

You can apply array_diff function on the sorted and unsorted file and check the output file to see weather sort had done any modification or not.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://1032922]
Front-paged by Arunbear
help
Chatterbox?
 [msh210]: I think I just found a lie in perldoc. [msh210]: warn: "If the last element of LIST does not end in a newline, it appends the same file/line number text as die does." [msh210]: perl -e'warn "test\$/", "" ' [msh210]: doesn't append anything. [msh210]: It should say "If the last nonempty element of LIST" or "If the string thus to be printed does not end in a newline"" [msh210]: Am I wrong? [shmem]: no. You're right. [msh210]: About time... last time I was right was... I don't even remember when. [shmem]: perl -e 'warn "test\$/", ^@^ '

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (9)
As of 2017-04-24 12:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I'm a fool:

Results (439 votes). Check out past polls.