Sort
2021年に発見されたソート
「ばいとにっく」と読む
常に$ O(n\log n)
一般的にはソートは、「要素数」「要素の並び方」に左右される
このソートは計算量が「要素数」のみで決まる
データ数が2の冪乗個でないと使えない
0paddingなどで対応
Sortの分類
haskell
どういうアイディアでsortしているのか
sort名の名前の意味
なにが「quick」なのか、どのへんが「bubble」なのかなど、「どういうアイディアか」とsort名が結びつくようにしたい
計算量
最低、最高、平均
またそのような計算量になる直感的な理解の言語化
sort名と計算量を結びつけて記憶するのはたぶん無理なので、「どういうアイディアか」から計算量を思い出せるようにすると良いと思う
sort時の動きのvisual
思い出す時にパット見で思い出せると良い
可視化するやつ
wikipedia
音声化と可視化
アルゴリズム
hsのコード(関数型)
tsのコード(その他)
配列の破壊的変更とかして手続的に書かなければあまり書く意味ないなmrsekut.icon
再帰を使わずに書かないとわざわざ書く意味があまりない
hsの下位互換にしかならない
長所と短所
速いだけなら「常にそれ使えば良いじゃん」になる
何かしらメリデメがあるはず
「実装が難しい」とかも理由に上がったりするのか？
改良版のsortとかがあるなら
code:temple
概要
命名
計算量
アルゴリズム
可視化
コード例
派生とか
長所と短所
参考