【またかよ】「Haskellでクイックソート」問題【何度目だ】

ありがとう @rfc4627

バブルソート遅いけど簡単だからすき

haiiro_shimeji @haiiro_shimeji

Haskellのあのクイックソートなんであかんのか理解してない

Hideyuki Tanaka @tanakh

fibもあれは正しいし、qsortも正しいけど、sieveが間違ったるから、なんかごっちゃにされてるんじゃないか？

Hideyuki Tanaka @tanakh

クイックソートのアルゴリズム：pivotの選択、pivotでの分割、再帰的にソート じゃないんか。なんで分割をinmemoryでやってないからおかしいということになるんだ。ちょっとわからない。

くいなちゃん @b2

qsortは、名前からクイックソートかのように誤解されがちですが、中身はボゴソートです。

swd @s_w_d_

そもそも、入門書でクイックソートを最初にやるのが間違いでは・・・

Masaki Hara @qnighy

「killer sequenceが存在してしまうというクイックソート自体の問題」「ソート済み配列がkiller sequenceになってしまうようなクイックソート実装の問題」「定数項が大きいクイックソートの問題」

Hideyuki Tanaka @tanakh

そうですよ、これはそういう問題だから。

NaOHaq(苛性ソーダ) @NaOHaq

定期的に盛り上がる "Haskellでクイックソート" 問題

KOIZUKA Akihiko @koizuka

pivot選択に乱数を使う修正クイックソートって何か名前ついてるんだっけ

普通のC++使い、銀天すばる @SubaruG

そういえば Haskell でのクイックソートってリストの連結操作にかかるオーダーを考慮しても most case で Ο(N log N) って認識であってる？

普通のC++使い、銀天すばる @SubaruG

(++) って結構遅かった気がするんだけど

Masaki Hara @qnighy

だからサンプルコードに注釈をつけてまわるくらいはしてもいいんじゃないんですかというのが僕のさっきのツイートでした

カル @nullkal

入門書に書かれてるソートアルゴリズムなんて手続き型のヤツでも実用上ライブラリの実装に劣ることは間違いないけど 仮に関数型言語でそれと同等の効率のモノを書こうとするとどうしても手続き型言語で書いたような実装になっちゃうってことなのでは

Hideyuki Tanaka @tanakh

@SubaruG avg case O(nlogn)であってます。

Masaki Hara @qnighy

余計なお世話感ある発言でしたね…

Kazuho Oku @kazuho

言語実装が使ってるハッシュ関数の衝突が脆弱性になるんだからクイックソート使ってたりするとやっぱり脆弱性になり得そう

You Ichimaru @m_at_ro

ライブラリ関数に素朴なクイックソート使われても困る。

普通のC++使い、銀天すばる @SubaruG

非正格だからいくらでも最適化できるってのは良いよね

Hideyuki Tanaka @tanakh

注釈付ける必要はないんではないのか。それはクイックソートの勉強じゃないか。そんなのみんな知ってる。って思ってても、HaskellからCS入る人もいるんですかね。

けんこふたんっ @kenkovtan

ソートTLになってるっ

子ゆりあ @koyuria

朝起きたら、TL がクイックソートで埋まっている、、、

Masaki Hara @qnighy

クイックソートを発明したhoareが全部悪い

Tsukasa #01 @a4lg

@b2 ボゴソートかは別として(汗、規格ではソートアルゴリズム自体を厳密に指定してるわけではないですね。

けんこふ @kenkov

ソートTLになってるっ