夕蛙のなく頃に

データアナリストとして学んだことや趣味で勉強し始めたIoTをアウトプットする

OpenDataStructures第11章を自分用にまとめる(ソート)

なにこれ 前回の続き blog.frogdusk.com 今回扱うのはソートです。 代表的なソートとして、マージソートとクイックソートをまとめます。 マージソート クイックソート マージソート 「配列を半分に分割、分割された配列毎にソートして、合わせるときに先頭の…

『数学ガール/乱択アルゴリズム』を読んだ

読もうと思ったきっかけ 以下のブログで、「基礎」の次の「読み物」として挙げられていました。 nowokay.hatenablog.com 基礎として『OpenDataStructures』を勉強したので、流れに従って読んでみようと思った次第です。 数学ガール/乱択アルゴリズム (数学ガ…

OpenDataStructures第10章を自分用にまとめる(ヒープ)

なにこれ 前回の続き blog.frogdusk.com 今回は話がガラッと変わって、優先度付きキューの実装の話です。 特殊な二分木であるヒープを使います。 ヒープとは「雑多に積まれたもの」という意味があり、今までの「高度に構造化されて積み上げられたもの」であ…

OpenDataStructures第9章を自分用にまとめる(赤黒木)

なにこれ 前回の続き blog.frogdusk.com 本の中で特に重要だと言われている項目のみまとめるため、6章から9章に飛んでいます。 BinarySearchTreeの問題点は、要素の追加の仕方によって木の構造がアンバランスになることです。(例えば[1,2,3,4,5]のように追…

OpenDataStructures第6章を自分用にまとめる(二分木)

なにこれ BinaryTree 深さ優先探索 幅優先探索 BinarySearchTree なにこれ 前回の続き。 blog.frogdusk.com 二分木を扱います。今までデータ構造としてリストと違う概念として捉えていましたが、 ポインタという概念を使った連結リストを勉強した後だと、実…

OpenDataStructures第5章を自分用にまとめる(ハッシュテーブル)

なにこれ ChainedHashTable 乗算ハッシュ法 LinearHashTable なにこれ 前回の続き blog.frogdusk.com ハッシュテーブルを用いてUSetインターフェースを実装します。 USetインターフェースは順序付けられていない値の集合です。 Setインターフェースで重要な…

OpenDataStructures第4章を自分用にまとめる(スキップリスト)

なにこれ SSetインターフェース スキップリスト 高さを決めるランダム性 SkiplistSSet SkiplistList なにこれ 前回の続き。 blog.frogdusk.com 今回はスキップリストを用いて、SSetインターフェースとListインターフェースを実装します。 SSetインターフェー…