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

2022年8月18日

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

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

問題文

選択ソート (昇順) は、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」の最小値を取り出し、「整列済み配列」の末尾に付け加えることを繰り返す手法です。「未整列な配列」の要素数が 1 になるまで処理を繰り返すと、1つの「整列済み配列」が得られます。

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

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

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

解答例

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

<?php

$n = trim(fgets(STDIN));

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

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

$min_index = $i;

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

if ($a[$j] < $a[$min_index]) {

$min_index = $j;

}

$buf = $a[$i];

$a[$i] = $a[$min_index];

$a[$min_index] = $buf;

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

}

解答例

カテゴリー