応用では整列・探索・区間処理・木・ハッシュを、上級では分割統治・ヒープ・最短経路を学びます。

応用 12

整列、探索、区間処理、木、ハッシュを学び、問題に応用します。

1. 整列アルゴリズム比較

   同じ配列を7種類のアルゴリズムで整列し、処理量・計算量・用途を比べます。

2. バブルソート

   隣接する値を比較・交換し、未確定の最大値を末尾へ移動させます。

3. 選択ソート

   残りの最小値を繰り返し選び、次の確定位置へ交換します。

4. 挿入ソート

   値を1つずつ取り出し、整列済みの接頭部分へ挿入します。

5. 計数ソート

   値同士を比較せず、出現回数から出力位置を計算します。

6. 二分探索

   整列済み配列の候補を半分ずつ絞り込み、値の検索、下限・上限探索、答えの二分探索を体験します。

7. 2ポインタ法

   2つのポインタを一方向に進め、一部の二乗時間の探索を線形走査に変えます。

8. スライディングウィンドウ

   連続区間に入る値と出る値だけを更新し、区間の情報を効率よく保ちます。

9. 累積和

   累積和を前計算し、区間和を1回の引き算で求めます。

10. 二分探索木

    値の挿入・検索・削除を試し、木の形が変わる様子と偏った木が遅くなる理由を確認します。

11. ハッシュテーブル

    キーをバケットに対応付け、衝突の処理方法を体験します。

12. 幅優先探索と深さ優先探索

    同じグラフをBFSとDFSでたどり、キューとスタックによる訪問順序の違いを確認します。

上級 4

分割統治、ヒープ、最短経路、複数のアルゴリズムの組み合わせを学びます。

1. クイックソート

   ピボットを基準に分割し、左右を再帰的に整列します。

2. マージソート

   配列を再帰的に分割し、整列済みの半分同士をマージする分割統治法です。

3. ヒープソート

   最大ヒープを作り、最大値を繰り返し末尾へ移動させます。

4. ダイクストラ法

   未確定の中で最も近いノードを確定し、隣接ノードへの距離を更新します。