シェルソート
挿入ソートを流用。少し手がかかった。。。
use strict; use warnings; my $trials = 30; my %h = map { int rand $trials => 1 } 1..$trials; my @target = keys %h; print join(" ", @target); print "\n"; @target = shell_sort(@target); print join(" ", @target); print "\n"; sub shell_sort { my @ary = @_; my $max_index = $#ary; my $interval = $max_index >> 1; while ($interval) { my $key = 0; my @h = ( [] ) x $interval; while (1) { my $shift = shift @ary; defined $shift or last; $h[$key] = [@{ $h[$key] }, $shift]; $key++; $key %= $interval; } $h[$_] = [isort(@{ $h[$_] })] for 0..$interval-1; push @ary, (shift @{ $h[$_ % $interval] }) for 0..$max_index; print join(" ", map { ( $_ % $interval ? ' ' : '| ') . $ary[$_] } 0..$max_index); print " (interval : $interval) \n"; $interval >>= 1; } @ary; } sub isort { my @ary = @_; my @ret = (shift @ary); while (1) { my $element = shift @ary; defined $element or last; my @temp; while (1) { my $shift = shift @ret; unless (defined $shift) { @temp = (@temp, $element); last; } if ($shift < $element) { @temp = (@temp, $shift); } else { @temp = (@temp, $element, $shift, @ret); last; } } @ret = @temp; } @ret; }
部分的に挿入ソート(別に何ソートでもいいような気もするけど)していく。たとえば2段目では(0,10,20,21,28),(2,3,5,8,13)という部分列がそれぞれソートされている。
21 2 1 18 0 13 27 6 28 3 9 12 20 8 24 19 10 5 | 10 2 1 12 0 8 24 6 | 21 3 9 18 20 13 27 19 | 28 5 (interval : 8) | 0 2 1 6 | 10 3 9 12 | 20 5 24 18 | 21 8 27 19 | 28 13 (interval : 4) | 0 2 | 1 3 | 9 5 | 10 6 | 20 8 | 21 12 | 24 13 | 27 18 | 28 19 (interval : 2) | 0 | 1 | 2 | 3 | 5 | 6 | 8 | 9 | 10 | 12 | 13 | 18 | 19 | 20 | 21 | 24 | 27 | 28 (interval : 1) 0 1 2 3 5 6 8 9 10 12 13 18 19 20 21 24 27 28