in reply to Check if sort has changed order

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;
}

[download]

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

Replies are listed 'Best First'.
Re^2: Check if sort has changed order
by Anonymous Monk on May 10, 2013 at 23:17 UTC

    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 

    $ perl -le " print sort { warn $f=$a <=> $b; $f } 1,2,3,4,5
-1 at -e line 1.
-1 at -e line 1.
-1 at -e line 1.
1 at -e line 1.
-1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
12345

$ perl -le " print sort { warn $f=$a <=> $b; $f } 5,4,3,2,1
1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
12345

$ perl -le " print sort { warn $f=$a <=> $b; $f } 1,4,2,3,5
-1 at -e line 1.
-1 at -e line 1.
-1 at -e line 1.
-1 at -e line 1.
1 at -e line 1.
-1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
1 at -e line 1.
12345

$ perl -le " @f; print sort { $f=$a <=> $b; printf qq{%3s == %3s <=> %
+3s\n}, $f,$a,$b; push @f,$f; $f } 1 .. 11; print int @f; print  qq{@f
+}; "
 -1 ==   1 <=>   2
 -1 ==   3 <=>   4
 -1 ==   5 <=>   6
 -1 ==   7 <=>   8
 -1 ==   9 <=>  10
 -1 ==   1 <=>   3
  1 ==   3 <=>   2
 -1 ==   1 <=>   5
  1 ==   5 <=>   2
  1 ==   5 <=>   3
  1 ==   5 <=>   4
 -1 ==   7 <=>   9
  1 ==   9 <=>   8
 -1 ==   7 <=>  11
  1 ==  11 <=>   8
  1 ==  11 <=>   9
  1 ==  11 <=>  10
 -1 ==   1 <=>   7
  1 ==   7 <=>   2
  1 ==   7 <=>   3
  1 ==   7 <=>   4
  1 ==   7 <=>   5
  1 ==   7 <=>   6
1234567891011
23
-1 -1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1 1 1 1

    [download]
[reply]
[d/l]

In Section Seekers of Perl Wisdom