R6RS:翻訳:Standard Libraries:4 Sorting

R6RS:翻訳:Standard Libraries:4 Sorting

4 章 並べ替え

本章ではリストとベクタの並べ替えに関する (rnrs sorting (6)) ライブラリについて述べる。

[procedure] (list-sort proc list)

[procedure] (vector-sort proc vector)

proc はリストとベクタの任意の要素ふたつを受け取る。その他の副作用があってはならない。 proc は最初の引き数が二番目のものよりも厳密に小さな場合に真値を返し、さもなくは #f を返す。

list-sort 手続きと vector-sort 手続きはリストないしベクタについて proc について昇順に安定な並べ替えを行ない、リストやベクタには何ら変更を行なわない。 list-sort はリストを返し、 vector-sort はベクタを返す。引き数が既に並べ替え済みである場合、戻り値は引き数と eq? であることもある。また、 list-sort の戻り値はもとのリストと末尾部分の構造を共有していることもある。リストないしベクタの長さが n としたとき、並べ替えアルゴリズムは proc を O(n log n) 回を呼び出し、 proc に渡される引き数はすべて、並べ替えられるリストないしベクタの要素である。ただし、引き数の組み合わせや proc の呼び出し順序については規定されていない。 list-sort や vector-sort から複数回戻った場合でも、以前の戻り値は変更されない。

(list-sort < ’(3 5 2 1))         ⇒ (1 2 3 5)
(vector-sort < ’#(3 5 2 1))         ⇒ #(1 2 3 5)

実装系への要求: 実装系は proc について、ここで述べた適用時の存続期間への制約について検査を行わなければならない。実装系は proc を適用する前に、それが適切な引き数であるか検査してもかまわない。

[procedure] (vector-sort! proc vector)

proc はベクタの任意の要素をふたつを取り、いかなる副作用も持ってはならない。 proc は最初の引き数が二番目の引き数より厳密に小さな場合に真値を返し、それ以外は #f を返す。 vector-sort! 手続きは proc にしたがって破壊的に vector の要素を昇順に並べ替える。ベクタの長さを n としたとき、アルゴリズムは proc を O(n^2) 回呼び出す。 proc に渡される引き数はすべて並べ替えのされるベクタの要素である。ただしこのとき、引き数の組み合わせと proc の呼び出し順序は規定されていない。並べ替えアルゴリズムは安定でなくてもよい。この手続きの戻り値は規定されていない。

(define v (vector 3 5 2 1))
(vector-sort! < v)         ⇒ unspecified
v         ⇒ #(1 2 3 5)

実装系への要求: 実装系は proc について、ここで述べた適用時の存続期間への制約について検査を行わなければならない。実装系は proc を適用する前に、それが適切な引き数であるか検査してもかまわない。

More ...