アルゴリズムとデータ構造 - マージソート
2020年2月1日概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 マージソート データ列が分割できなくなるまで（要素が1つ）再帰的に分割を行い、分割されたデータを複数回マージを繰り返していくことによってソートする 分割統治法に基づくソート 大きな問題を小さな問題に分割する 計算時間 最悪計...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 マージソート データ列が分割できなくなるまで（要素が1つ）再帰的に分割を行い、分割されたデータを複数回マージを繰り返していくことによってソートする 分割統治法に基づくソート 大きな問題を小さな問題に分割する 計算時間 最悪計...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープソート 要素の並べ替えを二分ヒープ木を用いて行うソート ヒープの構築 ヒープから要素（根）を取り出す操作をヒープ木が空になるまで行う 計算時間 最悪計算時間、平均計算時間 O(n log n) 実装package...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 挿入ソート データ列の先頭から順番にソートしていく ソート済みと未ソートでそれぞれ部分列に分けられる 1回目：0番目をソート済みとするので何もしない 2回目：0番目と1番目を比較して順序が逆なら入れ変える 3回目：0番目から1番目...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 選択ソート データを昇順または降順に並べ変えるソートの一つ １番目の要素と2番目以降の要素の中で最小の値を比較して、順序が逆なら入れ変えを行う、という操作をデータ列の最後の一つ手前まで繰り返す 計算時間 最良計算時間、平均計算時...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 バブルソート データを昇順または降順に並べ変えるソートの一つ 全要素に対して、隣合う要素同士を比較し、順序が逆なら入れ替えを行う、という操作を要素数-1回繰り返す 計算時間 最悪計算時間、最良計算時間、平均計算時間 O(n²) ...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 二分探索木 各ノードが多くとも2つまでのノードしか持たない二分木の一種で、左の子ノード ≤ 親 ≤ 右の子ノードという制約を持った構造の木 最も左にあるノードが最小ノードで、最も右にあるノードが最大ノードとなる 二分探索木に限...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープ 優先度付きキュー（priority queue）の一種 優先度付きキューは、集合（set）を扱うデータ型 集合に含まれる要素は優先度順に取り出される 集合を扱うデータ型の例：キュー、スタック ヒープの種類 ...
概要 アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ハッシュマップ ハッシュ値を添え字とした配列 ハッシュの衝突処理 開番地法 衝突が生じた際に、ハッシュ関数とは別の関数を使って別の番地を求める方法。 連鎖法 衝突が生じても新しい番地を求めずに、衝突した番地に衝突したキー同...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 キュー 常に先に追加されたデータからしかアクセスできないようにデータを一列に並べた構造 スタックとは追加と削除の方向が逆になる。 FIFO(First In First Out) 先入れ先出し 待ち行列ともいう。 データの...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 スタック 常に最新のデータからしかアクセスできないようにデータを一列に並べた構造 LIFO(Last In First Out) 後入れ先出し 常に最新のデータへアクセスしたいときに便利な構造 データの追加をPush、削除...