タグ: プログラミング学習

代表的なソートアルゴリズム

ChatGPTに教えて貰いました。備忘録として。

代表的なソートアルゴリズム

  1. バブルソート（Bubble Sort）:
    隣接する要素を比較して順序が逆なら交換することを繰り返す。
    比較回数がO(n^2)、入れ替え回数がO(n^2)となるため、効率は良くない。

    2. PHPでバブルソートを実装する

  2. 選択ソート（Selection Sort）:
    未ソート部分から最小（または最大）の要素を選び、先頭の要素と交換することを繰り返す。
    比較回数がO(n^2)、入れ替え回数がO(n)となるため、効率はあまり良くない。

    3. PHPで選択ソートを実装する

  3. 挿入ソート（Insertion Sort）:
    ソート済みの部分に要素を適切な位置に挿入することを繰り返す。
    ほぼ整列している場合に効率的で、比較回数がO(n^2)、入れ替え回数がO(n)となる。
  4. クイックソート（Quick Sort）:
    ピボット要素を選び、ピボットより小さい要素と大きい要素に分割し、それぞれ再帰的にソートする。
    平均的な場合において、比較回数がO(n log n)と非常に効率的。
  5. マージソート（Merge Sort）:
    分割統治法を用いてリストを分割し、それらをマージしながらソートする。
    比較回数がO(n log n)と非常に効率的で、安定している。
  6. ヒープソート（Heap Sort）:
    ヒープ構造を使ってソートする。
    比較回数がO(n log n)と効率的で、一定の追加メモリが必要。
  7. シェルソート（Shell Sort）:
    間隔を設定して部分的にソートを行い、徐々に間隔を縮めていく方法。
    比較回数がO(n log n)からO(n^2)となり、データのパターンによって効率が変わる。

これらのソートアルゴリズムはそれぞれ特徴と効率性が異なるため、ソート対象のデータの特性によって適切なアルゴリズムを選択することが重要です。

PHPで6×6の二次元配列を指定したブロックサイズ毎に合計し出力する

二次元配列の処理に手間取ったので練習として作成したコード。$div_numという変数でブロックサイズを指定し6ｘ6の二次元配列を指定したブロックサイズ毎に合計して結果を出力します。

$div_numで割り切れない場合はエラーになるのでtry-catchで例外処理にしています。

15行目以降の$i += $div_numと$j += $div_numがポイントで行と列の処理のインクリメントが$div_numずつ増えていくことで指定したブロックサイズ毎の処理を実現しています。

PHPでハノイの塔を解く

再帰的アルゴリズムの練習のためにPHPでハノイの塔を解いてみました。正直、再帰的アルゴリズムについては、まだ頭が混乱するので、ちょっと数をこなす必要があるなと感じています。

ハノイの塔についての概要

ハノイの塔（Tower of Hanoi）は、数学的なパズルや再帰的アルゴリズムの代表的な例として知られています。

ゲームの目的

ゲームの目的は、3本の棒といくつかの円盤があるとき、最初に一つの棒に積まれた円盤を他の棒に移動させることです。

ルール

  • 全ての円盤は、大きさによって異なる直径を持っています。
  • 3本の棒のうち、一つの棒に円盤を積み重ねて配置します。これを「出発棒」と呼びます。
  • 他の2本の棒を「中間棒」と「目標棒」として使います。
  • 全ての円盤は「出発棒」に積まれた状態から、「目標棒」に積み重ねることを目指します。
  • 円盤を一度に1枚だけ移動できます。
  • 小さい円盤の上に大きい円盤を積み重ねることはできません。
  • 再帰的に円盤を移動することにより、最小の手順で目標棒に円盤を移動させることが可能です。

再帰的アルゴリズム

ハノイの塔は再帰的アルゴリズムを用いて解くことが一般的です。再帰的アルゴリズムは、大きな問題をより小さな問題に分割して解決する方法です。ハノイの塔では、最も大きな円盤を目標棒に移動させるために、残りの円盤を中間棒に移動させる必要があります。このように、大きな問題を小さな問題に分割して解決する再帰的な手法を使うことで、効率的に円盤を移動させることができます。

教育的な側面

ハノイの塔は再帰やスタックなどの基本的なアルゴリズムとデータ構造を理解するのに役立つ教育的な側面を持っています。また、複雑なアルゴリズムや再帰的なアプローチを学ぶ上での良い練習問題としても利用されます。

PHPでバブルソートを実装する

ソートアルゴリズムへの理解を深めるためにPHPでバブルソートを実装してみました。

バブルソートの概念

バブルソート（Bubble Sort）は、隣接する2つの要素を比較し、必要に応じて交換を行いながら要素を適切な位置にソートしていくアルゴリズムです。

動作の概要

  1. 比較と交換のループを開始
  2. 配列の先頭から隣接する要素を順番に比較
  3. 現在の要素が次の要素より大きければ、両方の要素を交換
  4. 操作を配列の最後まで続ける
  5. 最大値が末尾に移動し、末尾に確定
  6. 次のループを開始し、末尾の要素を除いて同じ操作を行う
  7. ループを配列の要素数-1回繰り返す

特徴

  • シンプルで実装が容易
  • 効率的なソートアルゴリズムと比べて遅い（O(n^2)の計算量）
  • 小規模なデータに対しては利用されることがある
  • 大規模なデータセットには向いていない

Close