ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
選択ソートと挿入ソートの違い - Sideswipe
両者を同一視している方が多い上に、ぱっと見アルゴリズムが似ているこの2つ。 実は結構差があるので詳しく見てみましょう。 アルゴリズム ふたつのアルゴリズムの詳細については wikipedia がそこそこ詳しいのでそちらを参照してください。 挿入ソート 挿入ソートは「既にソート済みのデータ列に対して、新しい要素を正しい位置に挿入する」ことを繰り返していくアルゴリズムです（ wikipedia:挿入ソート ）。 選択ソート 対して、選択ソートは「整列されていない最小（最大）の要素を1つ取り出し、整列済みデータの末尾に加える」操作を繰り返していくアルゴリズムです（wikipedia:選択ソート）。 計算量 平均計算量、最悪計算量はどちらも です。 ところが、最良計算量は挿入ソートが に対して、選択ソートはになります。ここについて詳しく見てみましょう*1。 以下では昇順にソートすることを前提として
高速な安定ソートアルゴリズム "TimSort" の解説 - Preferred Networks Research & Development
先日、TimSortというソートアルゴリズムが話題になりました。TimSortは、高速な安定ソートで、Python(>=2.3)やJava SE 7、およびAndroidでの標準ソートアルゴリズムとして採用されているそうです。 C++のstd::sort()よりも高速であるというベンチマーク結果1が話題になり(後にベンチマークの誤りと判明)、私もそれで存在を知りました。実際のところ、ランダムなデータに対してはクイックソート(IntroSort)ほど速くないようですが、ソートというシンプルなタスクのアルゴリズムが今もなお改良され続けていて、なおかつ人々の関心を引くというのは興味深いものです。 しかしながら、オリジナルのTimSortのコードは若干複雑で、実際のところどういうアルゴリズムなのかわかりづらいところがあると思います。そこで今回はTimSortのアルゴリズムをできるだけわかりやすく解
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
