Post

データ構造

2020-02-01 16:02:47

アルゴリズムとデータ構造 - クイックソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 クイックソート データ列の中から適当なデータ(ピボット)を選択し、ピボットより小さいデータを前方、大きいデータを後方に移動させる。 分割されたデータをそれぞれソートする 分割統治法の一種 計算時間 最悪計算時間 O(n²) 最良計算時間、平均計算時間 O(n log n) 実装package main import ( "fmt" "math/rand" ) func quickSort(n [...

プログラミング

アルゴリズム データ構造 クイックソート

2020-02-01 16:02:11

アルゴリズムとデータ構造 - マージソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 マージソート データ列が分割できなくなるまで(要素が1つ)再帰的に分割を行い、分割されたデータを複数回マージを繰り返していくことによってソートする 分割統治法に基づくソート 大きな問題を小さな問題に分割する 計算時間 最悪計算時間 O(n log n) 実装// cf. https://github.com/TheAlgorithms/Go/blob/master/sorts/merge_sort.go packa...

プログラミング

アルゴリズム データ構造 マージソート

2020-02-01 16:01:16

アルゴリズムとデータ構造 - ヒープソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープソート 要素の並べ替えを二分ヒープ木を用いて行うソート ヒープの構築 ヒープから要素(根)を取り出す操作をヒープ木が空になるまで行う 計算時間 最悪計算時間、平均計算時間 O(n log n) 実装package main import "fmt" // Heap is a heap. type Heap struct { values []int size int max...

プログラミング

アルゴリズム データ構造 ヒープソート

2020-02-01 16:00:17

アルゴリズムとデータ構造 - 挿入ソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 挿入ソート データ列の先頭から順番にソートしていく ソート済みと未ソートでそれぞれ部分列に分けられる 1回目:0番目をソート済みとするので何もしない 2回目:0番目と1番目を比較して順序が逆なら入れ変える 3回目:0番目から1番目までのデータ列と比較、順序入れ替え 4回目:0番目から2番目までのデータ列と比較、順序入れ替え 以下、未ソート部分がなくなるまで繰り返す 計算時間 O(n²) 実装package main...

プログラミング

アルゴリズム データ構造 挿入ソート

2020-02-01 15:59:35

アルゴリズムとデータ構造 - 選択ソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 選択ソート データを昇順または降順に並べ変えるソートの一つ 1番目の要素と2番目以降の要素の中で最小の値を比較して、順序が逆なら入れ変えを行う、という操作をデータ列の最後の一つ手前まで繰り返す 計算時間 最良計算時間、平均計算時間 バブルソートと同じくО(n²) 実装package main func selectionSort(n []int) []int { for i := 0; i < len(...

プログラミング

アルゴリズム データ構造 選択ソート

2020-02-01 15:58:14

アルゴリズムとデータ構造 - バブルソート

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 バブルソート データを昇順または降順に並べ変えるソートの一つ 全要素に対して、隣合う要素同士を比較し、順序が逆なら入れ替えを行う、という操作を要素数-1回繰り返す 計算時間 最悪計算時間、最良計算時間、平均計算時間 O(n²) 実装package main import "fmt" func bubbleSort(n []int) []int { for i := 0; i < len(n)-1; i...

プログラミング

アルゴリズム データ構造 バブルソート

2020-01-15 22:40:24

アルゴリズムとデータ構造 - 二分探索木

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 二分探索木 各ノードが多くとも2つまでのノードしか持たない二分木の一種で、左の子ノード ≤ 親 ≤ 右の子ノードという制約を持った構造の木 最も左にあるノードが最小ノードで、最も右にあるノードが最大ノードとなる 二分探索木に限った話ではないが、木構造の走査(traverse)方法についてかいておく 深さ優先探索(depth-first search) 前順(行きがけ順、前置順、preorder) 中順(通りがけ順、中置順、...

プログラミング

アルゴリズム データ構造 二分探索木

2020-01-14 22:04:54

アルゴリズムとデータ構造 - ヒープ

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープ 優先度付きキュー(priority queue)の一種 優先度付きキューは、集合(set)を扱うデータ型 集合に含まれる要素は優先度順に取り出される 集合を扱うデータ型の例:キュー、スタック ヒープの種類 最小ヒープ(min heap) 根が常に最小となっているヒープ。親ノードは子ノードより常に小さい。 最大ヒープ(max heap) 根が常に最大の要素となっているヒープ。親ノードは子ノードより常に...

プログラミング

アルゴリズム データ構造 ヒープ

2019-12-04 22:30:37

アルゴリズムとデータ構造 - ハッシュテーブル

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ハッシュテーブル ハッシュ値を添え字とした配列 ハッシュの衝突処理 開番地法 衝突が生じた際に、ハッシュ関数とは別の関数を使って別の番地を求める方法。 連鎖法 衝突が生じても新しい番地を求めずに、衝突した番地に衝突したキー同士をポインタでつないだリンクリストを格納することで対応する方式。 計算時間データへのアクセス O(1) 添字を使ってランダムアクセスが可能。 データの追加 O(1) 配列の場合は、線形探...

プログラミング

アルゴリズム データ構造 ハッシュテーブル

2019-11-17 15:30:27

アルゴリズムとデータ構造 - キュー

概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 キュー 常に先に追加されたデータからしかアクセスできないようにデータを一列に並べた構造 スタックとは追加と削除の方向が逆になる。 FIFO(First In First Out) 先入れ先出し 待ち行列ともいう。 データの追加をenqueue、削除をdequeueという。 計算時間配列や連結リストなど実装形式による。 実装package main // Queue is a queue. type Queue st...

プログラミング

アルゴリズム データ構造 キュー