P is for Practical PerlMonks

### Re^2: sort of misunderstanding of sort

by Discipulus (Canon)
 on Mar 22, 2023 at 08:02 UTC Need Help??

in reply to Re: sort of misunderstanding of sort
in thread sort of misunderstanding of sort

Thanks ikegami and all who answered,

while now I understand better the matter of sorting, your sentence

> Returning garbage values doesn't not increase the number of comparisons

does not seems to be confirmed by my last example: perl -le "@a = sort{ print qq(\$a \$b); -1 }@ARGV" 1 2 3 4

Infact returning garbage ie: -1 seems to produce always an iteration more in respect of returning 0 or 1

If I understand the mergesort, the above example, should go like:

```        1 2 3 4

[1 2] [3 4]

[1 3] [3 2] [2 4]

So only [1 4] is skipped because derived by previous [1 2] [2 4] To notice also that returning -1 as garbage returns a weird sorted list 1 3 2 4 while returning always 1 produce (as I expected) a reversed list: 4 3 2 1

As side effect hacking sort can lead to a new shuffle :)

```# naive shuffle

perl -le "print for sort  { int rand(3) - 1 } @ARGV" 1 2 3 4 5

1
3
5
2
4

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Replies are listed 'Best First'.
Re^3: sort of misunderstanding of sort
by ikegami (Patriarch) on Mar 22, 2023 at 19:53 UTC

I did mention there are optimizations at play over a pure merge sort.

In fact, my testing shows that passing n sorted items, it only performs n comparisons. This is clearly not the behaviour of a pure merge sort.

But I was indeed wrong about the amount being constant.

• Merging 1,2,3 with 4,5,6 requires three comparisons.
• Merging 1,7,8 with 4,5,6 requires four comparisons.
In fact, my testing shows that passing n sorted items, it only performs n comparisons.

Except kind of anomaly in ~ 5..17 range:

```use strict;
use warnings;
use Chart::Gnuplot;

my @x = ( 2 .. 50 );
my @y = map {
my \$n = 0;
1 for sort { ++ \$n; \$a <=> \$b } 1 .. \$_;
\$n
} @x;

my \$chart = Chart::Gnuplot-> new(
gnuplot  => 'gnuplot.exe',
terminal => 'dumb size 60, 30',
xrange   => [ 0, 50 ],
yrange   => [ 0, 50 ],
title    => 'Number of comparisons vs pre-sorted array length',
);
my \$dataset = Chart::Gnuplot::DataSet->new(
xdata => \@x,
ydata => \@y,
style => 'impulses',
);

__END__

Number of comparisons vs pre-sorted array length

50 +--------------------------------------------------+
|         +         +          +         +       **|
|                                              ****|
|                                            ******|
|                                          ********|
40 |-+              *                       **********|
|                *                     ************|
|                *                   **************|
|                *                 ****************|
|              ***               ******************|
30 |-+           ****             ********************|
|            *****           **********************|
|           ******        *************************|
|          *******     ** *************************|
20 |-+        *******   **** *************************|
|        ********* ****** *************************|
|        **************** *************************|
|        **************** *************************|
|       ***************** *************************|
10 |-+    ****************** *************************|
|    ******************** *************************|
|    ******************** *************************|
|   ********************* *************************|
|  ********************** *************************|
0 +--------------------------------------------------+
0         10        20         30        40        50
Re^3: sort of misunderstanding of sort -- Discipulus's shuffle
by Discipulus (Canon) on Mar 22, 2023 at 08:43 UTC
Just for fun..

obfuscated shuffle can be sort {--\$|} but, as expected, List::Util shuffle is a bit more performant

```use strict;
use warnings;
use Benchmark qw(cmpthese);
use List::Util qw(shuffle);

my \$count = 10000;
my @numbers = 0..10000;

cmpthese(\$count, {
'List::Util::shuffle' => sub { my @shuffled = shuffle @numbers },
'Discipulus::shuffle' => sub { my @shuffled = sort { int rand(3) -
+ 1 } @numbers },
'Discipulus::--\$|fle' => sub { my @shuffled = sort { --\$| } @numbe
+rs },
});

__END__
Rate Discipulus::--\$|fle Discipulus::shuffle Lis
+t::Util::shuffle
Discipulus::--\$|fle  164/s                  --                -52%
+            -95%
Discipulus::shuffle  342/s                108%                  --
+            -89%
List::Util::shuffle 3107/s               1793%                809%
+              --

L*

There are no rules, there are no thumbs..
Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11151120]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others goofing around in the Monastery: (8)
As of 2024-02-27 22:32 GMT
Voting Booth?
My favourite way to spend a leap day ...

Results (26 votes). Check out past polls.