アルゴリズムの概要-ソートの選択

ソートの選択

function select_2($_array)
{
    for($i=0;$i<count($_array)-1;$i++)
    {   
        $key = $i; 
        for($j=$i+1;$j<count($_array);$j++)
        {
            if ($_array[$j]<$_array[$key])
            {
                $key = $j; 
            }
        }
        $tmp = $_array[$key];
        $_array[$key] = $_array[$i];
        $_array[$i] = $tmp;
    }   
    return $_array;
}

//27 
$start = time();
print_r(select_2(rand_array(10000)));
$end = time();
echo "            " . ($end - $start) . " ;";

比較回数O(n^2)、総比較回数N=(n-1)+(n-2)+...+1=n*(n-1)/2.交換回数O(n)、最良の場合は、すでに秩序化され、0回交換されている.最悪の場合,逆シーケンス,交換3(n−1)回である.交換回数はバブルソートよりも少なく,交換に必要なCPU時間は比較に必要なCPU時間よりも多く,n値が小さいため,選択ソートはバブルソートよりも速い.