未整列の部分を部分木で表し、そこから最大値又は最小値を取り出して既整列の部分に移す。この操作を繰り返して、未整列部分を縮めてゆく方法。
はじめに ヒープソート クイックソート マージソート おわりに 参考 はじめに こんにちは。talosです。前回に引き続きソートのアルゴリズムを説明します。後編では、「ヒープソート」、「クイックソート」、「マージソート」を説明します。前編はこちら talosta.hatenablog.com ヒープソート ヒープというデータ構造を用いてソートする方法です。ヒープとは、常に親ノードの要素より子ノードの要素のほうが小さいか等しい状態を保つ木構造のことです。つまり、根ノードには常に最大値が格納されるので、根ノードの取り出しを繰り返せばソートできます。ヒープの整形 ヒープから取り出し ヒープソートの平…
01/23(月) 午後3時少し前に起床。すぐ集中講義のZoomに接続した。 今週1週間参加する講義の名前は「応用数理総論」で、これだけだと何のことかわからないが内容は数理論理学である。実は同じ講義が学部生向けとしても開講されていて、自分は去年それの単位を取得した。だから知っている内容だろうし単位も楽に取れそうという見込み、純粋に理解を深めたいという気持ち、さらに今期の専門科目で他に興味のある科目がなかったため、以上3要素により受講を決めた。 初回の今日は基礎の確認で、命題論理、1階論理、再帰的関数、不完全性定理などが予定されていた。実際は3時間に収まらず、不完全性定理は次回に回された。内容的に…
代表的なアルゴリズムをGoを使って学習していた時に、自身のメモとして記述していた内容を改良して記事にしてみました。 Pythonなどで書いている記事はそれなりにあると思いますが、Goで書いている記事は少ない印象でしたので誰かの参考になれば幸いです！！ linear search(リニアサーチ） 線型探索は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。 n個のデータからm個のデータを検索する場合、時間計算量はO(nm)、空間計算量はO(1)である。 func linearSearch(nums []int…
こんにちは。谷口です。プログラミングを勉強中の方に、「入門レベルの内容は終わったけど、次は何を勉強すればいいの？」と聞かれることがあります。もちろん、作りたいものややりたいことが決まっている人はそのための勉強をすればよいのですが、特に思い当たらない、次はどこに進めばよいかわからいという方もいるでしょう。そこで今回は、paizaラーニングで入門編が終わったあとや、すでに入門レベルの勉強は終えている人が、次にどんな内容を学ぶとよいかについてご紹介します。プログラミング初心者の方、入門レベルの勉強を終えた方、エンジニアを目指している方の参考になればと思います。 Webアプリ開発入門編 プログラミング…
この記事は呉高専アドベントカレンダー2022に11月30日まで空きがあったら適当に埋めるための記事です。→ 4日目の記事になりました / 空きがないので放流します。 ごあいさつ はじめに 既存の有名ソートアルゴリズムたち バブルソート 選択ソート クイックソート マージソート 変なソートを作ろう 平方分割バブルソート 追記 最長増減部分列分割ソート 最長増加部分列 実験 ソースコード おわりに ごあいさつ こんにちは、点Nです。電気情報工学科卒です。高専在学中は高専プロコンに出たり、呉高専史上初めてICPC（大学対抗競プロ合戦）に参加して予選敗退したりといった感じです。 こちらは11日の記事の…
プログラミングの世界には、いろいろなソートアルゴリズムがある。バブルソート、選択ソート、挿入ソート、マージソート、ヒープソートなどである。 それぞれのコードの書き方の具体例はインターネット上にあふれているので、知りたいときは検索すれば済む。しかし、コードを示されて具体的に説明されてもいまいち理解できないという場合も多いだろう。 そこで、今回は挿入ソートについて理解するために、抽象的な観点から説明してみたい。 挿入ソートの基本的な流れは次の通りだ。 配列がソート済みの部分と未ソートの部分に分けられていると考え、未ソート部分の要素をソート済み部分の適切な位置に挿入していく。 おそらく実際のコードで…
はじめに 本稿は、確率単体へ射影するアルゴリズムを調査した内容をまとめたものになります。この記事を書くきっかけは、知り合いから共有された(Wang, 2013)がシンプルでわかりやすく、他の手法にも興味が出てきたことです。調べていく中で、各アルゴリズムの計算速度も気になったので、簡易な性能比較も行いました。 確率単体への射影 問題設定 確率単体への射影（以下、本問題）は以下に示す凸最適化問題です。 但し、とします。確率単体は上記の制約条件を満たす領域を指します。 最適解の導出方法 本問題の最適解はとなります。このをどのように求めるかがポイントとなっており、さまざまなアプローチがあります。 ラグ…
今回はアルゴリズムに関しての学習と、やってみて感じたことをまとめた。 基本情報処理技術者のアルゴリズム アルゴリズムにどのようなものがあるかは、ざっと基本情報処理技術者試験の内容を見ておくと良い。 基本情報処理技術者試験については内容をわかりやすくまとめてくださっている方がいるので参考になる。アルゴリズム以外の動画も公開されているので、その他の動画も見させていただいている。 無料で基本情報の範囲をざっと確認することができ、感謝です。 【午後_アルゴリズム】01. アルゴリズム問題の対策| 基本情報技術者試験 手元にあったキタミ式の書籍（平成30年度のやつだけど）も大体同じようなトピックが解説さ…
バブルソートとは ソートアルゴリズムの中の一つのアルゴリズム。バブルソートは、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。 アルゴリズムが単純で実装も容易である一方、最悪時間計算量は O(n2) と遅いため、一般にはマージソートやヒープソートなど、より最悪時間計算量の小さな（従って高速な）方法が利用される。 pythonを使ったサンプルコード def bubble_sort(data): for i in range(1, len(data)): for j in range(0, len(data)-i): if data[j] > data[j+1]: data[j], …
09/26(月) 午後4時半起床。インターン先定例会が始まっている。布団から飛び起きて会議に接続した。 今週の進捗、というか稼働状況は、勉強会スライドを作っただけ。先週やると言ったことに全く手を付けられていない……。今週こそ頑張りますと言って終了。勉強会は自分の番。質疑応答含め1時間半ほどの発表で、午後7時前に終了した。その後スライドを公開した。 勉強会0926.pdf - Google ドライブ 今日のテーマは文字列の列のソート。長さの総和にだけ制約がついているような文字列たちを辞書順でソートするとき、どういう計算量になるのか調べた。よくあるシチュエーションだが、初めて出会ったとき本当に間に…
秋にIPAの某試験を受けようと思っているが、合格したはずの応用情報の内容は遠い昔で、すっかり忘れてしまった。更なる言い訳としては、みっちり週5で本業と、週末は2件の副業に関わらさせていただいているため(ありがたいことです)、買ったテキストもろくに読めていない状況となり合格する可能性はほぼゼロといえる。とはいえ受験料を払った以上、モッタイナイ精神を司るゴーストが囁いてくる…隙間時間で勉強しろ、と…。 とりあえず個人的に掲げているブログノルマと勉強不足問題を一挙に解決すべく、覚えていなかった・もしくは覚えが曖昧だった単語をメモしていく。しばらくはこういう記事でお茶を濁すかもしれない…。まぁ自分のブ…
エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(po3rin) です。検索とGoが好きです。 最近、Go1.19でsortパッケージのアルゴリズムが一部変更されました。 Pattern-defeating Quicksortが入った時のdiff 1.19リリースノートではPattern-defeating Quicksortが採用されたと紹介があります。実際にsort/zsortfunc.go、sort/zsortinterface.goにそれぞれpdqsort_func、pdqsortという関数があります。 // pdqsort sorts d…
データ構造はコンピュータサイエンスとソフトウェアエンジニアリングの分野全体で幅広く多様な用途があります。 プログラマにとって、アルゴリズムとデータ構造は最も重要なテーマです。 プログラミングの分野に足を踏み入れたい場合は、最も一般的なデータ構造を習得し、需要の高いスキルであなたの履歴書を強化する必要があります。 本日はデータ構造とアルゴリズムを解説いたします。 データ構造とアルゴリズム データ構造とは？ 8つのデータ構造 アルゴリズムとは？ 覚えておくべきアルゴリズム 検索アルゴリズム 二乗によるべき乗 ソートアルゴリズム ハッシング 文字列の照合と解析 動的計画法(DP) アルゴリズムは何に…
ズッキーニが安かったので、焼いてゆで卵とともにカレーにぶっ乗せて頂く。しれっと交じってる細長いのはズッキーニじゃなくてカボチャ。 みずみずしいズッキーニ、これがまあスパイシーなジャワカレーと合うこと合うこと…。カレーは塩分があるので、乗せられたメンツは味つけなし。美味しくいただきました。 7/14の晩は睡眠6.5h、勉強2h。コーヒーに頼ったが日中の眠気もなく、ひたすらアルゴリズムのトレース＆コーディング。さすがにヒープソートとかクイックソート辺りまでくると、再帰関数を使ってる関係で手書きのトレースは骨が折れる。 明日はPaizaでＳＱＬ、マージソートのトレースとコーディングの予定。
2023年度 大阪府立大学(大阪公立大学) 工学域 電気電子系学類 情報工学過程の3年次編入学試験に合格しました。 今年で大阪府立大学としての編入試験実施は終了しますが、大阪公立大学として工学部の編入試験が行われると想定されるため、誰かの役に立つと信じて書いていきます。 プロフィール 志望動機 試験の傾向 試験内容 専門科目 論理演算工学 データ構造とアルゴリズム 数学 面接 試験までの流れ 前日 当日 2023年度の試験内容 論理演算工学 データ構造とアルゴリズム 大問1 大問2 数学 線形代数 微分方程式 複素関数論 英語 面接 試験を終えて アドバイス 最後に プロフィール twitte…
Python の標準モジュールで用意されている queue 関連のライブラリについて確認します。 環境 Python 3.9.13 queue 関連のライブラリ 以下があります。 種類 queue モジュール その他モジュール キュー queue.Queue collections.deque スタック queue.LifoQueue collections.deque 優先度付きキュー queue.PriorityQueue heapq queue.Queue/queue.LifoQueue vs collections.deque queue.Queue および queue.LifoQuo…
codezine.jp
ja.wikipedia.org
www.th.cs.meiji.ac.jp
su10.sgu.ac.jp
www.ics.kagoshima-u.ac.jp
