ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
ブロックソート - Wikipedia
ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) は、1994年にマイケル・バローズ (Michael Burrows) とデビッド・ホイーラー (David Wheeler) が開発した可逆変換の方式で、データ圧縮の前処理に応用される。 ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理としてMove To Front (MTF)・連長圧縮 (RLE)・エントロピー符号と組み合わせて、データを圧縮する。 実装はbzip2等。 原理[編集] 長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n 行列の第 n 列を取り出したものが、B
「Burrows Wheeler 変換」と逐次構築 - Line 1: Error: Invalid Blog('by Esehara' )
今日の肉 笑点における楽太郎の座布団みたいなもの。 概要 テキスト処理方法の一つとして、Burrows Wheeler 変換というものがある。丁度手元に、その辺りを論じた本があったので、練習がてらに実装してみることにした。 はじめに 自分の書架を整理していたら、奥から『高速文字列解析の世界』という本が出てきた。「そういえば、この本、知りあいにそそのかされて買ったけど、結局のところ詳しく読んでなかったなー」と思ったので、ちゃんと勉強するべく、実装してみることにした。 Burrows Wheeler 変換って何よ 実際のところ、Burrows Wheeler変換というトピックに関しては、いまさらでもある。実際に、2008年において既にnaoyaさんが言及しているくらいだし、適切に「Burrows Wheeler」で検索すれば、このブログよりも適切な解説(例えばこことか)が得られると思う。 まず
50以下挿入ソート、5万以下マージソート、あとはクイックソート | TECHSCORE BLOG | TECHSCORE BLOG
こんにちは、鈴木です。 TECHSCORE Advent Calendar 2014 の 6 日目の投稿です。 寒くなってきたのでソーティングアルゴリズムをいくつか実装して、速度を比較しました。 測定用のプログラムは以下の場所で公開しています。 https://github.com/suzuki-kei/sorting-algorithm 測定結果 まずは測定結果です。 ランダムな整数（int 型）の配列をソートする C++ のプログラムを書いて比較しました。 背景が黄色のセルはその条件（データ数）で最も速かったもの、背景がピンクのセルは 2 番目に速かったものです（時間がかかりすぎて測定を打ち切ったものはグレーです）。 データ数は 2 のべき乗にしたので厳密に速度が逆転するデータ数は分かりませんが、 データ数が 50 以下なら挿入ソート (Insertion Sort) データ数が 5
汎用ソート殺し - d.y.d.
00:26 12/12/18 BookLive! 7月に出会ってからずっと電子書籍ストアとして BookLive! をひいきにしているのですが、一体どこが好きなのか語りたくなりました。 ITMedia の これでもう迷わない、電子書店完全ガイド という一連の記事の、 電子書籍の端末の話よりストアの話をしましょうよというコンセプトに思いっきり影響されています。 といっても、第一印象が「普通のことが普通にできるので感激した！！」というもので、 つまり今年の前半に使っていた幾つかの電子書籍ストア/専用アプリが残念だっただけかもしれません。 買った本がどこをクリックすれば読めるのか理解するのに10分かかった、とか、 6冊以上買うと本棚アプリから画面外に本がはみ出るので手でいちいち棚を変えて整理しないと読めない、とか。 本当に普通に使えるという以上に特筆することもないんですが、 あ、でも、今年になる
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
C++: 構造体を格納したSTLコンテナに対してソート・探索・削除などのアルゴリズムを適用する
C++に慣れている人にとっては当たり前のことかもしれないけど、あまりC++に親しんでいない場合、構造体を格納したSTLコンテナに対してアルゴリズム<algorithm>を有効に活用していないかもしれない。そこで、構造体を格納したvectorなどのSTLコンテナでソートや探索、削除などのアルゴリズムの利用方法を書いておく。 struct A { int n; int* p; }; 上記のような構造体はよく見かける形だと思う。構造体Aに整数型変数のnとポインタ型変数のpがあり、例えばnに配列の要素数、pにその配列を確保したりする。こういった構造体を以下のようにvectorなどのSTLコンテナを使って格納することは多々ある。 vector<A> A_list; これで構造体Aをコンテナに格納できるわけだ。ところで、STLコンテナを使用する一つの理由として便利なアルゴリズムが利用できることが挙げら
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Bubble sort singly linked list in C with pointers
Burrows Wheeler Transform (BWT) — Stringpedia 0.1.0 ドキュメント