mergeSort

タグ: ,

マージソートは整列されていないリストを2つのリストに分割して、それぞれを整列させた後、それらをマージして整列済みのひとつのリストを作ります。

構文
mergeSort( Var array[], [Lt = 0, Rt = 0] )
引数
array
ソートする数値を格納した配列。参照引数。
Lt
Rt
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
//   Lt 
//   Rt 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE mergeSort(Var array[], Lt = 0, Rt = 0)
	IF Rt = 0 THEN Rt = UBound(array)
	IFB Rt - Lt <= 1 THEN
		IFB array[Lt] >= array[Rt] THEN
			swap(array[Lt], array[Rt])
		ENDIF
		EXIT
	ENDIF
	DIM mid = INT((Lt + Rt) / 2)
	mergeSort(array, Lt, mid)
	mergeSort(array, mid + 1, Rt)
	merge(array, Lt, mid + 1, Rt)
FEND

PROCEDURE merge(Var array[], Lt, mid, Rt)
	DIM tmp1 = SLICE(array, Lt, mid - 1)
	DIM tmp2 = SLICE(array, mid, Rt)
	DIM tmp[-1]
	WHILE tmp1[0] <> EMPTY OR tmp2[0] <> EMPTY
		IFB (tmp1[0] < tmp2[0] AND tmp1[0] <> EMPTY) OR tmp2[0] = EMPTY THEN
			arrayPush(tmp, tmp1[0])
			SHIFTARRAY(tmp1, -1)
		ELSE
			arrayPush(tmp, tmp2[0])
			SHIFTARRAY(tmp2, -1)
		ENDIF
	WEND
	FOR n = Lt TO Rt
		array[n] = tmp[n-Lt]
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   array : 要素を追加する配列(参照引数) 
//   str : 追加する要素 
// 【戻値】
//   処理後の配列の中の要素の数 
//////////////////////////////////////////////////
FUNCTION arrayPush(var arr[], str)
	DIM res = RESIZE(arr, UBound(arr) + 1)
	arr[res] = str
	RESULT = res + 1
FEND

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

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

マージソート

アルゴリズム

  1. データ列を2分割する。