基本選択法

基本選択法

 

前回紹介したバブルソート（Bubble Sort）は、隣接する２つの大小を比較し、順序が逆転していたならば、２つの要素を交換することのよって、データを並び替える方法であった。

そして、データの数がn個であった場合、比較回数が

　　

回であり、データの交換回数が最悪

　　

回になり、並び替えの効率が悪い方法であるという話をした。

 

隣接する２つの要素の大小関係を比較し、順序が逆転していたら交換することによって何をしているのかといえば、昇順ならば要素の最大の値のものを、降順ならば要素の値が最小のものを、その最後尾に配置してるのである。であるならば、昇順ならば要素の最大値を、降順ならば最小値を要素の中から選び出し、それを最後尾に配置すればよいということになるであろう。

 

たとえば、

　　{4,2,5,1,3}

であれば、5が最大値なので、

　　{4,2,5,1,3}→{4,2,3,1,5}

と並び替える。

５は最後尾に配置したので、次に、５を取り除いた

　　{4,2,3,1}

の最大値４を最後尾に配置する。

　　{4,2,3,1}→{1,2,3,4}

これで並び替えが終了。

 

{4,2,5,1,3}の場合、

　バブルソート：６回

　基本選択法：２回

と、データの交換回数を減らすことができる。

 

の場合、この方法のアルゴリズムは次のようなものになるであろう。

 

do i=n,n−1,・・・,2,1

　i_max=1

　do j=2,3,・・・,i

　　a(j)>a(i_max)ならばjをi_maxにする

　end do j

　a(i_max)とa(i)を交換

end do I

 

このFortranプログラムは次のようになる。

 

parameter(n=5)
integer a(n)
integer dummy

a(1)=4; a(2)=2; a(3)=5; a(4)=1; a(5)=3

do i=n, 2, -1
    i_max=1
    do j=2,i
        if(a(j).gt.a(i_max)) then
            i_max=j
        end if
    end do
    ! データの交換
     dummy=a(i) !データの退避
     a(i)=a(i_max)
     a(i_max)=dummy
end do

write(*,*) a

end

 

i_max=iのとき、交換をする必要がないので、次のように変更すると、さらに速くなる。

 

parameter(n=5)
integer a(n)
integer dummy

a(1)=4; a(2)=2; a(3)=5; a(4)=1; a(5)=3

do i=n, 2, -1
    i_max=1
    do j=2,i
        if(a(j).gt.a(i_max)) then
            i_max=j
        end if
    end do
    ! データの交換
    if(i_max.ne.i) then
        dummy=a(i) !データの退避
        a(i)=a(i_max)
        a(i_max)=dummy
    end if
end do

write(*,*) icount
write(*,*) a

end

データを昇順、降順に並び替えるという作業は、結構、奥が深いんだケロ。

そして、現在、最速とされるクイックソートよりも速い並べ替え法を発見すると、歴史に名を残すことができる。のみならず、特許をとれれば、巨万の富を稼げるかもしれない。

 

次回は、さらに速い挿入法を紹介する。