bubbleSort関数

本ページには広告が含まれています。

引数に指定された配列をバブルソートで並び替えます。参照引数で戻り値はありません。

構文: bubbleSort( array )

引数

array 必須: ソートする数値を格納した配列。参照引数。

戻り値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。
// 【戻り値】
//////////////////////////////////////////////////
PROCEDURE bubbleSort(Var array[])
	FOR i = 0 TO UBound(array) - 1
		FOR j = 0 TO UBound(array) - i - 1
			IF array[j] > array[j+1] THEN swap(array[j], array[j+1])
		NEXT
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   inputs : 繰り返す文字列
//   multiplier : inputsを繰り返す回数
// 【戻り値】
//   inputsをmultiplier回を繰り返した文字列を返します
//////////////////////////////////////////////////
FUNCTION strRepeat(inputs, multiplier)
	DIM res = ""
	FOR n = 1 TO multiplier
		res = res + inputs
	NEXT
	RESULT = res
FEND

//////////////////////////////////////////////////
// 【引数】
//   a : bと交換する値。参照引数。
//   b : aと交換する値。参照引数。
// 【戻り値】
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   arrayname : 上限値を求める配列の名前
//   dimension : 返す次元を示す整数
// 【戻り値】
//   配列の上限値
//////////////////////////////////////////////////
FUNCTION UBound(arrayname[], dimension = 1)
	RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")")
FEND

解説

2,6行目

配列の要素の数だけ繰り返す。この処理を繰り返すたびに配列の添字が大きい値が順に1つずつ確定していきます。

3,5行目

配列の0番目から順に値の比較を行う。2行目>>>を実行するたびに最大値が確定していくので、比較を行う範囲をiだけ減らしていきます。

4行目

もしarrayのj番目がj+1番目よりも大きければ、その2つの要素を入れ替える。この処理で比較した2つの値は添字の大きい方の値が大きくなるよう並び替えられます。

使い方

結果

バブルソート

バブルソートは、ソートを行うアルゴリズムの一つです。リストにおいて隣り合うふたつの要素の大小を比較しながらソートを行います。基本交換法、隣接交換法ともいいます。

最悪計算時間	\(O(n^{2})\)
最良計算時間	\(O(n)\)
平均計算時間	\(O(n^{2})\)

アルゴリズム

すべての要素に関して、隣接する要素を比較し大小が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行います。繰り返しは入れ替えが起こらなくなった時点で中断することができます。

最初に、配列の先頭要素をカレントポインタに設定します。
カレントポインタが配列の末尾まで到達するまで、以下の処理を繰り返します。
1. カレントポインタが指す要素と、カレントポインタの次の要素の大小関係を比較します。
2. もし、大小関係が逆であれば、2つの要素を交換します。
カレントポインタが配列の末尾まで到達したら、ソートが完了です。

QSORT関数 (スクリプト関数): 配列の中身をソートします。
shakerSort関数 (自作関数): 引数に指定された配列をシェーカーソートで並び替えます。
gnomeSort関数 (自作関数): 引数に指定された配列をノームソートで並び替えます。
small関数 (自作関数): 配列の中で小さい方から数えた順位の値を求めます。
insertionSort関数 (自作関数): 引数に指定された配列を挿入ソートで並び替えます。
shellSort関数 (自作関数): 引数に指定された配列をシェルソートで並び替えます。
heapSort関数 (自作関数): 引数に指定された配列をヒープソートで並び替えます。
quickSort関数 (自作関数): 引数に指定された配列をクイックソートで並び替えます。
shearSort関数 (自作関数): 引数に指定された配列をシェアソートで並び替えます。
RESIZE関数 (スクリプト関数): 配列の上限値を取得または変更します。配列の上限値を変更する場合は第二引数に値を指定します。