2020-08-01から1ヶ月間の記事一覧
はじめに 今回扱ってみる問題はこんな感じ。 n個の配列Aと整数kが入力として与えられたとき,Aの2つの要素の和がkとなる組み合わせを列挙せよ 例. 入力:A = {1, 6, 4, 5, 3},k = 7 出力:(6, 1), (3, 4) 解き方 まずは2重ループを使った全探索の方法が思い…
はじめに 今回は2分探索木を実装してみようと思います。ja.wikipedia.org早速みていきましょう。 二分探索木 二分探索木は「左の子の値 ≤ 親の値 ≤ 右の子の値」という制約を持つ二分木のことを指します。 今回は以下の4つを実装します。 挿入 削除 要素を見…
はじめに 今回は今までの記事とは少し違い、論文紹介をしたいと思います。読まさせていただいた論文はこちら。kyushu-u.pure.elsevier.com http://www.ifaamas.org/Proceedings/aamas2019/pdfs/p1413.pdfテーマは選挙の区分けをグラフ理論の視点からみるとい…
はじめに 今回は選択ソートを実装していきたいと思います。 ja.wikipedia.orgこのアルゴリズムは実装は簡単だけど性能がいいといったソートアルゴリズムで、バブルソートと似た系統のものです。早速みていきましょう。 はじめに 選択ソート 実装 テスト 考察…
はじめに 今回はマージソートを実装してみようという記事になります! ja.wikipedia.org前置きはなしに本題をみていきたいと思います。 はじめに マージソート 実装 使い方 考察 マージソート 英語ですが、この動画がすごく分かりやすく説明されていたのでオ…
はじめに 少し前に挿入ソートを実装してみました。 https://www.hanachiru-blog.com/entry/2020/07/30/180000www.hanachiru-blog.comこの挿入ソートをより高速化するために生まれたのが今回紹介するシェルソートになります。 ja.wikipedia.org早速みていきま…
はじめに 今回はヒープソートを実装してみようという記事になります!ヒープソートというのは名前の通りヒープというデータ構造を用いたソートアルゴリズムであり,安定して高速に処理ができる(安定ソートという意味ではない)優秀なソートだと知られています…
はじめに 前回はバケットソートを紹介しましたが、今回はその改良版とも言われる基数ソートについて実装していきたいと思います。 ja.wikipedia.orgバケットソートではバケットの数が膨大になってしまうのはNGという制約がありました。計算量と引き換えにそ…
はじめに 前回は挿入ソートを紹介しましたが、今回はバケットソートを実装していきたいと思います。バケットソートはソートアルゴリズムでよくある要素を交換する手法を取らない面白いアルゴリズムです。 ja.wikipedia.orgまた以下の制約を満たさなければ動…