scheme - スキーム内の数字の無秩序リストをソートする方法

Question

スキームでリストを値でソートする適切な方法は何ですか? たとえば、順序付けされていない値があります。

x1, x5, x32 .... xn

また

3, 4, 1, 3, 4, .. 9

まず、番号を増やして、次の順序で表示します。

x1, xn, x2, xn-1

また

1, 6, 2, 5, 3, 4

どんな助けも貴重です。

Answer 1

これは前に投稿した質問と同じですが、少しひねりを加えています。私の答えのコメントで言ったように、並べ替える前にリストを並べ替えるだけです。ラケットのソリューションは次のとおりです。

(define (interleave l1 l2)
  (cond ((empty? l1) l2)
        ((empty? l2) l1)
        (else (cons (first l1)
                    (interleave l2 (rest l1))))))

(define (zippy lst)
  (let-values (((head tail) (split-at
                             (sort lst <) ; this is the new part
                             (quotient (length lst) 2))))
    (interleave head (reverse tail))))

期待どおりに動作します：

(zippy '(4 2 6 3 5 1))
=> '(1 6 2 5 3 4)

Answer 2

これは、リストの半分がトラバースされたときに「低速/高速」手法を使用して再帰を停止する、単純な末尾再帰アプローチです。

(define (interleave l)
  (let ((l (list-sort < l)))
    (let merging ((slow l) (fast l) (revl (reverse l)) (rslt '()))
      (cond ((null? fast)
             (reverse rslt))

            ((null? (cdr fast)) 
             (reverse (cons (car slow) rslt)))

            (else
             (merging (cdr slow) (cddr fast) (cdr revl)
                      (cons (car revl) (cons (car slow) rslt))))))))

Answer 3

この R6RS ソリューションは、Chris Jester-Young が提案していることを実行しますが、実際にはそれを悪い方法で行う方法です。ところで、並べ替えなしの同じ質問に対するクリスとオスカーのソリューションは、このジッピーな手順よりも優れています。

    #!r6rs
    (import (rnrs base)
            (rnrs sorting)) ; list-sort

    (define (zippy lis)
      (let loop ((count-down (- (length lis) 1))
                 (count-up 0))
        (cond ((> count-up count-down) '())
              ((= count-up count-down) (cons (list-ref lis count-down) '()))
              (else (cons (list-ref lis count-down)
                          (cons (list-ref lis count-up)
                                (loop (- count-down 1)
                                      (+ count-up 1))))))))
    (define (sort-rearrange lis)
      (zippy (list-sort < lis)))