bogoSort

タグ: ,

要素をランダムに並べ替えることで偶発的な一致を試みる整列アルゴリズムです。

構文
bogoSort( Var array )
引数
array必須
ソートする数値を格納した配列。参照引数。
戻り値

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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

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

ボゴソート

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

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

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

アルゴリズム

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

関連記事

QSORT (スクリプト関数)
配列の中身をソートします。
gnomeSort (自作関数)
引数に指定された配列を ノームソート で並び替えます。
bubbleSort (自作関数)
引数に指定された配列を バブルソート で並び替えます。
shakerSort (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
combSort (自作関数)
引数に指定された配列を コムソート で並び替えます。
selectionSort (自作関数)
引数に指定された配列を 選択ソート で並び替えます。
heapSort (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
oddEvenSort (自作関数)
引数に指定された配列を 奇偶転置ソート で並び替えます。
shearSort (自作関数)
引数に指定された配列を シェアソート で並び替えます。
insertionSort (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
shellSort (自作関数)
引数に指定された配列を シェルソート で並び替えます。
mergeSort (自作関数)
引数に指定された配列を マージソート で並び替えます。
quickSort (自作関数)
引数に指定された配列を クイックソート で並び替えます。
Sort オブジェクト
データの並び替えを行います。
CALCARRAY (スクリプト関数)
配列データを計算します。
GETALLWIN (スクリプト関数)
全ウィンドウのIDを取得します。
JOIN (スクリプト関数)
配列の中身を区切り文字で結合し、文字列として返します。
SETCLEAR (スクリプト関数)
配列を指定された値で埋めます。
GETOLEITEM (スクリプト関数)
コレクションを取得します。
SHIFTARRAY (スクリプト関数)
配列データをシフトします。
UBound (自作関数)
配列の上限値(最大インデックス)を求めます。
連想配列
連想配列とは、自動的に割り当てられる数字をキーとして持つかわりに、自由に任意の文字列を割り振ることができる配列のことです。添え字に番号の変わりに名前をつけることでわかりやすく管理することができます。
inArray (自作関数)
指定した値が配列に存在すればTrue、なければFalseを返します。
POPUPMENU (スクリプト関数)
ポップアップメニューを表示します。
divisors (自作関数)
引数に指定した数値の約数のリストを返します。
Collatz (自作関数)
コラッツ数列 を求め結果を配列で返します。
Kaprekar (自作関数)
カプレカ数 を求め結果を配列で返します。
arraySearch (自作関数)
配列の中から指定した要素が見つかった場合、その要素がある最初のインデックスを返します。
arrayReverse (自作関数)
引数に指定した配列を逆順にして返します。
arrayDiff (自作関数)
配列の差を計算します。
RESIZE (スクリプト関数)
配列のサイズを変更します。
SLICE (スクリプト関数)
配列の中を指定範囲の配列で返します。
FOR-IN-NEXT
配列の要素分だけ処理を繰り返します。FOR文でも書き換えられます。
getFolderList (自作関数)
サブフォルダを含めたフォルダ一覧を配列で返します。
SPLIT (スクリプト関数)
文字列を区切り、配列を作成します。