% Function SORT, STABLE-SORT
Function SORT, STABLE-SORT
sort sequence predicate &key key => sorted-sequence
stable-sort sequence predicate &key key => sorted-sequence
sequence - 正常なシーケンス
predicate - 2つの引数をとりgeneralized-booleanを返却する関数の指定子
key - 1つの引数を取る関数の指定子、またはnil
sorted-sequence - シーケンス
sortとstable-sortは、
predicate関数で決められた順番に従って、
sequenceを破壊的にソートします。
もしsequenceがvectorのとき、
返却値は一次元のsimple-arrayであり、
sequenceと同じ実際の配列の要素の型を持ちます。
もしsequenceがリストなら、返却値はリストです。
sortは、keyによる要素の展開とpredicateの実行によって、
2つの要素間の関係を決定します。
predicate関数の最初の引数は、
key関数によって展開された（もしkeyが指定されたのなら）、
ひとつの要素の部分であり、
二番目の引数は、
key関数によって展開された（もしkeyが指定されたのなら）、
別の要素の部分です。
predicateは、第一引数が第二引数より（何らかの適切な意味で）、
厳密に小さい場合にのみtrueを返すべきです。
もし最初の引数が二番目の引数が（何らかの適切な意味で）、
以上であるときは、predicateはfalseを返却するべきです。
key関数の引数は、sequenceの要素です。
key関数の返却値は、predicateの引数になります。
もしkeyが与えられないか、あるいはnilが指定されたとき、
sequenceの要素そのものが使用されます。
keyが呼び出される回数を保証する方法はありません。
もしkeyとpredicateが常に返却するのであれば、 ソート操作は常に終了し、 sequenceとして同じ要素が含んだシーケンスが生成されます （つまり、返却値はseqeunceの並べ替えです）。 これはpredicateが実際には全順序の表現が一貫されていなくても保証されます （そのような場合は、要素は予測不可能な順番でスクランブルされますが、 要素が失われることはありません）。 もしkeyが一貫して意味のあるキーを返却し、 predicateがそれらのキーにおいて 何らかの全順序の基準を反映したのであれば、 sorted-sequenceの要素は、おそらく適切にソートされます。
sortによるソートの操作は、安定性が保証されません。
predicateによって等しいとされた要素は、
元の順序のままであるかもしれないし、そうでないかもしれません。
predicateは、
(funcall predicate x y)と(funcall predicate y x)が
両方ともfalseであるときに、
2つの要素xとyが等しいとみなすと仮定しています。
stable-sortは、安定性を保証します。
どの場合においても、ソート操作は破壊的です。
vectorが引数のときは、要素の場所に並べ替えることで行います。
リストの場合は、nreverseと同じ方法で
破壊的に並び替えられます。
(setq tester (copy-seq "lkjashd")) => "lkjashd"
(sort tester #'char-lessp) => "adhjkls"
(setq tester (list '(1 2 3) '(4 5 6) '(7 8 9))) => ((1 2 3) (4 5 6) (7 8 9))
(sort tester #'> :key #'car) => ((7 8 9) (4 5 6) (1 2 3))
(setq tester (list 1 2 3 4 5 6 7 8 9 0)) => (1 2 3 4 5 6 7 8 9 0)
(stable-sort tester #'(lambda (x y) (and (oddp x) (evenp y))))
=> (1 3 5 7 9 2 4 6 8 0)
(sort (setq committee-data
(vector (list (list "JonL" "White") "Iteration")
(list (list "Dick" "Waters") "Iteration")
(list (list "Dick" "Gabriel") "Objects")
(list (list "Kent" "Pitman") "Conditions")
(list (list "Gregor" "Kiczales") "Objects")
(list (list "David" "Moon") "Objects")
(list (list "Kathy" "Chapman") "Editorial")
(list (list "Larry" "Masinter") "Cleanup")
(list (list "Sandra" "Loosemore") "Compiler")))
#'string-lessp :key #'cadar)
=> #((("Kathy" "Chapman") "Editorial")
(("Dick" "Gabriel") "Objects")
(("Gregor" "Kiczales") "Objects")
(("Sandra" "Loosemore") "Compiler")
(("Larry" "Masinter") "Cleanup")
(("David" "Moon") "Objects")
(("Kent" "Pitman") "Conditions")
(("Dick" "Waters") "Iteration")
(("JonL" "White") "Iteration"))
;; "committees"内のアルファベット順は保存されます。
(setq committee-data
(stable-sort committee-data #'string-lessp :key #'cadr))
=> #((("Larry" "Masinter") "Cleanup")
(("Sandra" "Loosemore") "Compiler")
(("Kent" "Pitman") "Conditions")
(("Kathy" "Chapman") "Editorial")
(("Dick" "Waters") "Iteration")
(("JonL" "White") "Iteration")
(("Dick" "Gabriel") "Objects")
(("Gregor" "Kiczales") "Objects")
(("David" "Moon") "Objects"))
なし。
なし。
sequenceが正常なシーケンスでないとき、
型type-errorのエラーを通知する準備をしなければなりません。
merge,
3.2.1. コンパイラーの用語,
3.6. 横断の規則と副作用,
3.7. 破壊的操作
もしsequenceがvectorなら、
返却値はsimpleかもしれませんし、そうでないかもしれません。
また、返却値はsequenceと同一かもしれませんし、
そうでないかもしれません。