6.23 ソートとマージ

ソートとマージのインタフェースはSRFI-95に準拠し、さらに次の点で拡張されています。

• リスト、ベクタ、文字列だけでなく、あらゆるシーケンス (<sequence>のインスタンス)をソートできます。
• 順序を指定するのに、比較関数も比較器(基本的な比較器参照)も 使うことができます。
• 比較関数を省略できます。省略された場合、 要素同士はdefault-comparatorを使って比較されます。

Function: sort seq :optional cmp keyfn ¶

Function: sort! seq :optional cmp keyfn ¶

[SRFI-95+] シーケンスseqの要素を昇順にソートし、 ソートされたシーケンスを返します。 sort!は、オリジナルのシーケンスを破壊的に再利用します。

seqには<sequence>クラスのインスタンスを渡すことができます。 同じ型のシーケンスが返されます。sortの場合、 seqと同じ型のシーケンスを新たに作る必要があるので、 seqの型はビルダーインタフェースを実装していなければなりません (ビルダーインタフェースについては基礎的なイテレータ構築メソッドを参照)。 sort!の場合、seqは変更可能でなければなりません。

ソート順はcmpで指定されます。これは手続きか比較器でなければなりません。 手続きの場合は、seqのふたつの要素を 引数に取り、最初の要素が厳密に2番目の要素より先行する場合に #tを返します。 比較器の場合は、比較手続きを持つものでなければなりません。 省略された場合はdefault-comparatorが使われます。

省略可能な手続き引数keyfnが与えられた場合、 要素はまずkeyfnに渡され、その結果が比較に使われます。 keyfnは各要素に対してたかだか1回しか呼ばれないことが保証されます。

(sort '(("Chopin" "Frederic")
        ("Liszt" "Franz")
        ("Alkan" "Charles-Valentin"))
      string<?
      car)
  ⇒ (("Alkan" "Charles-Valentin")
      ("Chopin" "Frederic")
      ("Liszt" "Franz"))

現在の実装では、cmpが省略された場合は クィックソートとヒープソートを使い、 cmpが与えられた場合はマージソートを使っています。 すなわち、少なくともcmpを指定すれば、ソートは安定であることが 保証されます (ただし、安定であるためには cmpは等しい引数が与えられた時に必ず#fを返さなければなりません)。 SRFI-95は安定性を要求しますが、同時にcmpが与えられることも要求するので、 これらの手続きはSRFI-95の上位互換です。

なお、オブジェクトをひとつづつ集合に追加しつつ、常にソートされた 状態に保ちたい場合は、treemapの使用を考えても良いでしょう (ツリーマップ参照)。 また、最大または最小から数要素だけを必要とする場合は、 全ての要素をソートするかわりにヒープが使えます (data.heap - ヒープ参照)。

Function: sorted? seq :optional cmp keyfn ¶

[SRFI-95+] seqの要素がソートされている時に限り#tを返します。 seqにはどんなシーケンスを渡すこともできます。 省略可能引数cmpとkeyfnの意味はsortと同じです。

SRFI-95ではcmpは必須になっています。

Function: merge a b :optional cmp keyfn ¶

Function: merge! a b :optional cmp keyfn ¶

[SRFI-95+] 引数aとbはリストで、比較関数または比較器cmpによって 既にソートされているものとします。これらの手続きは二つのソート済みリストを マージして、ソートされた一つのリストにします。merge!は破壊的バージョンで、 aとbのセルを再利用します。戻り値はaかbに対してeq?と なります。

SRFI-95ではcmpは必須になっています。

以下の手続きは後方互換性のために残されていますが、その機能は 拡張されたsortおよびsort!によってカバーされています。

Function: stable-sort seq :optional cmp keyfn ¶

Function: stable-sort! seq :optional cmp keyfn ¶

安定ソートアルゴリズムを使って、シーケンス seqをソートします。 cmpfnとkeyfn引数はsortおよびsort!と同じです。

実のところ、現在ではsortとsort!はcmpが与えられれば 安定ソートアルゴリズムを使うので、これらの手続きは どうしてもcmpを省略しつつ安定ソートしたい、という場合でなければ 使う必要はありません。

Function: sort-by seq keyfn :optional cmp ¶

Function: sort-by! seq keyfn :optional cmp ¶

Function: stable-sort-by seq keyfn :optional cmp ¶

Function: stable-sort-by! seq keyfn :optional cmp ¶

比較のためのキーを取り出す関数を取る、ソート手続きの別バージョンです。 sort等の手続きが省略可能なkeyfnを取るようになったので、 現在ではこれらの関数は冗長です。