挿入ソートと選択ソートは双対 - Qiita
先日 Gotanda.hs #1 @HERP というイベントがあって、そこでRecursion Schemesで考える並べ替えアルゴリズムというタイトルでA Duality of Sortsという論文の話をLTしたんですが、この記事ではそこで話せなかった論文の後半で解説されている挿入ソートと選択ソートの双対性について書いていきたいと思っています。 ソートアルゴリズムの復習 まずは主役の二人である挿入ソートと選択ソートについて見ていきましょう。 挿入ソートは与えられたリストの先頭から要素を取り出し、これまでに構築したソート済みのリストに挿入していくという処理を繰り返すことでソートを実現するアルゴリズムです。 出典: Insertion sort - Wikipedia これをHaskellで実装すると以下のようになります。 insertSort :: [Int] -> [Int] inser
O(n)時間でソートが終了するバケットソートをHaskellで実装する (1) - Qiita
はじめに ネタで「洗脳ソート」を公開したら、思った以上に拡散してしまったので、マジメな方も書かないとまずい、と思い急遽バケットソートのHaskellでの実装を説明する。 いくつかの拡張機能を使うが、それらの説明は後回しにする。雰囲気だけでもお伝えできればと。 バケットソートとは なぜO(n)でソートできるのか ソートは最小でもO(n log(n))時間かかることが証明されている。なのになぜ、O(n)時間でソートができるのか。「粛正ソート」や「洗脳ソート」では、「ソートの結果」における条件をそれぞれつぎのようにゆるくしたことでO(n)時間でのソートが可能になった。 昇順(または降順)にデータが並んでいる ソート前に含まれていた以外のデータが含まれていない (粛正ソートではここまで) ソート前後で値の数が変化しない(洗脳ソートではここまで) これをおそらく「ソート」とは呼べない。だからこそ「ネ
クイックソート計測大会2 criterionの注意事項 他 - Qiita
前回記事の続きです。 前回は「Haskellクイックソート計測大会2016」という事でcriterionによる速度計測の実例をレポートしましたが、計測結果を本記事で少し修正しようと思います。 Criterionの補足：初期化処理について まずはcriterionの使い方についての補足です。 というか、前回記事で使用したソースに間違いが一つあったため、その訂正になります。 前回記事で使用したソースでは、MutableなVectorに対する計測を以下のように書いていました。 しかし、criterionのエンジンは、計測コードを複数回実行し平均を取る仕組みになっています。そのため、二回目以降はソート済みの配列に対して時間計測を行ってしまっていました。 今回の配列ソートではピボットを中央から取っているため、ソート済みの配列に対しては最大効率になります。つまり前回記事の計測スコアでは、Vector関
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
