比較しないソートの作成 in Perl DouKaku?

ソート対象のデータ同士で一切比較などを行わずにソートし、ソート結果を出力するプログラムを作成してください。条件は以下の通り。
・最低値・最大値・個数・並び替え対象の4つを引数として受け取る
・最大値と最低値はあくまで取りうる可能性であり、実際に出現することを保障するものではない。
・同値が複数出現することがある。
・入出力方法及びフォーマットは自由、関数として実装し引数に渡す形でも良い。
・小数点以下の数値が渡されることはないが、負の数は渡される可能性がある。
・最大値や最低値を元に算出した数値との比較は使用しても問題ありません。
・出来るだけ多様な条件のデータをソートできるアルゴリズムを使ってください(データが多少多いときや一定の並び順だとソート失敗するものはダメ)
・昇順降順はどちらでもかまいません

以下サンプル入出力
>>入力
-1 10 10
-1 9 4 8 9 6 3 9 5 2
>>出力
-1 2 3 4 5 6 8 9 9 9

perlが無かったので。
アルゴリズムはバケツソートです。

use strict;

sub bucket_sort
{
  my ($min, $max, $num, @data) = @_;

  my @bucket;
  eval {
    for ( map { [$_ - $min,$_] } @data) {
      $bucket[$_->[0]] = [] if !$bucket[$_->[0]];
      push @{$bucket[$_->[0]]}, $_->[1];
    }
  };
  if ( $@ ) {
    bucket_sort($min-1,$max,$num,@data);
  }
  else {
    map { @$_ } grep { $_ } @bucket;
  }
}

$,=', '; $\="\n";
print bucket_sort(qw/-1 10 10 -1 9 4 8 9 6 3 9 5 2/);
print bucket_sort(qw/1 10 10 -1 9 4 8 9 6 3 9 5 2/);

バケットソートです。ワンライナーで書いてみました。
最大値と個数は無視します。

1	($n,$x,$c,@s)=@ARGV;$b[$_-$n]++for@s;$b[$_]&&print(($_+$n.' ')x$b[$_])for 0..$#b

DouKaku?

比較しないソートの作成

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq