Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
PerlMonks  

Re^2: sort of misunderstanding of sort

by Discipulus (Canon)
on Mar 22, 2023 at 08:02 UTC ( [id://11151120] : note . print w/replies, xml ) 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.