インデクスソートモジュール作りました
インデクスソートをモジュール化してみました。
それなりに速度は最適化したつもりです。
長いスクリプトですがお付き合いください。
バグがあれば修正しますので報告宜しくお願いします。
#ifndef IndexSort #module // 必須 , 必須(この配列がソートされる), 省略時 = 昇順 , 省略時 = 非安定 , 省略時(max) = インデクス配列の最後まで , 省略時 = インデクス配列の先頭 // 比較元の配列 , インデクスが格納された配列 , 昇順降順フラグ , 安定化フラグ , ソートする個数 , インデクス配列のオフセット #deffunc IndexSort array ar , array _index , int 降順 , int 安定 , int _size , int _offset len = length(_index) offset = limit(_offset, 0, len - 1) size = limit(_size, 0, len - offset) if size <= 0: size = len - offset if size <= 1: return ptr = varptr(_index) + offset * 4 dupptr index, ptr, size * 4 e = size - 1 on (((vartype(ar) == 2) << 2) | ((降順 ! 0) << 1) | (安定 ! 0)) goto *lab0, *lab1, *lab2, *lab3, *lab4, *lab5, *lab6, *lab7 *lab0: QuickSort数値昇順 ar : return *lab2: QuickSort数値降順 ar : return *lab4: QuickSort文字列昇順 ar : return *lab6: QuickSort文字列降順 ar : return #define バッファ確保 if length(t) < size{ dim t, size} tptr = varptr(t) *lab1: バッファ確保: MergeSort数値昇順 ar,,e: return *lab3: バッファ確保: MergeSort数値降順 ar,,e: return *lab5: バッファ確保: MergeSort文字列昇順 ar,,e: return *lab7: バッファ確保: MergeSort文字列降順 ar,,e: return //無限ループ定義 #define ● %tmlploop *%i // ラベル repeat #define ◎ %tmlploop goto*%p // goto ● continue #define ○ %tmlploop goto*%o // goto ● loop #define swap(%1, %2) tmp = index(%1): index(%1) = index(%2): index(%2) = tmp #const INSERT 13 //要素数閾値以下は挿入ソートで処理 //定義読み込み展開 #define ctype 比較器(%1, %2) ((%1) < (%2)) #define QuickIndexSort QuickSort数値昇順 #define MainArrayMerge MergeSort数値昇順 #define SubArrayMerge _MergeSort数値昇順 #include __FILE__ #define ctype 比較器(%1, %2) ((%1) > (%2)) #define QuickIndexSort QuickSort数値降順 #define MainArrayMerge MergeSort数値降順 #define SubArrayMerge _MergeSort数値降順 #include __FILE__ #define ctype 比較器(%1, %2) (((%1) ! (%2)) < 0) #define QuickIndexSort QuickSort文字列昇順 #define MainArrayMerge MergeSort文字列昇順 #define SubArrayMerge _MergeSort文字列昇順 #include __FILE__ #define ctype 比較器(%1, %2) (((%1) ! (%2)) > 0) #define QuickIndexSort QuickSort文字列降順 #define MainArrayMerge MergeSort文字列降順 #define SubArrayMerge _MergeSort文字列降順 #include __FILE__ #global #endif //以下ソート定義 #ifdef 比較器 ///////////////////////QuickSort_Core/////////////////////////非再帰 #deffunc QuickIndexSort array ar left = 0 right = e ● l = left r = right //ピボット選択 med = 1 | logf(r - l) ; サンプルとしてソートする要素数 medst = l + rnd(r - l - med) ; ソート位置乱択 //中間値確定までバブルソート repeat med / 2 + 1, 1 repeat med - cnt, medst if 比較器(ar(index(cnt + 1)), ar(index(cnt))): swap cnt + 1, cnt loop loop // 中間値をピボットにする pivot = ar(index(medst + med / 2)) ●: if 比較器(pivot, ar(index(r))): r-: ◎ ; 右要素選択 ●: if 比較器(ar(index(l)), pivot): l+: ○ ; 左要素選択 if l < r{ //交換して次のペアを探しに行く swap l, r l+ r- ○ } //ピボットを基準とした交換処理終了 //次の分割への処理 if l - left > INSERT{ if right - r > INSERT{ //右側領域をスタックに積む lstack(sn) = r + 1 rstack(sn) = right sn+ } //左側領域分割実行 right = l - 1 ◎ } if right - r > INSERT{ //右側領域分割実行 left = r + 1 ◎ } //スタックに領域が積まれていれば取り出して分割実行 if sn{ sn- left = lstack(sn) right = rstack(sn) ○ } //クイックソートによる大まかなソート終了 //仕上げ(全体を挿入ソートする) //番人となる要素を先頭に移動 for r, limit(INSERT - 1, 0, e), 0, -1 if 比較器(ar(index(r)), ar(index(r - 1))): swap r, r - 1 next //番人付き挿入ソート repeat e - 1, 2 l = cnt tmp = index(l) tmpval = ar(tmp) ●: if 比較器(tmpval, ar(index(l - 1))): index(l) = index(l - 1): l-: ○ index(l) = tmp loop return ///////////////////////MergeSort_Core//////////////////////////////相互再帰、修正マージソート //本体をマージソート #deffunc MainArrayMerge array ar, int p1, int p2 if p2 - p1 < INSERT{ //要素数が閾値以下なので挿入ソート repeat p2 - p1, p1 + 1 l = cnt tmp = index(l) tmpval = ar(tmp) ●: if 比較器(tmpval, ar(index(l - 1))): index(l) = index(l - 1): l-: if l > p1: ○ index(l) = tmp loop return } //左側をバッファにソート、右側を本体にソート SubArrayMerge ar, p1, p2 + p1 >> 1 MainArrayMerge ar, (p2 + p1 >> 1) + 1, p2 //ソート結果を本体にマージ 先頭同士を比較して本体の左側からつめて行く lstart = p1 lend = p2 + p1 >> 1 rstart = lend + 1 ;rend == p2 //マージ開始 repeat , p1 if 比較器(ar(index(rstart)), ar(t(lstart))){ index(cnt) = index(rstart) if rstart = p2{ memcpy index, t, lend - lstart + 1 << 2, cnt + 1 << 2, lstart << 2 break } rstart+ }else{ index(cnt) = t(lstart) if lstart = lend: break lstart+ } loop return //バッファをマージソート #deffunc SubArrayMerge array ar, int p1, int p2 if p2 - p1 < INSERT{ //要素数が閾値以下なので挿入ソート (本体からバッファに挿入していく t(p1) = index(p1) repeat p2 - p1, p1 + 1 l = cnt tmp = index(l) tmpval = ar(tmp) ●: if 比較器(tmpval, ar(t(l - 1))): t(l) = t(l - 1): l-: if l > p1: ○ t(l) = tmp loop return } //左側をバッファにソート、右側を本体にソート SubArrayMerge ar, p1, p2 + p1 >> 1 MainArrayMerge ar, (p2 + p1 >> 1) + 1, p2 //ソート結果をバッファにマージ 末尾同士を比較して右側につめて行く lend = p2 + p1 >> 1 l = lend - p1 r = p2 - lend - 1 gend = p2 - p1 dupptr nl, tptr + p1 * 4 , gend + 1 << 2 dupptr nr, ptr + lend * 4 + 4, r + 1 << 2 // マージ開始 ●: if 比較器(ar(nr(r)), ar(nl(l))){ nl(gend) = nl(l) if l: l-: gend-: ◎ memcpy nl, nr, r + 1 << 2 }else{ nl(gend) = nr(r) if r: r-: gend-: ○ } return #undef 比較器 #undef QuickIndexSort #undef MainArrayMerge #undef SubArrayMerge #else //-----------定義ここまで--------------// // 簡単なサンプル #if 0 title"インデクスソート サンプル" size = 20 repeat size data.cnt = rnd(size) index.cnt = cnt loop pos 0,0 mes "ソート前" repeat size mes strf("データ = %03d 元の位置(%03d)",data(index.cnt),index.cnt) loop indexsort data, index ; 昇順で非安定ソート(indexの全ての範囲) ;indexsort data, index, 1 ; 降順で非安定ソート(indexの全ての範囲) ;indexsort data, index, 1, 1 ; 降順で安定ソート(indexの全ての範囲) ;indexsort data, index,,,length(index) / 2 ; indexの半分だけソート ;indexsort data, index,,,,length(index) / 2 ; indexの半分からソート pos 250,0 mes "ソート後" repeat size mes strf("データ = %03d 元の位置(%03d)",data(index.cnt),index.cnt) loop pos 470,0 mes "文字列でのソート" strsample = "あ","り","ん","こ","♪" dim index index = 0,1,2,3,4 indexsort strsample, index foreach index mes strsample(index.cnt) + "(" + index.cnt + ")" loop #endif #endif
サンプルは 最後のほうの#if 0 を #if 1に変えると実行できます
