track how many moves to sort an array?

[Gerald Jones]

Lets say I have an array with 10 elements, such as:

@a = ( "ian", "albert", "chris", "ed", "bertram", "david", "john", "fred",
"george", "harry");

I am interested in determining how many moves it would take to sort this
alphabetically. Now, I could re-implement Perl's built in sort mechanism and
have an incremented value in there somewhere, but first I'd like to know if
there was any way to do this with the built-in sort. The perldoc says this:

[snip]

If SUBNAME or BLOCK is omitted, sorts in standard string comparison order. If
SUBNAME is specified, it gives the name of a subroutine that returns an integer
less than, equal to, or greater than 0, depending on how the elements of the
list are to be ordered. (The <=> and cmp operators are extremely useful in such
routines.)

[/snip]

Huh? And how can I extrapolate these number is into number of moves to get to:


@a = ( albert", "bertram", "chris", "david", "ed", "fred",
"george", "harry", "ian", "john" );


..... anyways? So far, I got:

$ perl -e 'while (<>) { push( @a, $_) } @b = sort { print $a <=> $b, "\n" } @a; foreach $b (@b) { print "$b" }'
zed
ded
head
bread
aded
0
0
0
0
0
aded
bread
head
ded
zed
$


Which is wrong, but I have no idea how to interpret this let alone determine
how close I am to being correct. Any insight any one has would be appreciated!

Thanks, Gerald

 

[Scott Bryce]

Lets say I have an array with 10 elements, such as:

@a = ( "ian", "albert", "chris", "ed", "bertram", "david", "john", "fred",
"george", "harry");

I am interested in determining how many moves it would take to sort this
alphabetically.

Though I'm not sure what purpose this serves, this does what you are
describing.


use strict;
use warnings;

my @list = qw( ian
albert
chris
ed
bertram
david
john
fred
george
harry);

my $count = 0;

@list = sort {$count ++; $a cmp $b} @list;

print join ', ', @list;
print "\nThe sort required $count steps.\n";

 

[Todd W]

Lets say I have an array with 10 elements, such as:

@a = ( "ian", "albert", "chris", "ed", "bertram", "david", "john", "fred",
"george", "harry");

I am interested in determining how many moves it would take to sort this
alphabetically. Now, I could re-implement Perl's built in sort mechanism and
have an incremented value in there somewhere, but first I'd like to know if
there was any way to do this with the built-in sort. The perldoc says this:

[snip]

If SUBNAME or BLOCK is omitted, sorts in standard string comparison order. If
SUBNAME is specified, it gives the name of a subroutine that returns an integer
less than, equal to, or greater than 0, depending on how the elements of the
list are to be ordered. (The <=> and cmp operators are extremely useful in such
routines.)

[/snip]

Huh? And how can I extrapolate these number is into number of moves to get to:


@a = ( albert", "bertram", "chris", "david", "ed", "fred",
"george", "harry", "ian", "john" );


.... anyways? So far, I got:

$ perl -e 'while (<>) { push( @a, $_) } @b = sort { print $a <=> $b,

"\n" } @a; foreach $b (@b) { print "$b" }'

<snip />

because you are comparing strings you need to use "cmp" instead of the
numeric comparison operator "<=>"

if you wouldve added a -w flag to your oneliner you'd of found that out.

Heres what I came up with:

[trwww@waveright trwww]$ perl
use warnings;
use strict;

my @orig = qw(ian albert chris ed bertram david john fred george harry);
my $count;
my @sort = sort( { $count++; $a cmp $b } @orig );
print "$count iterations:\n";
print map( "$_\n", @sort );
Ctrl-D
24 iterations:
albert
bertram
chris
david
ed
fred
george
harry
ian
john

Todd W.

 

[Jürgen Exner]

@list = sort {$count ++; $a cmp $b} @list;

Not quite. You are counting how often two elements are compared.
The OP was asking for how often elements are "moved" (by whatever definition
of "move").

jue

 

[Jürgen Exner]

Lets say I have an array with 10 elements, such as:

@a = ( "ian", "albert", "chris", "ed", "bertram", "david", "john",
"fred", "george", "harry");

I am interested in determining how many moves it would take to sort
this alphabetically.

This very much depends upon which sort algorithm you are using and how you
define a "move".

jue

 

[Scott Bryce]

Not quite. You are counting how often two elements are compared.

# Perhaps this is what the OP wanted?
@list = sort {$count ++ if $a gt $b; $a cmp $b} @list;

The OP was asking for how often elements are "moved" (by whatever definition
of "move").

As you point out, it depends on what the OP means by "move."

 

[Anno Siegel]

Scott Bryce ([email protected]) wrote on MMMMCLXXXII September
MCMXCIII in <URL:-- Jürgen Exner wrote:
--
-- > Not quite. You are counting how often two elements are compared.
--
-- # Perhaps this is what the OP wanted?
-- @list = sort {$count ++ if $a gt $b; $a cmp $b} @list;

No. That still counts compares, not moves. There's no way to count
the number of moves from within Perl.

The "number of moves" isn't well defined in view of the various sort
algorithms. Not every sort proceeds in place, moving elements back and
forth. What is the number of moves a merge sort? In a heap sort?
And how are they relevant? An indirect sort moves every element exactly
once.

Anno