PHP での挿入ソート アルゴリズムの実装手順

PHP での挿入ソート アルゴリズムの実装手順

挿入ソートは、順序付けられたシーケンスを構築することによって、並べ替えられていないデータを並べ替えられたシーケンスに 1 つずつ挿入し、順序付けされたシーケンスを取得する、シンプルで直感的な並べ替えアルゴリズムです。 PHP では、次の手順で挿入ソート アルゴリズムを実装できます。

ステップ 1: ソートする配列をパラメーターとして受け取る関数 insertSort を定義します。

function insertionSort($arr) {
  $n = count($arr);
  for ($i = 1; $i < $n; $i++) {
    $key = $arr[$i];
    $j = $i - 1;

    while ($j >= 0 && $arr[$j] > $key) {
      $arr[$j + 1] = $arr[$j];
      $j = $j - 1;
    }
    $arr[$j + 1] = $key;
  }

  return $arr;
}

ステップ 2: メイン プログラムで insertSort 関数を呼び出し、並べ替える配列を渡します。

$unsortedArray = [5, 2, 1, 7, 3];
$sortedArray = insertionSort($unsortedArray);

ステップ 3: ソートされた配列を出力するための for ループを定義します。

$n = count($sortedArray);
for ($i = 0; $i < $n; $i++) {
  echo $sortedArray[$i] . " ";
}

完全なコードは次のとおりです。

上記のコードは、挿入ソート アルゴリズムを実装しています。このアルゴリズムの中心となる考え方は、ソート対象の配列をソート済みと未ソートの 2 つの部分に分割し、未ソートの要素をソート済みの部分に 1 つずつ挿入することで順序付けされた結果を取得することです。コードでは、for ループを使用して、並べ替えられる配列を走査し、現在の要素を適切な位置に挿入します。内部の while ループは、適切な位置が見つかるまで、ソートされたセクションの要素を継続的に比較および移動するために使用されます。

挿入ソート アルゴリズムの時間計算量は O(n^2) です。ここで、n はソートされる配列の長さを表します。このアルゴリズムには隣接する要素の比較と移動操作のみが含まれるため、空間複雑度は O(1) であり、インプレース ソート アルゴリズムです。

要約: 上記の手順により、PHP に挿入ソート アルゴリズムを実装することができました。このアルゴリズムはシンプルかつ効果的で、小規模データの並べ替えに適しています。実際のアプリケーションでは、ソートされる配列がより大きい場合、またはより高いパフォーマンスが必要な場合は、他のより高速なソート アルゴリズムを検討できます。

以上がPHP での挿入ソート アルゴリズムの実装手順の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。