ブラウザよりも高速アクセス！
56 関係: 基数ソート、奇偶転置ソート、安定ソート、乱択アルゴリズム、平衡二分探索木、仮想記憶、ノームソート、マージ、マージソート、バッチャー奇偶マージソート、バブルソート、バケットソート、ランダウの記号、リンショーピング大学、リスト (抽象データ型)、ボゴソート、ボストンカレッジ、パンチカード、ヒープソート、データ、データベース、データ構造、ドナルド・クヌース、分割統治法、アルゴリズム、アプリケーションソフトウェア、イントロソート、クイックソート、コムソート、シェルソート、シェーカーソート、シェアソート、ストゥージソート、スターリングの近似、ソーティングネットワーク、全順序、図書館ソート、置換 (数学)、選択アルゴリズム、選択ソート、補助記憶装置、計算理論、計算複雑性理論、計算機科学、記憶装置、鳩の巣ソート、関係データベース、配列、In-placeアルゴリズム、Sort (UNIX)、...、The Art of Computer Programming、探索、検索、挿入ソート、情報工学、時間と空間のトレードオフ。 インデックスを展開 (6 もっと) »
基数ソート
基数ソート（きすうソート、radix sort）は、「比較によらないソート」のアルゴリズムの一つで、位取り記数法で表現可能な対象について、下の桁から順番にソートしてゆき、最後に最上位桁でソートすると、全体が順序通りに並ぶ、という手法である。 nをデータの数、kを桁数として、計算量のオーダーはO(nk)である。また、アルゴリズム自身の性質により、素直な実装が安定ソートになる。.
奇偶転置ソート
奇偶転置ソート（きぐうてんちソート、odd-even sort）は、ソートのアルゴリズムの一つで、バブルソートを、改良したもの。バブルソートではスキャンを一方向に順次行うのに対し、奇偶転置ソートでは組ごとに行う。 バブルソートと同じく安定な内部ソートで、最悪の場合で時間計算量はO(n2)である。 組の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。 そのため、ハードウェアで隣り合う組の比較を同時に処理すれば、常に (n-1) ステップで処理が完了する。 ただし、ソートの対象が多いと必要とするリソースが大きくなり、実用的ではない。.
新しい！!: ソートと奇偶転置ソート · 続きを見る »
安定ソート
安定ソート（あんていソート、stable sort）とは、ソート（並び替え）のアルゴリズムのうち、同等なデータのソート前の順序が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。 たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。.
乱択アルゴリズム
乱択アルゴリズム（らんたくアルゴリズム、Randomized algorithm、ランダム・アルゴリズム）または確率的アルゴリズム（かくりつてき-、Probabilistic algorithm）は、その論理の一部に無作為性を導入したアルゴリズムである。通常のアルゴリズムでは自然数を順番にあてはめるような決定的な部分で、乱数による非決定的な選択を入れることで、「平均的に」よい性能を実現することを目的としている。形式的には、乱択アルゴリズムの性能はランダムビット列で決定される確率変数となる。その期待値を「期待実行時間; expected runtime」と呼ぶ。最悪の場合に関して「無視できる」ほどに低い確率であることが、一般に、この類のアルゴリズムが効果的である要件となる。.
新しい！!: ソートと乱択アルゴリズム · 続きを見る »
平衡二分探索木
平衡二分探索木（へいこうにぶんたんさくぎ、self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。.
新しい！!: ソートと平衡二分探索木 · 続きを見る »
仮想記憶
仮想記憶（かそうきおく、Virtual Memory、バーチャルメモリ）とは、コンピュータ分野におけるメモリ管理の仮想化技法の一種であり、オペレーティングシステムなどが物理的なメモリを、アプリケーション・ソフトウェア（プロセスなど）に対して、専用の連続した主記憶装置に見えるように提供する。 この技術により、物理的な主記憶装置に加えてハードディスク装置等の補助記憶装置を併用すれば、物理的な主記憶装置よりも大きな仮想メモリを提供する事ができる。またアプリケーション・プログラム側は、物理メモリ上のアドレスを意識しなくて良いため、マルチタスクの実現が容易である。このため現代のオペレーティングシステムの多くが仮想記憶をサポートしている。 仮想的に与えられたアドレスを仮想アドレス (virtual address) または論理アドレス (logical address)、実記憶上で有効なアドレスを物理アドレス (physical address) または実アドレス (real address) という。仮想アドレスの範囲を仮想アドレス空間、物理アドレスの範囲を物理アドレス空間という。.
ノームソート
ノームソート（英: gnome sort）はソートアルゴリズムの一種で、挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行う。その名称の由来は、オランダのノームが一列に並んだ鉢植えの花をソートする話である。 非常に単純であり、入れ子のループも必要としない。時間計算量は O(n2) だが、実際にソートしてみると挿入ソートと同程度の性能を発揮する。 このアルゴリズムでは、隣接する2つの要素の順序が正しくないときは、それらを交換する。この交換を行ったとき、「正しくない順序にある隣接要素」が新たに発生するのは、交換した要素の直前か直後だけであるという点に注視する。交換した要素よりも前の部分はまだ整列されていないという前提なので、交換した要素の直後のみを確認すればよいことになる。 また、処理対象全部を読み込む前にソートを開始できるため、標準入力やパイプラインで読み込みながら並行してソート処理が行えるという特徴もある(上の例でいうと、ノームが植木鉢を並べ替えている最中に、ノームよりも前に植木鉢を足していっても並び替えは問題なく完了する)。.
新しい！!: ソートとノームソート · 続きを見る »
マージ
マージ(merge)とは「併合する」、「合併する」という意味であり、情報工学の用語としてよく用いられる。 広義には複数のデータベースやファイル、プログラムなどを一つにまとめる行為を意味する。 狭義には以下で述べる二つの線形リストを一つにまとめるアルゴリズムのことである。.
マージソート
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。 n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースな（すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない）バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする。 （ナイーブな）クイックソートと比べると、最悪計算量は少ない。ランダムなデータでは通常、クイックソートのほうが速い。.
新しい！!: ソートとマージソート · 続きを見る »
バッチャー奇偶マージソート
バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(n (log n)2) かつ深さ O((log n)2) のソーティングネットワークである。これは漸近的に最適（:en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。 the second GPU Gems bookの中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。.
新しい！!: ソートとバッチャー奇偶マージソート · 続きを見る »
バブルソート
バブルソート (bubble sort) は、ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が高いことから、しばしば用いられる。安定な内部ソート。基本交換法、隣接交換法ともいう。（単に交換法と言う場合もある）.
新しい！!: ソートとバブルソート · 続きを見る »
バケットソート
バケットソート（bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。.
新しい！!: ソートとバケットソート · 続きを見る »
ランダウの記号
ランダウの記号（ランダウのきごう、Landau symbol）は、関数の極限における値の変化度合いに、おおよその評価を与えるための記法である。 ランダウの漸近記法 (asymptotic notation)、ランダウ記法 (Landau notation) あるいは主要な記号として O （オーもしくはオミクロン Ο。数字の0ではない）を用いることから（ランダウの）O-記法、ランダウのオミクロンなどともいう。 記号 O は「程度」の意味のオーダー（Order）から。 なおここでいうランダウはエドムント・ランダウの事であり、『理論物理学教程』の著者であるレフ・ランダウとは別人である。 ランダウの記号は数学や計算機科学をはじめとした様々な分野で用いられる。.
新しい！!: ソートとランダウの記号 · 続きを見る »
リンショーピング大学
リンショーピング大学 (スウェーデン語:Linköpings Universitet)は、スウェーデンのリンショーピングにある公立の大学である。1969年に創立された。23の教育部門および4学部を有し、教育センターが設置されている。 教職員3,400人、学部生26,500人、大学院生1,450人。 教育プログラム等のインターディシプリナリ・アプローチ（学際的研究）、インダストリアル・エンジニアリング及び管理、国際的な経営管理(言語研究を含む)、認知科学及び情報技術で有名である。 芸術及び科学の研究は、複数の異なった分野に及ぶ学際的なものであり、感性工学の分野でKansei Engineering Software（KESo）の開発も行われている。 主要なキャンパスは、リンショーピング市の西約3キロメートルにあり、ウァラと呼ばれている。 学生の大部分は隣接した住宅区域w:Rydに住んでいる。 リンショーピング市の南に、大学病院(Universitetssjukhuset)があり、健康科学部で医学教育と研究を行っている。ノルチェピンキャンパスは、リンショーピング市の北東28マイル(45Km)にある。 キャンパス間は、学生は無料の「キャンパス バス」によって結ばれている。 教育はドイツ語、スペイン語またはフランス語のさらなる言語研究から成っている。 2006年に第3回「ビジネス情報技術国際会議」（ITIB 2006）が、ワルシャワ農業大学（Warsaw Agricultural University）、リンショーピング大学とサンクトペテルブルク大学によって組織された。.
新しい！!: ソートとリンショーピング大学 · 続きを見る »
リスト (抽象データ型)
抽象データ型としてのリスト(list)は、順序つきのデータコンテナとして定義される。 リストはたいてい配列や連結リストを使って実装される。これは配列や連結リストと似た特性を持っているからである。また連結リストのことを単にリストと呼ぶこともある。順序を持つ点を強調してシーケンス(列; sequence)と呼び、連結リストと区別することもある。.
新しい！!: ソートとリスト (抽象データ型) · 続きを見る »
ボゴソート
ボゴソート (bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"に由来する。 英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。.
ボストンカレッジ
ボストン市西部、ブライトン・ニュートンの2市にもまたがるチェストナット・ヒル地区に位置する名門私立総合大学。ボストンカレッジの歴史は古く1863年に創立されたボストン市内で最も古い大学だったが、今は移転してボストン市の西10km（約6マイル）の郊外に位置する。丘の上のキャンパスが美しいことで知られており、特にゴシック様式の建物が有名である。また、アメリカで最も古い一般教育の歴史を持つイエズス会が経営する大学であるために、本校はリベラルアーツの一般教育をとりわけ強調している。国内での権威は高く1956年の卒業式演説でカトリック信徒であったジョン・F・ケネディに「イエズス会のアイビー」（"Jesuit Ivy"）と呼ばれたことがある。ヒドゥン・アイビー（Hidden Ivies）の一校に数えられる。 『US News and World Report』誌のAmerica's Best Colleges 2016のNational Universities; Top schools部門において31位、2016年度フォーブス誌 "Top Colleges" ランキングでは全米22位にランクされている。 ボストンカレッジは早稲田大学および上智大学と交換留学協定を結んでいる。 なお、日本ではBoston Collegeがボストン大学と訳されることがしばしばあるが、ボストン大学（Boston University ）は全く別の大学である。.
新しい！!: ソートとボストンカレッジ · 続きを見る »
パンチカード
20世紀に最も広く使われた80欄のパンチカード。寸法は 187.325 mm × 82.55 mm。この例は1964年のEBCDIC文字セットにそれ以前につかわれていた特殊記号を加えて示したものである。 パンチカードは、穿孔カードなどともいう、厚手の紙に穴を開けて、その位置や有無から情報を記録する記録媒体で、以前には鑽孔紙テープとともに多用された。電子式コンピュータ以前のタビュレーティングマシン（パンチカードシステム）の時代から多用されたものであるが、近年はコンピュータ用の主力メディアとしては過去のものとなっている。画像などといった大容量のデータを負担なく扱えるようになる以前には、四角い窓を作ってそこに写真フィルムを張る、といった使い方や、端に切れ込みを入れて串を使った手作業で分類できる edge-notched card（#ハンドソートパンチカードの節を参照）など、紙テープとは違ったカードならではの使い方もある。 現在の使われ方としては、国や地方によっては選挙の投票用であるとか、穴を開けるのではないものの、マークシート用で同一の大きさ・形状・材質のカードが使われていることがある。.
新しい！!: ソートとパンチカード · 続きを見る »
ヒープソート
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである（ヒープ領域とは無関係であることに注意する）。 アルゴリズムは、以下のように2つの段階から構成される。.
新しい！!: ソートとヒープソート · 続きを見る »
データ
データ（data）とは、事実や資料をさす言葉。言語的には複数形であるため、厳密には複数の事象や数値の集まりのことを指し、単数形は datum（データム）である。.
データベース
データベース（database, DB）とは、検索や蓄積が容易にできるよう整理された情報の集まり。 通常はコンピュータによって実現されたものを指すが、紙の住所録などをデータベースと呼ぶ場合もある。コンピュータを使用したデータベース・システムでは、データベース管理用のソフトウェアであるデータベース管理システムを使用する場合も多い。.
新しい！!: ソートとデータベース · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
ドナルド・クヌース
ドナルド・エルビン・クヌース（Donald Ervin Knuth, 1938年1月10日 -）は数学者、計算機科学者。スタンフォード大学名誉教授。 クヌースによるアルゴリズムに関する著作 The Art of Computer Programming のシリーズはプログラミングに携わるものの間では有名である。アルゴリズム解析と呼ばれる分野を開拓し、計算理論の発展に多大な貢献をしている。その過程で漸近記法で計算量を表すことを一般化させた。 理論計算機科学への貢献とは別に、コンピュータによる組版システム TeX とフォント設計システム METAFONT の開発者でもあり、Computer Modern という書体ファミリも開発した。 作家であり学者であるクヌースは、文芸的プログラミングのコンセプトを生み出し、そのためのプログラミングシステム WEB / CWEB を開発。また、MIX / MMIX 命令セットアーキテクチャを設計。.
新しい！!: ソートとドナルド・クヌース · 続きを見る »
分割統治法
分割統治法（ぶんかつとうちほう、divide-and-conquer method）は、そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。.
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: ソートとアルゴリズム · 続きを見る »
アプリケーションソフトウェア
アプリケーションスイートである。 アプリケーションソフトウェア（application software, 応用ソフトウェア）は、アプリケーション（応用）プログラムともいい、ワープロや表計算などといった、コンピュータを「応用」する目的に応じた、コンピュータ・プログラムである。なお、それに対してシステムプログラムは、アプリケーションプログラムに対して処理実行のための計算機資源を抽象化して提供する、などのインフラとしての役割のプログラムであり、ユーザーが要求する情報処理を直接実行するものではなく、ユーザーが普段は意識することはない裏方的な存在がシステムプログラムである。.
新しい！!: ソートとアプリケーションソフトウェア · 続きを見る »
イントロソート
イントロソート（英: 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)である。また数々の変種がある。 安定ソートではない。.
新しい！!: ソートとクイックソート · 続きを見る »
コムソート
ムソート（comb sort）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した。 バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。.
シェルソート
ェルソート（改良挿入ソート、）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。ドナルド・シェル（Donald L. Shell）が、1959年に、シェルソートの最初のバージョンを公開した 。シェルソートの実行時間は、比較時に選ぶ間隔によって大きく異なる。多くの実用的な方法が提案されているが、正確な時間計算量を求める方法は、未解決問題である。.
新しい！!: ソートとシェルソート · 続きを見る »
シェーカーソート
ェーカーソート (shaker sort) は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。 バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。 バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。.
新しい！!: ソートとシェーカーソート · 続きを見る »
シェアソート
ェアソート（shear-sort）は、ソートのアルゴリズムの一つ。シェアソートでは、データを長方形に並べた上で、各行／各列ごとにソートを行なう。1989年に Isaac D. Scherson らが発表した。安定ではない内部ソートであり、最悪の場合の時間計算量はO(n1.5)である。各行／各列の比較は互いに独立であるため、バブルソートとは異なり、並列動作が可能である。.
新しい！!: ソートとシェアソート · 続きを見る »
ストゥージソート
トゥージソート（Stooge sort）は、再帰を用いたソートアルゴリズムのひとつである。 計算時間はであり、これはマージソートなどの効率的なアルゴリズムよりも、それどころか非常に効率の悪い単純なソートの例としてよく挙げられるバブルソートよりも遅い。 アルゴリズムは以下の通りである。.
新しい！!: ソートとストゥージソート · 続きを見る »
スターリングの近似
log ''n''! と ''n'' log ''n'' − ''n'' は ''n'' → ∞ のとき漸近する スターリングの近似（Stirling's approximation）またはスターリングの公式（Stirling's formula）は、階乗、あるいはその拡張の一つであるガンマ関数の漸近近似である。名称は数学者に因む。.
新しい！!: ソートとスターリングの近似 · 続きを見る »
ソーティングネットワーク
ーティングネットワーク（sorting network）とは、ワイヤとコンパレータからなる、数列をソートするネットワーク（抽象的な数理モデル）である。一つのコンパレータが二つのワイヤを繋ぎ、小さい方の値を一方に、大きい方の値を他方に出力する。これによって値のソートが行われる。比較ソートアルゴリズムとソーティングネットワークの主な違いは、比較の順序が、それまでの比較の結果によらずあらかじめ決まっていることである。このため、アルゴリズムを並列に実行することが容易である。モデルは単純だが、ソーティングネットワークの理論は非常に深く、複雑である。.
新しい！!: ソートとソーティングネットワーク · 続きを見る »
全順序
数学における線型順序（せんけいじゅんじょ、linear order）、全順序（ぜんじゅんじょ、total order）または単純順序（たんじゅんじゅんじょ、simple order）は、推移的、反対称かつ完全な二項関係を言う。集合と全順序を組にしたものは、全順序集合 (totally ordered set), 線型順序集合 (linearly ordered set), 単純順序集合 (simply ordered set) あるいは鎖 (chain) と呼ばれる。 即ち、集合 X が関係 ≤ によって全順序付けられるとき、X の任意の元 a, b, c に対して、以下の条件 が満足される。 反対称性によって a < b でも b < a でもあるような不確定な状態は排除される。完全性を持つ関係は、その集合の任意の二元がその関係でであることを意味する。これはまた、元を直線に並べた図式によってその集合が表せるということでもあり、それは「線型」順序の名の由来である。また完全性から反射性 (a ≤ a) が出るから、全順序は半順序の公理を満たす。半順序は（完全性の代わりに反射性のみが課されるという意味で）全順序よりも弱い条件である。与えられた半順序を拡張して全順序をえることは、半順序のと呼ばれる。.
図書館ソート
図書館ソートまたはライブラリソート（英: library sort, gapped insertion sort）は、ソートのアルゴリズムの一つ。挿入ソートをベースとし、挿入操作を高速化するために配列に隙間（gap）を設けるもの。名前は次のアナロジーに由来する: 司書が長い本棚にアルファベット順に本を陳列しようとしているとする。本棚は左端がAで始まり、右端のZの終わりまで隙間なく本で埋まっている。司書が新しい本をBの区画に収めるには、Bの区画に適切な位置を見つけ、スペースを空けるために後ろのすべての本をずらす必要がある。これが挿入ソートである。しかし、各区画の間(BとCの境界など)に空白があったなら、新しい本のためにずらすべき本の数は少なくて済む。これが図書館ソートの基本的な原理である。 このアルゴリズムは2004年にMichael A. Bender、Martín Farach-ColtonおよびMiguel Mosteiroによって提案され、2006年 に発表された。 図書館ソートはそのベースとなる挿入ソートと同様、安定な比較ソートであり、オンラインアルゴリズムとして実行可能。しかしながら O(n2) の挿入ソートとは異なり、高確率でクイックソートと同じクラスの O(n log n) で実行できることが示されている。この改良のために使われた仕組みはスキップリストのものとほぼ同様である。論文では、完全な実装も、挿入や調整(rebalance)のような重要な部分の正確なアルゴリズムも示されていない。図書館ソートが他のソートアルゴリズムと比べて現実的にどの程度有効であるかを議論するには、さらなる情報が必要となる。 基本的な挿入ソートと比べて、図書館ソートの欠点は隙間のための空間を要することである。スペースの量や配置は実装による。論文において、必要な配列の長さは (1 + ε)n だとされているが、ε の選び方は何も推奨されていない。 挿入ソートの弱点の一つに、メモリへの書き込みが高コストである時に、多くの回数の swap 操作が負荷になりるというものがある。図書館ソートは要素の移動が少なくなるように改良されているので、挿入段階が多少改善される可能性があるが、調整の段階で追加のコストを要する。加えて、ランダムなデータセットからの挿入操作がキャッシュから外れたメモリにアクセスする可能性があり、特に大きなデータセットについて、参照の局所性がマージソートに劣る。.
新しい！!: ソートと図書館ソート · 続きを見る »
置換 (数学)
数学における置換（ちかん、permutation）の概念は、いくつか僅かに異なった意味で用いられるが、いずれも対象や値を「並べ替える」ことに関するものである。有り体に言えば、対象からなる集合の置換というのは、それらの対象に適当な順番を与えて並べることを言う。例えば、集合 の置換は、 の全部で六種類ある順序組である。単語のアナグラムは、単語を構成する文字列に対する置換として定められる。そういった意味での置換の研究は、一般には組合せ論に属する話題である。 相異なる n 個の対象の置換の総数は 通りであり、これは "n!" と書いて n の階乗と呼ばれる。 置換の概念は、多かれ少なかれ（あるいは陰に陽に）、数学のほとんどすべての領域に現れる。たとえばある有限集合上に異なる順序付けが考えられる場合に、単にそれらの順番を無視したいとか、無視した時にどれほどの配置が同一視されるかを知る必要があるなどの理由で、置換が行われることも多い。同様の理由で、置換は計算機科学におけるソートアルゴリズムの研究において生じる。 代数学、特に群論において、集合 S 上の置換は S から自身への全単射（つまり写像 で S の各元が像としてちょうど一つずつ現れるもの）として定義される。これは各元 s を対応する f(s) と入れ替えるという意味での S の並び替え (rearrangement) と関連する。このような置換の全体は対称群と呼ばれる群を成す。重要なことは、置換の合成が定義できること、つまり二つの並び替えを続けて行うと、それは全体として別の並べ替えになっているということである。S 上の置換は、S の元（あるいはそれを特定の記号によって置き換えたもの）を対象として、それらに対象の並び替えとして作用する。 初等組合せ論において、「」はともに n 元集合から k 個の元を取り出す方法として可能なものを数え上げる問題に関するもので、取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。k.
新しい！!: ソートと置換 (数学) · 続きを見る »
選択アルゴリズム
選択アルゴリズム（selection algorithm）とは、数列から k 番目に小さい（あるいは k 番目に大きい）数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。.
新しい！!: ソートと選択アルゴリズム · 続きを見る »
選択ソート
選択ソート（selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。内部ソート。後述するように、安定ソートではない。 このアルゴリズムを改良したソート法として、ヒープソートが挙げられる。.
補助記憶装置
パーソナルコンピュータのハードディスク 補助記憶装置（ほじょきおくそうち）は記憶装置の分類で、「主記憶装置」がコンピュータのメインのバスに直接接続され、CPUが即座にアクセスでき、演算の対象にもできる場合もあるのに対し、外部バスに接続され、CPUからは直接アクセスできないものを指す。レイテンシやスループットは遅いが比較すると大容量である。二次記憶装置などとも。.
新しい！!: ソートと補助記憶装置 · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。.
新しい！!: ソートと計算複雑性理論 · 続きを見る »
計算機科学
計算機科学（けいさんきかがく、computer science、コンピュータ科学）とは、情報と計算の理論的基礎、及びそのコンピュータ上への実装と応用に関する研究分野である。計算機科学には様々な下位領域がある。コンピュータグラフィックスのように特定の処理に集中する領域もあれば、計算理論のように数学的な理論に関する領域もある。またある領域は計算の実装を試みることに集中している。例えば、プログラミング言語理論は計算を記述する手法に関する学問領域であり、プログラミングは特定のプログラミング言語を使って問題を解決する領域である。.
記憶装置
GB SDRAM。一次記憶装置の例 GB ハードディスクドライブ(HDD)。コンピュータに接続すると二次記憶装置として機能する SDLT テープカートリッジ。オフライン・ストレージの例。自動テープライブラリで使う場合は、三次記憶装置に分類される 記憶装置（きおくそうち）は、コンピュータが処理すべきデジタルデータをある期間保持するのに使う、部品、装置、電子媒体の総称。「記憶」という語の一般的な意味にも対応する英語としてはメモリ（memory）である。記憶装置は「情報の記憶」を行う。他に「記憶装置」に相当する英語としてはストレージ デバイス（Storage Device）というものもある。.
鳩の巣ソート
鳩の巣ソート（はとのすソート、pigeonhole sort）はソートアルゴリズムの一種であり、要素数 (n) とソートキーの値の個数 (N) がほぼ同じ場合に適した手法である。必要な時間計算量は Θ(n + N) である。.
新しい！!: ソートと鳩の巣ソート · 続きを見る »
関係データベース
関係データベース（かんけいデータベース、リレーショナルデータベース、英: relational database）は関係モデル（リレーショナルデータモデル、後述）にもとづいて設計、開発されるデータベースである。関係データベースを管理するデータベース管理システム (DBMS) を関係データベース管理システム (RDBMS) と呼ぶ。 Oracle Database、Microsoft SQL Server、MySQL、PostgreSQL、DB2、FileMaker、H2 Database などがRDBMSである関係データベースに含まれないデータベースは、NoSQL などを参照。 。.
新しい！!: ソートと関係データベース · 続きを見る »
配列
この記事では、コンピュータ・プログラムにおいて配列（はいれつ、array）と呼ばれているデータ構造およびデータ型について説明する。計算科学方面ではベクトルという場合もある。また、リストも参照。一般に、添え字で個々の要素を区別する。.
In-placeアルゴリズム
in-placeアルゴリズムとは、計算機科学においてデータ構造の変換を行うにあたって、追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。 in-place とは「その場で」といった意味であり、入力が出力で上書きされることが多いことから来る用語である。 in-place でないアルゴリズムは not-in-place あるいは out-of-place などと呼ばれることもある。 in-placeの定義にはやや揺れがある。最も狭義にはポインタなども含めて一定の空間しか使用しないアルゴリズムを指す。しかし長さnの配列の添字を表すだけでも O(log n) の空間を必要とするため、この意味で in-place であるアルゴリズムはごく限られている。多くの場合、 O(log n) の空間を使うことが許される。より広く O((log n)const.) 程度まで認めることもあり、時には o(n) であればよいとすることもある。 入力を出力で上書きしない場合、出力を追加の記憶領域とみなすかどうかについても揺れがある。出力先が通常の記憶装置である場合は記憶領域に含めて評価するが、書き込み専用メモリやストリームに出力する場合にはその大きさを無視して作業領域だけを評価することがある。特に対数領域帰着のような計算複雑性理論の問題では出力空間を無視するのが一般的である（その場合、出力をライトオンリーとすることが本質的に必要である）。.
新しい！!: ソートとIn-placeアルゴリズム · 続きを見る »
Sort (UNIX)
sort --help sort（ソート）は、UNIXに標準的に存在するコマンド行プログラムの一種であり、入力の各行をソートされた順序で出力するものである。.
新しい！!: ソートとSort (UNIX) · 続きを見る »
The Art of Computer Programming
『』は、コンピュータプログラミングに関する書籍である。様々なアルゴリズムについて、その背景や歴史まで踏み込んだ徹底的な解説を行っている。著者のドナルド・クヌース は、自身のライフワークと位置づけている。 その全体構想から見れば現在も未完であるが、十分な業績としてみなされていることは、3巻初版までが刊行されていた1974年に受賞したチューリング賞の受賞理由に功績として本シリーズが含まれていることからも分かる。また、1976年に2巻の第2版の準備をしていた際に、初版のような鉛版による組版 (en:Hot metal typesetting) が行われなくなっていたために仕上がりに納得せず、組版システムの TeX を（当初は1978年のサバティカルが終わるまでには完全に仕上げるつもりで）作り始めてしまったことなど、逸話も多い。 現在3巻までと4巻の分冊が刊行されている。今後の計画についてはwebページで確認できるが、おおむね執筆開始当初の構想と変わっておらず、5巻は構文的 (syntactic) アルゴリズムについてで、9章が字句スキャナ、10章が（文字列）解析の技術、6巻は文脈自由文法の理論、7巻がコンパイラ技術となっている。ただし位置付けとして、5巻までの内容は central core of computer programming for sequential machines であるのに対し、6・7巻の内容は important but more specialized である、としている（またドラゴンブック等、この40年の間に書籍が充実した分野でもある）。 近年では、アスキーから日本語訳が出版されていた。2007年9月現在で3巻までと改訂版分冊1巻、4巻の分冊2,3が刊行されていた。その後、KADOKAWAドワンゴに在籍する元アスキーの編集者が担当する「アスキードワンゴ」レーベルにより、2015年6月の1巻再刊から再開され、2017年3月に4巻の最初のまとまった分冊である4A巻が刊行されている。 サイエンス社から出版されていた旧日本語訳版は、原著2巻相当分の4巻までしか出ていない。また、出版時期が古いためもあるが、専門用語について可能な限りカタカナ語を使わず訳すという少々冒険的な方針のために独特の用語が多用されており、和訳における専門用語の扱いにおける歴史的な一例にもなっている。.
新しい！!: ソートとThe Art of Computer Programming · 続きを見る »
探索
探索（たんさく、search）とは、特定の制約条件を満たす物を見つけ出す行動のこと。何か問題を解くに当たって、有効な解析的な解法を用いることのできない場合は、試行錯誤によって解を得る場合もある。一部のアルゴリズムは、元々、機械学習と並んで人工知能の分野のアルゴリズムであるが、現在はその他の分野にも応用されている。類義語として検索（search）も参照。.
検索
検索（けんさく、search）とは、データの集合の中から目的とするデータを探し出すことである。古くは図書館の所蔵物を探し出したり、辞書の項目を引いたりといった人手で行うのが主だったが、コンピューターの発達により、テキスト文字列の検索（文書検索、文字列探索）、画像データの検索（画像検索）、音声データの検索（音声検索）など、大規模かつマルチメディアの情報に関する検索技術が発展した。さらにデータベースの発展とインターネットの普及に伴い、分散保管されているデータに対する検索技術が研究されている。ファイルの内容に対して文字列探索を行う機能も検索と呼ばれる。.
挿入ソート
挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、しばしば用いられる。安定な内部ソート。基本挿入法ともいう。in-placeアルゴリズムであり、オンラインアルゴリズムである。 挿入ソートを高速化したソート法として、シェルソートが知られている。.
情報工学
情報工学（じょうほうこうがく）は情報分野についての工学である。語感としては、情報科学という語がもっぱらおおまかに「科学」という語が指す範囲を中心としているのに対し、「工学」的な分野に重心があるが、内実としてはどれもたいして変わらないことが多い（たとえば、大学の学部学科名などに関しては、個々の大学の個性による違いのほうが、名前による違いより大きい）。日本で、大学の工学部などにコンピュータ科学ないし情報関係の学科を設置する際に、「工学」部という語との整合のためだけに便利に使われた、という面が大きい（情報工学科の記事を参照）。 なお英語の information engineering はソフトウェア工学における一手法であり、日本語の「情報工学」とは対応しない。また似た言葉に情報学がある。.
時間と空間のトレードオフ
計算機科学における時間と空間のトレードオフ（じかんとくうかんのトレードオフ、space-time tradeoff）または時間と記憶域のトレードオフ（じかんときおくいきのトレードオフ、time-memory tradeoff、タイム・メモリ・トレードオフ）とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。 時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる。しばしば、時間と空間のトレードオフを利用して、問題の複雑性クラスを変えるというテクニックも使用される。 時間と空間のトレードオフの例として最も一般的なのはルックアップテーブルを利用したアルゴリズムである。テーブルの全てを最初から持つようにした実装では、処理時間は削減できるが、必要なメモリの量は増加する。また、テーブルの要素をその都度計算することもでき、これは計算時間は増加するが、必要なメモリの量を削減できる。 時間と空間のトレードオフは、データストレージにも当てはまる。データを圧縮せずに保存すると、圧縮した場合と比べ、消費する容量は多く、必要な時間は短くなる。データの圧縮によって保存に必要な領域を減らすことができるが、データ圧縮処理を行う時間が必要になる。どちらが適切かは場合によって異なる。 もう一つの例として、数式をウィキペディアで表示する方法が挙げられる。LaTeXのソースだけを保存しておき、ページを表示する度にそれをレンダリングする方法をとれば、時間はかかるが、記憶装置の使用量は少なくて済み、空間を時間でまかなうことができる。ページが保存されたときに画像をレンダリングし、それを保存しておく方法をとれば、記憶装置の使用量は多くなるが、時間は短くて済み、時間を空間でまかなうことができる。 時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散対数の計算で利用されるbaby-step giant-stepアルゴリズムがある。 他の分野では、暗号システムに対する総当たり攻撃におけるレインボーテーブルの作成が、時間と空間のトレードオフにあたる。中間一致攻撃も時間と空間のトレードオフの応用である。.
新しい！!: ソートと時間と空間のトレードオフ · 続きを見る »
