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

くいなちゃん @b2

@a4lg VCをはじめとする多くの実装では、マージソートですかね

Sierra@ioアカウント作った @s_voltec

ソートTLになってない...

Hideyuki Tanaka @tanakh

でもそれこそCの長いよく乗ってるコードだって、worst cast なんもしてないこと多いし、注釈する必要がないんじゃないか

Hideyuki Tanaka @tanakh

マージソートだったらそんなに論争怒らないじゃないですかぁ。はあ。

ふみ (DJ Monad) @fumieval

個人的にクイックソートはあんまりHaskellで短く書くのに適していないと思うのでマージソートを代わりに使おう(提案)

くいなちゃん @b2

@a4lg クイックソートは不安定ソートだったと思いますが、問題ないんですかね

Noriyuki OHKAWA @notogawa

クイックソートって命名が悪いでFAになったんじゃなかったっけ？

suibaka @suibaka

今おきた。ソートの話で盛り上がってるの？

Hideyuki Tanaka @tanakh

HaskellのあのQuickソートのベンチとってくださいよ。randomとworstで

Amboinensis @Amboinensis

ソートの勉強なら1〜1000までカードに印刷して各アルゴリズムを人力でやらせると良い

Tsukasa #01 @a4lg

@b2 規格上、同じ値と判定された 2 つの値がどう並ぶかは指定されていません。なので不安定ソートでも何の問題もないですし、むしろ qsort が安定ソートであることを期待すると処理系次第でマズい結果になるかと。

けんこふたんっ @kenkovtan

Clojureで練習がてらいろいろソート書いてみようかなっ

カル @nullkal

なんかクイックソートの話題、参加している人の前提が揃ってない感じ

NaOHaq(苛性ソーダ) @NaOHaq

ソート済みのデータを入力すると時間計算量のオーダがO(N^2)になるので最初に適当に混ぜ混ぜしときましょう、という辺りにクイックソートの闇が見える

Üe🦀 @ranha

クイックソート，partitionの際に（部分）セグメントの左端と右端からそれぞれlowerポインタとupperポインタを走らせて交差するまで交換しますと書いてるし，dividing lineでpartitionした後は計算機の特性によって小サイズセグメントをアレせよ（続く

くいなちゃん @b2

クイックソートって、名前が自意識過剰すぎ。　もっと速いソートありますのに。

狂える中３女子ボレロ村上／陶芸C++er @bolero_MURAKAMI

クイックソートじゃない。ボゴソートの話題だ。

けんこふ @kenkov

(println "いろいろソート")

カル @nullkal

C++にstd::bogosortの実装はよ

Sierra@ioアカウント作った @s_voltec

でもスローソートとかあっても使いたくない

brainfilesystem @brainfs

クイックソートの説明には必ず有名な処理系での処理方法も補足として添付してみては

Maxしぐれん @Sigureya

クイックソートよりも速そうな名前とは。

みょん @myuon_myon

常にO(1)の爆速ソートはよ

れぐすぺP @project_mathmas

クイックソートであふれかえるTLをソートしたい

カル @nullkal

「既にソートされていること」を入力値の条件にすればO(1)の爆速ソートは実装できるのでは