選択ソート

概要

社内のcrowiに貼っていた記事をせっかくなのでこちらに移動しました。

1年半前くらいにアルゴリズムの勉強をしていたときの名残りです。
「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を参考に図を作成してプログラムを書きましたが、正直、「参考」に貼ったアプリケーションのほうが分かりやすいです。

選択ソート

A[N]	N個の整数でできた配列
i	未ソートの部分の先頭を示すループ変数で、配列の先頭から末尾に向かって移動する
minj	各ループの処理でi番目からN-1番目までの要素のうち、最小値の位置
j	未ソートの部分から最小値の位置(minj)を探すためのループ変数

未ソート部分から最小値の位置を探し、その位置の要素と未ソート部分の先頭の要素を交換する。
交換されて先頭にきたものはソート済みとする。
これを繰り返し、配列の先頭から小さい順に決定される。

選択ソートは離れた要素を交換するため安定なソートではない？(ここがちょっとわからない)

計算量

未ソート部分の最小値を見つけるため、各ループでN-1回、N-2回、N-3、…、1回の比較が行われる。
よって、常に(N^2 - N) / 2 回の比較が行われる。
N^2に比べてNは十分小さいので無視することができ、定数である1/2も無視することができるので、選択ソートはN^2に比例するといえる。

問題

入力は、1行目に数列の長さを表す整数N、2行目にN個の整数が空白区切りで与えられる。
出力は、1行目に整列された数列の要素を空白区切り、2行目に交換回数を出力する。

入力値

6
5 6 4 2 1 3

プログラム

<?php
$arrayCount = trim(fgets(STDIN));
$array = explode(' ', trim(fgets(STDIN)));

list($sortedArray, $sortedCount) = selectSort($arrayCount, $array);

foreach ($sortedArray as $value) {
    echo $value.' ';
}
echo PHP_EOL, $sortedCount, PHP_EOL;

function selectSort($arrayCount, $array)
{
    $sortedCount = 0;
    for ($i = 0; $i < $arrayCount; $i++) {
        $minj = $i;
        for ($j = $i; $j < $arrayCount; $j++) {
            if ($array[$j] < $array[$minj]) {
                $minj = $j;
            }
        }

        $temporary = $array[$i];
        $array[$i] = $array[$minj];
        $array[$minj] = $temporary;
        if ($minj !== $i) {
            $sortedCount++;
        }
    }

    return [$array, $sortedCount];
}

出力結果

1 2 3 4 5 6 
4

参考

• 書籍 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
• 私には難しすぎる・・・。
• iOSアプリ アルゴリズム図鑑
  • 動くイメージで解説してくれるので分かりやすい。