暇だったので比較プログラムを作ってみました。
(各アルゴリズムの命名は適当につけました、見当違いだったらごめんなさい)
個人的には入れ替え型が一番早いかな、と思ったのですがソート型が一番早くてびっくりです。
計算量的にソートって無駄がありそうなんですが・・・
#uselib "winmm.dll"
#cfunc global timeGetTime "timeGetTime"
#const Ofx 300;1回あたりの時間を表示する位置
#const DrawOfy 160;乱数表を可視化した図形
screen 0,600,260
randomize
繰り返し回数=1000
posx=10:posy=10;表示用
line_=0
StartTime=timeGetTime()
repeat 繰り返し回数
length_=90;乱数の長さ
length_half=length_/2;乱数の長さの半分
dim value,length_
dim Rndarr,length_;乱数表
repeat length_
RndSheet.cnt=rnd(length_);適当に乱数を入れる。被りとかは気にしなくておk
loop
;乱数表を小さい順にソート
sortval RndSheet,0;p2 並び順 (0=小さい順/1=大きい順)
repeat length_
sortget i,cnt;ソート元のインデックスを取得
value.i=cnt
loop
/*
if length_>cnt{
repeat length_
color value.cnt,value.cnt,value.cnt:pset cnt,line_+DrawOfy
loop
line_+1
}
//*/
loop
EndTime=timeGetTime()
color 0,0,0
pos posx,posy:mes "ソート型 (提案者:ソラ)"
pos posx+Ofx,posy:mes "1回あたり"+(double(EndTime-StartTime)/limitf(繰り返し回数,1))+"ms"
line_=0
StartTime=timeGetTime()
repeat 繰り返し回数
length_ = 90;乱数の長さ
dim value, length_; // 重複しない乱数を格納する配列変数
// 一旦配列に0〜89までの数値を順番に入れる
repeat length_
value(cnt) = cnt;
loop
// 配列に入れた数値をランダムな箇所と入れ替える
repeat length_
idx = rnd(length_); // ランダムな箇所を決定する
if idx=cnt:continue
// 以下3行は2つの数を入れ替える処理
value(cnt) += value(idx);
value(idx) = value(cnt) - value(idx);
value(cnt) -= value(idx);
loop
/*
if length_>cnt{
repeat length_
color value.cnt,value.cnt,value.cnt:pset cnt+100,line_+DrawOfy
loop
line_+1
}
//*/
loop
EndTime=timeGetTime()
posy+25
color 0,0,0
pos posx,posy:mes "入れ替え型(提案者:あらやさん)
pos posx+Ofx,posy:mes "1回あたり"+(double(EndTime-StartTime)/limitf(繰り返し回数,1))+"ms"
line_=0
StartTime=timeGetTime()
repeat 繰り返し回数
dim RndTable,90
dim value,90
//乱数テーブル作成
repeat 90
RndTable(cnt) = cnt
value_check += RndTable(cnt)
loop
repeat 90
//value 0〜44 用
i = rnd(90 - cnt)
value(cnt) = RndTable(i)
//利用した乱数テーブル要素を後方に移動
tmp = RndTable(i)
RndTable(i) = RndTable(89 - cnt)
RndTable(89 - cnt) = tmp
loop
/*
if length_>cnt{
repeat length_
color value.cnt,value.cnt,value.cnt:pset cnt+200,line_+DrawOfy
loop
line_+1
}
//*/
loop
EndTime=timeGetTime()
posy+25
color 0,0,0
pos posx,posy:mes "片付け型 (提案者:MillkeyStarsさん)"
pos posx+Ofx,posy:mes "1回あたり"+(double(EndTime-StartTime)/limitf(繰り返し回数,1))+"ms"
line_=0
StartTime=timeGetTime()
repeat 繰り返し回数
dim value,90
repeat 90
value(cnt) = cnt
loop
for i , 90 - 1, 0 , -1
j = rnd(i + 1)
b = value(i)
value(i) = value(j)
value(j) = b
next
/*
if length_>cnt{
repeat length_
color value.cnt,value.cnt,value.cnt:pset cnt+300,line_+DrawOfy
loop
line_+1
}
//*/
loop
EndTime=timeGetTime()
posy+25
color 0,0,0
pos posx,posy:mes "入れ替え型 (提案者:Makotoさん)"
pos posx+Ofx,posy:mes "1回あたり"+(double(EndTime-StartTime)/limitf(繰り返し回数,1))+"ms"
line_=0
StartTime=timeGetTime()
repeat 繰り返し回数
dim value, 90
ii = 0
repeat
r = rnd( length( value ) )
repeat ii
if value.cnt == r: r = -1: break
loop
if r == -1: continue
value.ii = r
ii ++: if ii = length( value ): break
loop
/*
if length_>cnt{
repeat length_
color value.cnt,value.cnt,value.cnt:pset cnt+400,line_+DrawOfy
loop
line_+1
}
//*/
loop
EndTime=timeGetTime()
posy+25
color 0,0,0
pos posx,posy:mes "総当り型 (提案者:さかさん)"
pos posx+Ofx,posy:mes "1回あたり"+(double(EndTime-StartTime)/limitf(繰り返し回数,1))+"ms"
line_=0
StartTime=timeGetTime()
repeat 繰り返し回数
dim value, 90
repeat 90
value(cnt)=-1
loop
repeat 90
c=cnt
repeat
i=rnd(90)
if(value(i)=-1){
value(i)=c
break
}
loop
loop
/*
if length_>cnt{
repeat length_
color value.cnt,value.cnt,value.cnt:pset cnt+500,line_+DrawOfy
loop
line_+1
}
//*/
loop
EndTime=timeGetTime()
posy+25
color 0,0,0
pos posx,posy:mes "フラグ型 (提案者:kanamaruさん)
pos posx+Ofx,posy:mes "1回あたり"+(double(EndTime-StartTime)/limitf(繰り返し回数,1))+"ms"