スキームでリストをソートする

Question

リストを昇順に返すソートアルゴリズムを書くにはどうすればいいですか？

例： '（1 3 5 2 9）を返し'（1 2 3 4 5 9）

Answer 1

SRFI 95ソートライブラリを提供します。多くのScheme実装ではソートライブラリも組み込まれていますが、それらのすべてがSRFI 95インターフェイスに準拠しているわけではありません。あなたは（宿題のために、と言う）独自の実装を記述する必要がある場合は

---

することは、あなたはマージソートやクイックソートのような標準的なソートアルゴリズムのいずれかを使用する必要があります。しかし、これらのアルゴリズムはどちらもベクトルベースのアルゴリズムなので、リストをベクトルにコピーして並べ替え、リストに戻してコピーする必要があります。ベクトル操作操作に便利なSRFI 43があります。特にベクトルの2つの要素を交換するのにvector-swap!が役に立ちます。

リンクされたリストを直接ソートするのに適したアルゴリズムがあります。私は彼らと一緒にいるわけではないので、私はそれ以上コメントしません。

Answer 2

ほとんどのSchemeの実装には、リストをソートするプロシージャが付属しています。あなたの実装がそれを提供しない場合、それをあなたの上で動かすことは困難ではありません。ここでは、クイックソートアルゴリズムの実装です：

> (define (qsort e) 
    (if (or (null? e) (<= (length e) 1)) e 
     (let loop ((left null) (right null) 
        (pivot (car e)) (rest (cdr e))) 
      (if (null? rest) 
       (append (append (qsort left) (list pivot)) (qsort right)) 
       (if (<= (car rest) pivot) 
        (loop (append left (list (car rest))) right pivot (cdr rest)) 
        (loop left (append right (list (car rest))) pivot (cdr rest))))))) 
> (qsort '(1 3 5 2 9)) 
=> (1 2 3 5 9)