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分割する。