masquerade0324のブログ

とある大学院生のメモ書き

関数型プログラミングにおけるクイックソートの議論が楽しい

先日Twitter上で,関数型プログラミングにおけるクイックソートの議論がありました.

関数型プログラミングにおけるクイックソートの議論というのはよく起こるみたいで,私もTwitterで何回か見たことがありますが,おもしろい話題であることに間違いないです.議論してるのはプログラマとしてはかなり凄腕の人たちばかりで,なるほどなーと思えることが多いです.

クイックソートの本質は何か,という議論にもなりそうです.Hoareが提唱したと私は記憶していますが,そもそもクイックソートっていうネーミングにはみんな困ってるみたいです.in-placeじゃなきゃクイックソートじゃないのかとか,計算量的にもどうだとか.

関数型プログラミングにおけるクイックソートの例は結構好きなんですが.確かにピボット選択がどうだとか,リストの連結がどうだとか言う話はあります.しかし,私自身はCでクイックソートを書いたこともあるのでそこら辺はわかってる上でクイックソートはきれいだなと思います.計算量もあれでもO(nlogn)らしいので(ちゃんと見てないので嘘言ってたらごめんなさい).

こういう議論に目を通して勉強するのは楽しいなと思います.