#:g1: zsortの紹介

Posted 2014-08-22 14:00:00 GMT

(LISP Library 365参加エントリ)

 LISP Library 365 の234日目です。

zsortとはなにか

 zsortは、Jorge Tavares氏作のCommon Lispのシークエンス用のソートライブラリです。

パッケージ情報

パッケージ名zsort
Quicklisp
Quickdocszsort | Quickdocs
CL Test Grid: ビルド状況zsort | CL Test Grid

インストール方法

(ql:quickload :zsort)

試してみる

 どんな関数があるかは、Quickdocsで確認できます。

 Common Lispには標準でsortとstable-sortが用意されていますが、どんなソートアルゴリズムかを選択することはできないので、色々なアルゴリズムのソートを用意してみました、というライブラリです。
現在のところ

が用意されています。
動作は下記のような感じです。

(let ((u (*:iota 100 100 -1)))
  (zsort:counting-sort u))
;=>  (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
;     30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
;     56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
;     82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

(let ((u (*:iota 100 100 -1))) (zsort:heapsort u #'<)) ;=> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ; 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ; 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ; 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

(let ((u (*:iota 100 100 -1))) (zsort:insertion-sort u #'<)) ;=> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ; 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ; 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ; 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

(let ((u (coerce (*:iota 100 100 -1) 'vector))) (zsort:merge-sort u #'<)) ;=> #(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ; 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ; 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ; 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

(let ((u (*:iota 100 100 -1))) (zsort:quicksort u #'<)) ;=> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ; 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ; 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ; 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

(let ((u (*:iota 100 100 -1))) (zsort:randomized-quicksort u #'<)) ;=> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ; 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 ; 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 ; 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

ちなみに、どういう訳かmerge-sortがvectorにしか対応してないみたいです。

まとめ

 今回は、zsortを紹介してみました。
色々なアルゴリズムが選択できるというのは、なかなか良いですね。

comments powered by Disqus