比較しないソートの作成 in PostScript 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

post comment

Posted feedbacks - PostScript

PostScriptで、radix sort 基数2 です。特にかわったことはやっていない筈です。

%!PS

/AddToVector { % val [Vector]  AddToVector  [NewVector]
    [ 3 1 roll
    {
        1 index add exch
    } forall
    pop
    ]
} bind def

/RadixSortCore { % [Vector]  max  RadixSortCore  [NewVector]
    5 dict begin 
    /Max exch def
    /Vect exch def
    /Radix 1 def
    {
        /Vect
        [
            Vect {
                dup Radix and 0 ne {
                    pop
                } if
            } forall
            Vect {
                dup Radix and 0 eq {
                    pop
                } if
            } forall
        ] def
        Radix Max gt { exit } if
        /Radix Radix dup add def
    } loop
    Vect
    end
} bind def

/RadixSort { % min max [Vector] RadixSort [NewVector]
    2 index neg exch AddToVector exch 2 index sub
    RadixSortCore
    AddToVector
} bind def

% ============ Test Code ==============
-1024 2048 [ -510 10 7 12 45 120 -1024 -511 -512 249 1238 1274 ] RadixSort ==

DouKaku?

比較しないソートの作成

Posted feedbacks - PostScript

Index

Feed

Other

Link

Pathtraq