計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell - Qiita

皆さん、ソートは好きですか？ 僕はHaskellerのクセにボゴソートが好きです。 ソートされていない要素を粛清することでO(N)でソートできるスターリンソートとかいうのを見て爆笑してる — やんぎん (@4116You) July 28, 2019 なにやらTLでスターリンソートなるものが流行っていました。 まずO(n)とは何かという事なんですが、これはビッグ・オー記法と言ってアルゴリズムの性能の指標を表すものです。 O(n)の他にO(1)とかO(log(n))とかO(nlog(n))とかO(n^2)とかがありますが、詳しくは割愛します。この辺を参考にするとよく分かると思います。ともかく、O(n)はむっちゃ速い、というかソートアルゴリズムではまず有り得ないです。 にも関わらず、スターリンソートはその壁を打ち破って、O(n)で並べ替えを実現しちゃうんですよね。 というわけでHaskellで

[ruicc]

これ全部粛正すればO(1)では？

[qtamaki]

革命的だ

[hase0510]

安定ソートじゃん実用的！

[yumura_s]

Data.Listのsortもボトムアップマージソートする前に整列済みのリストのリストにするからあながちって感じもする

[nekoruri]

ソビエト連邦の生産性を支える技術

[lotz84]

なんど見ても草

[miragestlike]

なるほどシベリア送りだ

[kaputte]

ソートとは（哲学

[kazuau]

最初の要素だけ返せばいいんじゃね？民主集中制だ(違う)

[manji0]

なるほど粛清

[kkobayashi]

逆順ソートされたデータを入れると無くなっちゃうやんけ！

[FutureIsWhatWeAre]

革命的ソートアルゴリズム笑った

[migrant777]

アジア圏ではNKソートと呼ばれそう。

[igrep]

x < yな場合も要素が消えるgroup関数だね。