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

Mosh (Scheme) で書きました。データ個数を終了条件に使えばもっと効率よくできそうです。

(define count-sort (lambda (range-min range-max range-len data)
  (let loop1 ((i range-min) (result '()))
    (if (>= i range-max)
      result
      (loop1 (+ i 1) (append result
        (let loop2 ((ls data) (rs '()))
          (if (pair? ls)
            (loop2 (cdr ls) (if (= i (car ls)) (cons i rs) rs))
            rs))))))))

(write (count-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2)))
(newline)

しまった。。。
バケットソートというのがあるんですね。
あんまり余裕がないので Gauche で書き直し。

(use gauche.sequence)

(define bucket-sort (lambda (range-min range-max data-len data)
  (let* ((range-len (+ 1 (- range-max range-min)))
         (bucket (make-vector range-len 0))
         (result '()))
    (for-each (lambda (i)
      (let ((j (- i range-min)))
        (vector-set! bucket j (+ 1 (vector-ref bucket j)))))
      data)
    (for-each-with-index
      (lambda (i count)
        (set! result (append result
          (make-list count (+ i range-min)))))
      bucket)
    result)))

(define main (lambda (args)
  (write (bucket-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2)))
  (newline)
  0))

mc さんの #6658 を参考にして、だいぶすっきりしたコードになりました。
ありがとうございます。

(define bucket-sort (lambda (range-min range-max data-len data)
  (let ((bucket (make-vector (+ 1 (- range-max range-min)) '())))
    (for-each
      (lambda (i)
        (let ((j (- i range-min)))
          (vector-set! bucket j (cons i (vector-ref bucket j)))))
      data)
    (fold-right append '() (vector->list bucket)))))

素直に単純なビンソートで。

(use srfi-1)
(use srfi-43)

(define (bin-sort vmin vmax n xs)
  (let ((v (make-vector (- vmax vmin -1) 0)))
    (for-each (lambda (x)
                (inc! (ref v (- x vmin))))
              xs)
    (concatenate
     (vector-fold-right (lambda (i knil x)
                          (cons (make-list x (+ i vmin)) knil))
                        '() v))))

(define (main args)
  (print (bin-sort -1 10 10 '(-1 9 4 8 9 6 3 9 5 2)))
  0)

DouKaku?

比較しないソートの作成

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq