bogoSort

タグ: ,
構文
bogoSort( Var array[] )
引数
array
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE bogoSort(Var array[])
	DIM num = UBound(array)
	REPEAT
		DIM flg = FALSE
		FisherYates(array)
		FOR n = 0 TO num - 1
			IF array[n] > array[n+1] THEN
				flg = TRUE
				BREAK
			ENDIF
		NEXT
		SLEEP(0.001)
	UNTIL !flg
FEND

//////////////////////////////////////////////////
// 【引数】
//   var arr[] : シャッフルする配列（参照引数） 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE FisherYates(var arr[])
	FOR n = UBound(arr) TO 0 STEP -1
		DIM num = RANDOM(n+1)
		DIM tmp = arr[n]
		arr[n] = arr[num]
		arr[num] = tmp
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND

ボゴソート

ボゴソートはソートアルゴリズムの一つ。ソートされるまで要素をランダムに並び替え、運良くソートされていたら終了するというとても効率の悪いソート方法です。

要素数が多いと無限ループ状態になるので、強制終了処理を入れることをおすすめします。

運がよければ1回目でソート完了するので、他のどのソート方法よりも最速になることもあります。

アルゴリズム

  1. 与えられたデータをバラバラにしたのち、無作為に並べる。
  2. 並べたデータが正しい順序になっていれば終了。そうでなければ1から繰り返す。
  3. ソートされていたら終了。ソートされていなければ1〜3を繰り返す。