CLでQuickSort

サルでもできる題材をなぜ採用したか

・私はサル未満だから。

・markdown parser,xml parserを書こうと思ったが、ちょうど勉強してたパーサコンビネータというものをみて、直書きがアホらしくなったので頓挫。

・B-Treeの実装も考えた。というよりこっちはずっと前から考えてた。けど全然よいプラン思いつかんし、他人の実装みてもう〜んってなって、こっちも頓挫。

おまえほんとやらない言い訳作るの得意だな？

リンクとか

wikipedia

実装

(defun quicksort (lst &optional (f #'<))
 (if (null lst)
	  lst
	  (let* ((pivot (car lst))
			 (before (quicksort (remove-if #'(lambda (x) (funcall f pivot x)) (cdr lst)) f))
			 (after (quicksort (remove-if-not #'(lambda (x) (funcall f pivot x)) (cdr lst)) f)))
		(append (append before `(,pivot)) after))))

ああああああ＾〜〜〜〜〜〜〜〜〜〜気持ちいいいいいいい＾〜〜〜〜〜〜〜〜

雑魚狩り気持ちいいいいいいいいいいいいいいいいい＾〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜〜

...

実装メモ

今回は再帰で組んだ。

故に?最初に落とし所判定、nullチェックをおいた。

これで例外はあるが、まあSOFすることはない。

次にpivot、これ普通なら配列中の中央値とかを採用するんだけども、

めんどい。なので最初の値を使う。

ただこうすると最悪の計算量がひどいことになる。

これなら何度か探索してでも中央値を求めたほうがいい。

しかし、今回はそれを知っているのでそれでいい。

感想

やりました・・・・・。やったんですよ！必死に！その結果がこれなんですよ！Emacs起動して、小指使い倒して、今はこうして砂漠を歩いてる。これ以上、何をどうしろって言うんです！何を書けって言うんですか！

まあネタはこれくらいにして、実を言うと数年前クイックソートを実装しようとしたとき、なんと数時間かかったんですよ。笑える。

それが今や10分もかからずに実装できるようになった。

とはいえ、Wikipediaみられたバレるんだけど、実際はそこのPython実装のパクリ。実力ではない。そういう意見もある。わかる。

しかし、こうも見れる。以前はパクることすら知らずに数時間溶していた。

私の目指すハッカーとは職人ではない。日本人の思い描くなんちゃって職人ではない。

パクリだろうが、なんだろうが(もちろん遵法等は守った上で)楽に、早く、楽しく、そしてシンプルに問題を解決すればよいのだ。

ほかは知らん。それが私の変数に定義されてる*hacker*だ。

以上、言い訳終わり。

次どうするかな。競プロの問題でもやるか、パーサコンビネータ書きたい気持ちも強いが、私の能力的に一日で書ける感じはしない。

とーりあえずしばらくはパク参考にできる素材にインデックスを貼ることに集中する。