ブラウザよりも高速アクセス！
17 関係: 参照の局所性、安定ソート、並列化、二分ヒープ、ランダウの記号、ヒープ、ヒープ領域、アルゴリズム、イントロソート、クイックソート、ソート、サブルーチン、再帰、配列、技術評論社、木構造 (データ構造)、擬似コード。
参照の局所性
参照の局所性（さんしょうのきょくしょせい、locality of reference）とは、1つのリソースに複数回アクセスする処理に関する情報工学上の概念である。.
新しい！!: ヒープソートと参照の局所性 · 続きを見る »
安定ソート
安定ソート（あんていソート、stable sort）とは、ソート（並び替え）のアルゴリズムのうち、同等なデータのソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。 たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。.
新しい！!: ヒープソートと安定ソート · 続きを見る »
並列化
並列化（へいれつか）は、コンピュータにおいて、同時に複数の演算処理を実行すること（並列計算）によって処理のスループットを上げるプログラミング手法である。.
新しい！!: ヒープソートと並列化 · 続きを見る »
二分ヒープ
二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ構造)の特に単純な種類のひとつである。それは、二分木に、以下の2つの制約を追加したものとみなせる。.
新しい！!: ヒープソートと二分ヒープ · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: ヒープソートとランダウの記号 · 続きを見る »
ヒープ
ヒープ（heap）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。 二分ヒープのインデックス付け.
新しい！!: ヒープソートとヒープ · 続きを見る »
ヒープ領域
ヒープ領域（heap memory）はコンピュータープログラミングにおいて、動的に確保可能なメモリの領域。ヒープ (heap) とは、『山積み』という言葉の中の『山』をさす英単語である。 データ構造のヒープと直接的な関係があるかどうかは、ヒープ領域の構造の設計、保守にデータ構造のヒープの技術を使うかどうかに依る（あらゆるデータ構造とヒープ領域の関係について「直接的な関係があるかどうかは、ヒープ領域の構造の設計、保守にそのデータ構造の技術を使うかどうかに依る」ということが言えるので、データ構造のヒープについても、こう主張することが絶対的な間違いだとは言い切れない）。 ヒープ領域は、2種類のラベルを持つ双方向リストによって構成されている。初期状態では、リストはひとつの「未使用」ノードが全体を占めていて、メモリ確保関数(C言語のmalloc, C++のnew等)によって、「未使用」ノードから必要な分を切り取って「使用中」ノードと「未使用」ノードに分ける。確保したメモリが不要になった場合には、メモリ解放関数(C言語のfree, C++のdelete等)によってノードのラベルを「未使用」に書き換える。解放のつど、あるいはカウンタによって一定水準に達した時、連続した個々の「未使用」ノードを結合し、大きな「未使用」ノードに還元する。「未使用」ノードが不足した場合には、オペレーティングシステムに領域拡大を要求しヒープ領域を拡大するか、飛び飛びの未使用領域を連続な未使用領域に統合する。これをごみ集め(garbage collection)という。 ヒープ領域により、変数を動的に確保できる利点がある。欠点としては領域の確認・確保の時間にばらつきがあり処理時間の見積もりが困難になることと、領域の確保と解放の繰り返しによりヒープ上にどこからも参照しない領域が発生することがある。この領域を塵（garbage）という。 「未使用ノード」と「使用中」ノードが混在、つまり塵によりヒープの未使用領域がバラバラに分断された状態をフラグメンテーション状態と呼ぶ。.
新しい！!: ヒープソートとヒープ領域 · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ヒープソートとアルゴリズム · 続きを見る »
イントロソート
イントロソート（英: introsort）は、David Musser が1997年に設計したソートアルゴリズムである。最初はクイックソートを行い、再帰のレベルがソートされた要素数（の対数）を超えるとヒープソートに切り替える。最悪でも O(n log n) であり、同時に典型的なデータに対するソートではクイックソートに匹敵する性能を示す。クイックソートもヒープソートも比較ソートであり、イントロソートも同様である。 クイックソートでは、ピボット（リストを分割する位置）の選択が重要である。リストの先頭や最後尾をピボットに選ぶと、ほぼソートされた入力について最悪の性能を示す。ニクラウス・ヴィルトはこれを避けるため、中央の位置をピボットに選ぶようにしたが、工夫をこらした並びに対しては最悪で O(n2) となる。先頭、最後尾、中央の値の中央値となる位置をピボットにするアルゴリズムもある。実際のデータのソートはこれでほとんどうまくいくが、これを出し抜くように工夫したリストを作ることができ、性能を大幅に低下させることができる。例えば、そのようなリストを使ったDoS攻撃がありうる。 Musser によれば、クイックソートが最悪値を示すようなリストであっても、イントロソートではその1/1200の時間でソートを完了する。Musser は Robert Sedgewick が考案したキャッシュメモリの効果を考慮したソートアルゴリズムも検討した。それは、細かい部分について挿入ソートを1回最後に行うというものである。彼によると、イントロソートではキャッシュミス率は2倍になるが、両端キューを使った実装では劇的に性能を改善できるため、テンプレートライブラリに保持すべきだとしている（特に、キャッシュの保持されている間にソートを行わないこともあるため）。 同様に、Musser は最悪時間でも線形の選択アルゴリズムも考案した。その時間計算量はアントニー・ホーアのアルゴリズムに匹敵する（ホーアのアルゴリズムは選択アルゴリズムとして最も効率的とされているアルゴリズムで、クイックソートを単純に利用している）。これをイントロ選択 (introselect) アルゴリズムと呼ぶ。 2000年6月、SGI C++ Standard Template Library で、Musser のイントロソートの手法を利用した不安定ソートの実装をした。ヒープソートに切り替える再帰の深さは引数で指定でき、最終段は Sedgewick の挿入ソートを使う方式である。挿入ソートに切り替わる再帰の深さは16だった。.
新しい！!: ヒープソートとイントロソート · 続きを見る »
クイックソート
イックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 n個のデータをソートする際の最良計算量および平均計算量はO(n\log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^2)である。また数々の変種がある。 安定ソートではない。.
新しい！!: ヒープソートとクイックソート · 続きを見る »
ソート
ート は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていたが、もう使われていない） 主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、）という。 対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。.
新しい！!: ヒープソートとソート · 続きを見る »
サブルーチン
ブルーチン（subroutine）は、コンピュータプログラミングにおいて、プログラム中で意味や内容がまとまっている作業をひとつの手続きとしたものである。繰り返し利用されるルーチン作業をモジュールとしてまとめたもので、呼び出す側の「主」となるもの（メインルーチン）と対比して「サブルーチン」と呼ばれる。サブプログラム (subprogram) と呼ばれることもある。また、「サブ」をつけずに「ルーチン」と呼ぶこともある。 プログラムのソース中で、繰り返し現れる作業をサブルーチン化することで、可読性や保守性を高く保つことができる。繰り返し現れる作業でなくても、意味的なまとまりを示すためにサブルーチン化することもある。また、キャッシュのような階層的メモリの設計を持つコンピュータ（現在のパソコンやワークステーションなどほぼすべて）では、よく使われるサブルーチンがキャッシュに格納されることで高速な動作を期待できる。.
新しい！!: ヒープソートとサブルーチン · 続きを見る »
再帰
再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。 主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳（回帰#物理学及び再帰性を参照のこと）や、reflexiveの訳として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。.
配列
この記事では、コンピュータ・プログラムにおいて配列（はいれつ、array）と呼ばれているデータ構造およびデータ型について説明する。計算科学方面ではベクトルという場合もある。また、リストも参照。一般に、添え字で個々の要素を区別する。.
技術評論社
株式会社技術評論社（ぎじゅつひょうろんしゃ）は、日本の出版社。主にコンピュータ関連の書籍・雑誌を発行している。.
新しい！!: ヒープソートと技術評論社 · 続きを見る »
木構造 (データ構造)
親子構造 木構造（きこうぞう）とは、グラフ理論の木の構造をしたデータ構造のこと。.
新しい！!: ヒープソートと木構造 (データ構造) · 続きを見る »
擬似コード
擬似コード （ぎじコード、pseudocode）とは、アルゴリズムなどを、架空の非常に高水準なプログラミング言語（擬似言語）で記述したものである。Pascal、Fortran、C言語などの既存のプログラミング言語の構文と、自然言語に近い表現を組み合わせて記述することが多い。.
新しい！!: ヒープソートと擬似コード · 続きを見る »
