[B! algorithm][sort] clavierのブックマーク

clavier id:clavier

algorithmとsortに関するclavierのブックマーク (6)

[KMP77] を読んでみた - d.y.d.
17:53 14/12/22 ソートの逆流れクイックソートってあるじゃないですか、クイックソート。配列、たとえば [4,2,1,7,0,6,5,3] があったときに、小さい方を左に、大きい方を右にまず適当に集める。この「小さい方」と「大きい方」への二分割を、いわゆる再帰的に、分かれたブロック両方で同じ事を繰り返していくと… なんと、小さい順に並んだ配列 [0,1,2,3,4,5,6,7] が出来上がるというアルゴリズムです。逆向き！このデータの流れを「逆向きに」見てみたい。つまり、ソートが終わった最終状態から話が始まります。しかも、さっきから説明なしで意味ありげにくっついていた、「入力配列で元々どの位置にあったか」を表す値に注目していきます。 0の上に[4]がくっついているのは、最初は値0は配列のインデックス[4]の位置にあった、ということを意味しています。（上のソート
clavier 2014/12/23
Algorithm

sort

あとで読む
リンク
手続き脳によるHaskell -- Sorting Algorithms
このページは手続き脳から脱却でいない筆者が、Haskell による各種ソートティングアルゴリズムを実装してみた結果を紹介するページです。ソートはアルゴリズムの基本ですから、これで Haskell を攻略しようというわけです。ところで、Haskell に関するWebページを巡回していると、高階関数やモナドなどを複雑に使ったアクロバチックでアブノーマルなコードに出会うことがしばしばあります。書いている超頭の良い人達は自らの変態さ加減が披露出来て快感なのかもしれませんが、頭の悪い私にはそんなコードは理解できません... orz。そこで私のページでは次のスローガンでプログラミングを行います普通にやれ、普通に！そんなわけで「モナドを理解したい」とか常人には不可能な無理難題を期待している人は他のページを当たってください。筆者自身が分かってないので解説できません。ごめんなさい。
clavier 2013/02/24
programming

Haskell

sort

algorithm
リンク
VOYAGE GROUP　エンジニアブログ : Linuxカーネルのlist, rbtree, sortを使ってみた！
2012年12月21日10:40 カテゴリ Linuxカーネルのlist, rbtree, sortを使ってみた！ ※　このエントリーは、VOYAGE GROUPエンジニア blog Advent Calendarの12/21分です。こんにちは、VGエンジニアのポール（@pank7）です。多分知ってる人はいらっしゃいますが、半年前にvgtechブログを書いた際にはまだ日本語がまだダメなので、英語で書きました。今回はできるだけ頑張って日本語で書きます。ご指導よろしくお願いいたします。何を書きますか私が書ける言語はそんな多くないですけど、普段自分が好きな言語だといえば、C言語はその中の１つです。Cのメリットとしてはやはり多いと思います。シンプルや移植性が良いや効率的やUNIX系OSと仲良いなどというのがあります。でも今の仕事で使っている言語のPHP、Perl、Python、Shellとか
clavier 2012/12/21
linux

sort

algorithm

あとで読む
リンク
algorithm - bucket sort - 比較しなければソートは相当速い : 404 Blog Not Found
2012年01月11日07:00 カテゴリアルゴリズム百選Math algorithm - bucket sort - 比較しなければソートは相当速い珠玉のプログラミング Jon Bentley / 小林健一郎訳絶賛風邪こじらせ中につきコードと戯れることに。新ソートアルゴリズム「配列挿入ソート」だ! - hp12c その名も「配列挿入ソート」! すでに突っ込み入ってるけど、それ、もしかしたら人類最古のアルゴリズムだから。最古にして最速? おそらくプログラムを組んだことがない人でも「誰にも教えられずに」知った「天然の」アルゴリズムの筆頭に来るのがこのバケットソートではないでしょうか。ソートしたいものに適当に番号を振っておく番号がついたバケツを用意するソートしたいものの番号がついたバケツにそれを放り込む必要があればバケツの中身を同じやり方でソートする番号順にバケツの中身をぶち
clavier 2012/01/11
programming

sort

JavaScript

Algorithm
リンク
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
clavier 2011/11/17
sort

Algorithm
リンク
quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream
<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。画期的（？）なソートアルゴリズム「Sleep Sort」：濃縮還元オレンジニュース｜gihyo.jp … 技術評論社このあたりで拾ってきたネタですね。 merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）： https://github.co
clavier 2011/10/19
programming

Java

Algorithm

sort
リンク
1