bubbleSortバブルソート関数

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

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

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

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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を繰り返す回数 
// 【戻り値】
//   
//////////////////////////////////////////////////
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

解説

  1. 2,6行目
    UWSC
    	FOR i = 0 TO UBound(array) - 1
    		…
    	NEXT
    配列の要素の数だけ繰り返す。この処理を繰り返すたびに配列の添字が大きい値が順に1つずつ確定していきます。
  2. 3,5行目
    UWSC
    		FOR j = 0 TO UBound(array) - i - 1
    			…
    		NEXT
    配列の0番目から順に値の比較を行う。2行目>>>を実行するたびに最大値が確定していくので、比較を行う範囲をiだけ減らしていきます。
  3. 4行目
    UWSC
    			IF array[j] > array[j+1] THEN swap(array[j], array[j+1])
    もしarrayj番目がj+1番目よりも大きければ、その2つの要素を入れ替える。この処理で比較した2つの値は添字の大きい方の値が大きくなるよう並び替えられます。

使い方

UWSC
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5

bubbleSort(array)

FOR item IN array
	PRINT item
NEXT
結果
プレーンテキスト
2
4
5
8
14
17
20
22
25
30

バブルソート

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

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

アルゴリズム

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

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

関連記事

QSORT関数 (スクリプト関数)
QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
small関数 (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
shakerSort関数 (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
gnomeSort関数 (自作関数)
ノームソートはソートアルゴリズムの一つです。挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行います。
insertionSort関数 (自作関数)
挿入ソートは、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入します。
shellSort関数 (自作関数)
シェルソートは挿入ソートが改良された整列アルゴリズムです。リストにおいてあらかじめ離れている要素を交換しておき、最終的に挿入ソートを実行します。
heapSort関数 (自作関数)
引数に指定された配列をヒープソートで並び替えます。
quickSort関数 (自作関数)
問題を小さな部分問題に分割していく分割統治法を利用した手法で、データから適当に基準値を決めこれより大きいグループと小さいグループに分けるという手順を、分けた小さなグループに対しても再帰的に繰り返していきます。
shearSort関数 (自作関数)
シェアソートはソートアルゴリズムの一つで、データを長方形に並べた上で各行・各列ごとにソートを行ないます。
Sort.Header プロパティ (Excel)