中央値の中央値 - Wikipedia
中央値の中央値（ちゅうおうちのちゅうおうち、英: median of medians）とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。 このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。 このアルゴリズムは、マヌエル・ブラムら[1]によって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。 概要[編集] クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が個の場合にの計算時間を必要とする。そ
QuickSort Killer
We use your LinkedIn profile and activity data to personalize ads and to show you more relevant ads. You can change your ad preferences anytime.
Smoothsort Demystified
Last Major Update: January 7, 2011 A few years ago I heard about an interesting sorting algorithm (invented by the legendary Edsger Dijkstra) called smoothsort with great memory and runtime guarantees. Although it is a comparison sort and thus on average cannot run faster than Ω(n lg n), smoothsort is an adaptive sort, meaning that if the input is somewhat sorted, smoothsort will run in time close
flint blog: 「選択アルゴリズム」と「中央値の中央値」
ある小説の登場人物、あるいは、あるアーティストの曲といった集合について考えるとき、「それらの中で最も好きなものはどれですか?」という問いに答えることは (甲乙付け難くて悩むケースもあるかも知れませんが) 比較的簡単です。 しかし、「2番目に好きなものは?」「3番目に好きなものは?」...といった具合に質問を続けていくと、どんどん回答が困難になっていくはず。 最も嫌い (好きでない) ものについては、好きでないものと同じように簡単に答えられるので、最も特定が困難なのは、好きな (あるいは嫌いな) 順に並べたとき、そのシーケンスの中央に位置する要素だと言えるでしょう。 私はこれまで、プログラミングにおいてもこれと同様の問題が存在する、即ち、ある配列 (要素数n )について特定の指標に沿っての並べ替え (ソート) を行ったときに中央あるいはその付近に配置される要素を特定するには、ソートそのものと
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
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
![quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い] - Islands in the byte stream](https://cdn-ak-scissors.b.st-hatena.com/image/square/f9103c273a45047a455a47c2322a4ec545cd77ee/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F17680117127143682567%2F17680117127143702106%2F1558185862)
¥Ð¥¤¥È¥Ë¥Ã¥¯¥½¡¼¥È - ¹â®²½¥×¥í¥°¥é¥ß¥ó¥°
¹â®²½¥×¥í¥°¥é¥ß¥ó¥° ¥È¥Ã¥×¥Ú¡¼¥¸¥Ú¡¼¥¸°ìÍ÷¥á¥ó¥Ð¡¼·Ç¼¨ÈÄÊÔ½¸ ¥Ð¥¤¥È¥Ë¥Ã¥¯¥½¡¼¥È ºÇ½ª¹¹¿·¡§ highcalc 2010ǯ07·î25Æü(Æü) 14:43:05ÍúÎò Tweet °Ê²¼¤Î¼ê½ç¤ÇÍ×ÁǸò´¹¤ò¹Ô¤¦¤³¤È¤Ç¡¢¥½¡¼¥È¤¬´°Î»¤¹¤ë¡£ ¡Ö¾º½ç¡Ü¹ß½ç¤Î¥Ð¥¤¥È¥Ë¥Ã¥¯Îó¡×¤Ë¤¹¤ë¡£ 2^n�¥�¥�¥2^0´Ö¤ò¾º½ç¡Ê¹ß½ç¡Ë¤ÇÈæ³Ó¤¹¤ë¡£ ¥á¥ê¥Ã¥È ¤½¤ì¤¾¤ì¤Î¸ò´¹¤ÏÆÈΩ¤Ë¹Ô¤¦¤³¤È¤¬¤Ç¤¤ë¤Î¤ÇÊÂÎ󲽤¬ÍÆ°× ¸ò´¹²ó¿ô¤¬Í×ÁÇ¿ô¤Ç·è¤Þ¤ë¤Î¤Ç½ªÎ»È½Ä꤬ÉÔÍ× ¥Ç¥á¥ê¥Ã¥È Í×ÁÇ¿ô¤¬2^
マージ・ソート : 巨大データのソート法
はじめに まずはともあれ腕試し、この問題を解いてみてくださいな: 【問1】 デタラメな順序で並んだ文字列の集合がテキストファイル「input.txt」に収められています。この文字列群を辞書順（昇順）に並び換えたテキストファイル「sorted.txt」を作りなさい。 ※各文字列は改行で区切られています。 プログラミング教本の練習問題、あるいは学校の課題で出てきそうな“お馴染み”の問題です。ソート（整列）アルゴリズムの実装には配列/代入/条件分岐/ループなどなどプログラミングの基本中の基本となる構文を総動員するため、練習問題としてよく使われますね。 早速解いてみましょう、ソート・アルゴリズムにはこれまたお馴染みのバブル・ソートを使います。C#、VB.NET、C++/CLIの3本まとめて一気にいきますよ: using System; using System.IO; using System.C
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
