ヒープソート

はじめに ヒープソート クイックソート マージソート おわりに 参考 はじめに こんにちは。talosです。前回に引き続きソートのアルゴリズムを説明します。後編では、「ヒープソート」、「クイックソート」、「マージソート」を説明します。前編はこちら talosta.hatenablog.com ヒープソート ヒープというデータ構造を用いてソートする方法です。ヒープとは、常に親ノードの要素より子ノードの要素のほうが小さいか等しい状態を保つ木構造のことです。つまり、根ノードには常に最大値が格納されるので、根ノードの取り出しを繰り返せばソートできます。ヒープの整形 ヒープから取り出し ヒープソートの平…

はじめに 今月はReact（+α）スキルの向上と応用情報技術者試験の対策をしていました。 実務でReactを使うことになり、改めて自分のフロントエンドスキルを見直して実装力を高めているところです。 去年の８月にポートフォリオを作成した以来ですが、「今改めて見ると、まだまだ改善点が多いなあ」と感じます。 そこは現時点での成長と受け止め、ひとまずは実装力を上げていこうと思います。 応用情報技術者試験は午後問題の演習に時間がかかっています。 オンライン講座 Udemy React & TypeScript - The Practical Guide ReactをTypeScriptで書くのが、あまり…

バブルソート -- 最小値を先頭に bubble [x] = [x] -- 要素1個ならそのまま bubble (x:xs) | x < y = x:y:ys -- 1個目が2個目以降の最小値より小さければ入れ替えなし | otherwise = y:x:ys -- そうでなければ1個目と2個目以降の最小値を入れ替える where (y:ys) = bubble xs -- 2個目以降の最小値を先頭に -- バブルソート bsort [x] = [x] -- 要素1個ならそのまま bsort xs = y : bsort ys -- 最小値を先頭に、残りをさらにバブルソート where (y:…

Programmers use dynamic memory allocators (such as malloc) to acquire VM at run time. For data structures whose size is only known at runtime. Dynamicmemory allocators manage an area of process virtual memory known as theheap. サイズがコード実行時に初めてわかるデータ構造の場合、VM,(Virtual Machine/仮想マシン）をrun timeで取得するために、プログ…

探索、整列アルゴリズム 探索 線形探索 リストや配列の先頭から順に要素を比較し、目標の要素を見つけるまで判定していく探索アルゴリズム 整列されていないものに対しても整列できるが、あまり効率的ではない。 計算量 : O(n) 二分探索 リストが昇順または降順で整列されていることが前提とされる探索アルゴリズム 目的の値が探索するリストの中央の値より大きいか小さいかを判断して次の探索範囲を絞りこみ、それを繰り返す。 計算量 : O(log n) 整列、ソート バブルソート 隣接する要素を比較し、順番が逆であれば交換するという操作を繰り返す。 計算量 : O(n²) 選択ソート データ列を未整列と整列…

あるデータ列を整列したら状態0から順に状態1，2，・・・，Nへと推移した。整列に使ったアルゴリズムはどれか。 状態0 3，5，9，6，1，2 状態1 3，5，6，1，2，9 状態2 3，5，1，2，6，9 ・ ・ 状態N 1，2，3，5，6，9 隣り合う数を交換し、 最大値（または最小値）が決定していく。 今回は最大値が9.6..と決まる。 ア クイックソート イ 挿入ソート ウ バブルソート エ ヒープソート 正解はウです

前回 Visual Studio Preview の既知の問題で時間を溶かしてあまり詳しく挙動を確認できなかったので、再度どれくらいいい感じにリネームしてくれるか確認してみました。 hiro128.hatenablog.jp well-known なアルゴリズム well-known なアルゴリズムのネーミングを不親切なものにして、Copilot が適切な名前にリネームできるか試してみました リストの逆順並び替え これは本来 list.Reverse(); で1発ですが、あえてロジックを手書きして確認しました。 public static List<string> aaa01(List<str…

免責 この解答・解説は当ブログ管理人のものであり、間違っている可能性もあります。 この記事の記載内容によって生じた損失や損害については、当ブログ管理人は一切責任を負いません。 が、間違っている箇所や、よりよい解法があれば後から見に来た人のためにもコメント欄に残していってもらえると、幸いです。 あと、解説でこれが解ければ院試は受かる、的なことを言っていますが、一回しか院試を受けたことがない管理人の所感なので真剣にはあてになさらず。 でももちろん、管理人が実際にそう感じたことを書いています。 問題 東大院工学系電気系工学専攻2020年問題4 解答 ※昔から電子工作を趣味としている管理人は、問題4の…

世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎- 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎-」内容紹介 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎-」目次 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻-基礎・ソートと順序統計量・データ構造・数学的基礎-」Amazonでの購入はこちら 「世界標準MIT教科書 アルゴリズムイントロダクション第4版 第1巻…

さて基本情報科目B計画2日目、Excersize4-1～Excersize4-6として、配列をソートするプログラムのトレースの練習をひと通り終えました。 結論としては、下記7種類ほどのソートプログラムの型（形）を暗記し、データがどう動けば正しくプログラムが実行されるかを試験会場でイメージできるまで、何度もトレースの練習をする必要がある感じです。 ・選択ソート ・バブルソート ・マージソート ・挿入ソート ・シェルソート ・クイックソート ・ヒープソート なお3日目Excersize4-7～Excersize4-11は、主にサーチ関数からの出題となります。12月最初の土日で、3日目について投稿し…

公式ビジュアライザ（seed = 5） AHC025で優勝しました。長期AHCの過去最高順位は10位だったということもあり、非常に嬉しく思います。 順位表 はじめに 解法だけでなく、考察や余談についても記載しました。 重要度が低いと思われるものは折りたたみにしました。必要に応じてクリック（タップ）してください。 ベイズ推定やMCMCについては私自身が詳しくないため、コンテスト後に少し勉強して理解したことを書きました。「お気持ち」だけ汲み取っていただければ幸いです。 アイテム集合 に対して、それらの重さ（の推定値）の和を と表記しました。行儀が悪い表現ですがお許しください。 環境によっては数式が…

目次 目次 概要 バブルソート バブルソートとは 具体的な手順 サンプルコード 選択ソート 選択ソートとは 具体的な手順 サンプルコード 挿入ソート 挿入ソートとは 具体的な手順 サンプルコード クイックソート クイックソートとは 具体的な手順 サンプルコード マージソート マージソートとは 具体的な手順 サンプルコード ヒープソート ヒープソートとは 具体的な手順 サンプルコード 終わり 参考記事 概要 ソートについて学んだので、まとめます。 今回は以下の基本的な3つのソート バブルソート 選択ソート 挿入ソート と応用的な3つのソート クイックソート マージソート ヒープソート をまとめま…