帰ってきたネコブログ

「ゲーム制作者のための物理シミュレーション 剛体編（Amazon）」という本を読んでいたら、
基数ソート（Radix sort）なるものを見つけたのでPerlで実装してみた。

use v5.16;
use strict;
use warnings;
use integer;

use List::Util qw/shuffle/;

use constant PRINT_NUMBERS_PER_LINE => 5;

my @numbers = shuffle( 1..20 );

say '=== input  numbers ===';
print_numbers( @numbers );

#say '=== sorted numbers ===';
#print_numbers( perl_sort(@numbers) );

say '=-=-=-=-=-=-=-=-=-=-=-=';
my @my_sorted = my_sort( @numbers );
say '=-=-=-=-=-=-=-=-=-=-=-=';

say '=== sorted numbers ===';
print_numbers( @my_sorted );

sub print_numbers {
	my $n = scalar( @_ );

	my $i = 0;
	while ( $i < $n ) {
		my $m = PRINT_NUMBERS_PER_LINE;
		$m = $n - $i if $n < ($i + $m);

		my @wk = ();
		for (my $j=0; $j<$m; $j++, $i++) {
			push @wk, sprintf('%3d', $_[$i]);
		}

		print join( ',', @wk );
		print ( ($i < $n) ? ",\n" : "\n" );
	}
}

sub perl_sort {
	return sort { $a <=> $b } @_;
}

sub my_sort {
	my @src = @_;
	my $lshift = 2;

	my $step = 1 << $lshift;
	my $mask = $step - 1;

	my @dst = ();
	for ( 0..2 ) {
		printf( "mask = 0x%02X\n", $mask );
		my $rshift = $_ * $lshift;

		my @wk = map { []; } 1..$step;
		foreach ( @src ) {
			push @{$wk[($_ & $mask) >> $rshift]}, $_;
		}

		for (my $i=0; $i<$step; $i++) {
			print "$i: ", join(",", @{$wk[$i]}), "\n";
		}

		@dst = ();
		for (my $i=0; $i<$step; $i++) {
			push @dst, @{$wk[$i]};
		}

		@src = @dst;
		$mask <<= $lshift;
	}

	return @dst;
}

実行するとこんな感じ。

$ perl aaa.pl
=== input numbers ===
7, 16, 3, 10, 4,
5, 18, 17, 13, 9,
6, 1, 12, 2, 8,
14, 15, 11, 19, 20
=-=-=-=-=-=-=-=-=-=-=-=
mask = 0x03
0: 16,4,12,8,20
1: 5,17,13,9,1
2: 10,18,6,2,14
3: 7,3,15,11,19
mask = 0x0C
0: 16,17,1,18,2,3,19
1: 4,20,5,6,7
2: 8,9,10,11
3: 12,13,14,15
mask = 0x30
0: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
1: 16,17,18,19,20
2:
3:
=-=-=-=-=-=-=-=-=-=-=-=
=== sorted numbers ===
1, 2, 3, 4, 5,
6, 7, 8, 9, 10,
11, 12, 13, 14, 15,
16, 17, 18, 19, 20

本に載ってる説明では、
1の位を参照して、10の位を参照して、100の位を参照してって内容だったけど、
実際にコードとして記述するのは、下位ビットから上位ビットの順に、
参照した値を添え字に使って配列に格納して、それを連結してを繰り返す。
比較したり、交換が発生しないので、ソートっぽくないんだけど、
見ての通り、あれよあれよとしてるうちにソートされる。

実装方法は、これ以外にもあるみたいだけど、
本当にソートされるのか気になったので実装した次第。
勘の良い人なら気付いたと思うけど、このソートは整数値にしか適用できない。

思い付く用途として、
画像のノイズ除去に使われるメディアンフィルタには良んじゃないかなーって思った。

おしまい。

カテゴリー: Perl, コンピューター by ネコ on 2015年07月17日 | タグ: アルゴリズム > ソート > メモ