-
- いいね！7
Hideyuki Tanaka
@tanakh
insertion ソートはケツからSwapしないといけないとか、そういうことになりかねないし、そういうのは実装の詳細であって、そういうことをいうから余計混乱するんですよ
2013-01-27 12:10:16
狂える中３女子ボレロ村上／陶芸C++er
@bolero_MURAKAMI
constexpr でクイックソートを実装すると計算量が Ο(N^2logN) になるので偽物です。Ο(N^2) 未満の計算量のソートはまだ発見していないので誰か考えてください。
2013-01-27 12:10:20
Masaki Hara
@qnighy
qsortの件は、「そのサンプルコードをそのまま使うのは推奨されない」と全てのサンプルコードに注釈をつけてまわれば解決しそう
2013-01-27 12:10:49
Hideyuki Tanaka
@tanakh
ガチガチにチューニングしたソートがライブラリにあるので、そっちつ帰ってんなら、そもそも誰が実装したものも使えないしどっちにしろあんま変わらんじゃん
2013-01-27 12:12:11
カル
@nullkal
結局クイックソートは手続き型言語での実装が沢山なされてきているせいで、どうしても関数型言語での実装は実用上難があるというのが現状なのでは
2013-01-27 12:12:42
ふみ (DJ Monad)
@fumieval
アルゴリズムとしては本質的にクイックソートと同じであっても、実用性のない実装なのに「Haskellではこんなにシンプルにクイックソートが書ける！」というのはミスリーディングではないかと思う
2013-01-27 12:13:05
きしだൠ(K1S)
@kis
@tanakh クイックソートの本質というのは計算量が平均してn log nになることや最悪時n^2になることですよねぇ。定数項は本質じゃないと思います。コンピュータの本質がメモリ書き換えというのも、少し違う気がするし。
2013-01-27 12:13:05
Hideyuki Tanaka
@tanakh
だからあれがなんで実用できないとか、間違ってるとかそういう話になるのかわからない。あれはあってるし、計算量も正しいと思うんだけど。
2013-01-27 12:13:27
きしだൠ(K1S)
@kis
@tanakh コンピュータの本質というのなら、メモリ書き換えだけでなく、メモリ確保・開放もあわせて本質で、関数型でのクイックソートの例は後者を利用しているということもできる気がします。
2013-01-27 12:14:54
shobotch
@dll7
クイックソートを使うことを…しいられているんだっ…！ 仕様には逆らえねぇ。たとえメモリの効率が悪いとしても…。上の命令と仕様書は…
2013-01-27 12:15:50
ありがとう
@rfc4627
マージソート「マージでえ？」 クイックソート「イく…イックう！！」 ボゴソート「母語は日本語ですね」 ヒープソート「ひいっ！プリンうめえ！ひいっ！」 バブルソート「ばぶー！」
2013-01-27 12:15:57
Hideyuki Tanaka
@tanakh
@kis 僕もそう思うのですねえ。なんか違うって人は、そういうところじゃないところにクイックソートの要件があるというのかなんだろうか
2013-01-27 12:16:01