挿入法 [数値解析]
挿入法
基本選択法よりも、さらに、効率のよい整列法である挿入法について、{4,2,5,1,3}を例に説明する。
まず、{4,2,5,1,3}の部分列（部分集合）である{4,2}に注目し、最後尾の要素2の挿入箇所を探し、そこに２を挿入すると
{4,2}→{2,4}
になり、{4,2}の並び替えが終了する。
次に、{2,4,5}の最後尾の５の挿入箇所を探し、そこに１を挿入する。すると、次のようになる。
{2,4,5}→{2,4,5}
同様に、
{2,4,5,1}→{1,2,4,5}
最後に、最後尾の３の挿入箇所を探し、そこに３を挿入すると、
{1,2,4,5,3}→{1,2,3,4,5}
と、{4,2,5,1,3}を昇順に整列することができる。
一般に、
の場合、
i=2,3,・・・,nに対して、
部分列
における
の挿入箇所を探索し、そこにを挿入することによって、整列することができる。
この手順を、アルゴリズム的に書くと次のようになる。
do i=2, 3, ・・・, n
do j=i, i−1, ・・・, 2
a(j−1)>a(j)ならば、a(j−1)とa(j)を交換
end do j
end do i
この方針に基づいてプログラムを書くと、次のようになる。
parameter(n=5)
integer a(n)
integer w
a(1)=4; a(2)=2; a(3)=5 ; a(4)=1; a(5)=3
do i=2,n
do j=i,2,-1
if(a(j-1).gt.a(j)) then ! a(j-1)とa(j)の比較
w=a(j); a(j)=a(j-1); a(j-1)=w ! a(j-1)とa(j)の交換
end if
end do
end do
write(*,*) a
end
このプログラムで昇順にデータを整列できるのですが、たとえば、
{2,4,5}
のように整列の必要のない部分列に関しては、整列の処理を省くことができるので、次のようにプログラムを改良することできる。
parameter(n=5)
integer a(n)
integer w
a(1)=4; a(2)=2; a(3)=5 ; a(4)=1; a(5)=3
do i=2,n
do j=i,2,-1
if(a(j-1).gt.a(j)) then ! a(j-1)とa(j)の比較
w=a(j); a(j)=a(j-1); a(j-1)=w ! a(j-1)とa(j)の交換
else
exit ! 並び替えの必要がないのでループから抜ける
end if
end do
end do
write(*,*) a
end
これで無駄な、無意味な挿入箇所の探索省くことが可能となり、より高速に並び替えを行うことができるのですが、a(j−1)とa(j)の交換処理には
w=a(j); a(j)=a(j-1); a(j-1)=w
と３つの作業が必要になるので、まだまだ、無駄が多い。
そこで、アルゴリズムを次のように変更する。
do i=2, 3, ・・・, n
t=a(i)
do j=i, i−1, ・・・, 2
a(j−1)>tならば、a(j)をa(j−1)に代入 （a(j−1)を１つ後ろにずらす）
そうでなければ、ループを抜ける
end do j
tをa(j)に代入
end do i
このように変更すると、
w=a(j); a(j)=a(j-1); a(j-1)=w
を
a(j)=a(j−1)
と１つの作業にすることができる。
これで、より、高速に並び替えを行うことができる。
parameter(n=100)
integer a(n)
integer t
do i=1, n
a(i)=nrandom(n) ! 乱数を使って1〜nまでのデータの作成
end do
do i=2,n
t=a(i) ! a(i)をtにコピー
do j=i,2,-1
if(a(j-1).gt.t) then ! a(j-1)とtの比較
a(j)=a(j-1) ! a(j-1)を後方に１つずらす
else
exit ! 並び替えの必要がないのでループから抜ける
end if
end do
a(j)=t ! tを挿入
end do
write(*,100) (a(i), i=1,n)
100 format (10(i8))
end
! 1〜nまでの乱数を作成
function nrandom(n)
call random_number(x)
nrandom = n*x+1
end
function nrandom(n)
call random_number(x)
nrandom = n*x+1
end
プログラムの実行結果
2019-02-20 12:00
nice!(0)
コメント(0)
コメント 0