【素朴なソートアルゴリズムメニュー】挿入ソート (paizaランク B)-解答例-PHP編

2022年8月18日

【素朴なソートアルゴリズムメニュー】> FINAL問題挿入ソート (paizaランク B 相当) [難易度: 1629 ±15]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

挿入ソートは、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入することを繰り返す手法です。「未整列な配列」が空になるまで処理を繰り返すと、1つの「整列済み配列」が得られます。この手法は、手持ちのトランプを並び替える際などによく用いられる、自然で比較的直感的なものです。

では、要素数 n の数列を昇順にソートする挿入ソートのプログラムを作成してください。上の疑似コードに従って実装してください。アルゴリズムが正しく実装されていることを確認するために、各 i についてその処理が終わった時点での配列を出力してください。

入力値（例）
5
4 1 3 5 2

出力値（例）
1 4 3 5 2
1 3 4 5 2
1 3 4 5 2
1 2 3 4 5

解答例

<?php
    $n = trim(fgets(STDIN));
    $a = explode(" ", trim(fgets(STDIN)));
    
    for ($i = 1; $i <= $n-1; $i++) {
        $x = $a[$i];
        $j = $i-1;
        
        while ($j >= 0 and $a[$j] > $x) {
            $a[$j+1] = $a[$j];
            $j--;
        }
        
        $a[$j+1] = $x;
        
        echo implode(" ", $a). "\n";
    }
?>

<?php

$n = trim(fgets(STDIN));

$a = explode(" ", trim(fgets(STDIN)));

for ($i = 1; $i <= $n-1; $i++) {

$x = $a[$i];

$j = $i-1;

while ($j >= 0 and $a[$j] > $x) {

$a[$j+1] = $a[$j];

$j--;

}

$a[$j+1] = $x;

echo implode(" ", $a). "\n";

}

解答例

カテゴリー