概要 ハッシュ法（チェイン法）を用いてデータの追加・検索・削除を行う。 ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。 チェイン法とは 衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法…

概要 ハッシュ法を使用せず昇順にソートされた状態のデータに新しい値の追加を行う。 バイナリサーチのアルゴリズムを用いて挿入すべき位置を見つけ値を追加し、それ以降の全要素を一つずつ後方へ移動するため、ハッシュ法を用いたデータの追加と比べ効率は…

アルゴリズムの勉強としてRubyで二分探索（バイナリサーチ）を実装する。 二分探索とは ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい…

アルゴリズムの勉強としてRubyで番兵法を用いた線形探索を実装する。 番兵法とは データの終了を示すために配置される特殊なデータを指す。この用語は、微妙に異なる以下の2つの意味で使われる。 ・実データには出現しない、データの終了を表すための専用の…

アルゴリズムの勉強としてRubyで線形探索を実装する。 線形探索とは 線形探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行…

アルゴリズムの勉強としてRubyで分布数え上げソート（カウンティングソート、度数ソートとも呼ばれる）を実装する。 分布数え上げソートとは 分布数え上げソートはソート対象のデータをキーにして、キーの出現回数とその累積度数分布を計算して利用すること…

アルゴリズムの勉強としてRubyでヒープソートを実装する。 ヒープソートとは ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。 アルゴリズムは、以下…

アルゴリズムの勉強としてRubyでマージソートを実装する。 マージソートとは マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボト…

アルゴリズムの勉強としてRubyでクイックソートを実装する。 クイックソートとは クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 n個のデータをソートする際の最良計算量および平均計算量は…

アルゴリズムの勉強としてRubyでシェルソートを実装する。 シェルソートとは シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブル…

アルゴリズムの勉強としてRubyで選択ソートを実装する。 選択ソートとは 選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列された要素から、最大値やまたは最小値を探索し配列最後の要素と入れ替えをおこなうこと。最悪計算時間がO(n2)…

アルゴリズムの勉強としてRubyで挿入ソートを実装する。 挿入ソートとは 挿入ソート（インサーションソート）は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。平均計算時間・最悪計算時間がともにO(n2)と遅いが、ア…

アルゴリズムの勉強としてRubyでバブルソートを実装する。 バブルソートとは ソートのアルゴリズムの一つ。隣り合う要素の大小を比較しながら整列させること。最悪計算時間がO(n2)と遅いが、アルゴリズムが単純で実装が容易なため、また並列処理との親和性が…