最近のソートは、クイックソートに代わってマージソートが主流のようです。 最大の理由は「安定」性にあると思われます。しかし、マージソートは 　（１）要素の移動回数が多い 　（２）同じキー値が複数現れる場合でも速度向上が十分には望めない などの欠点があります。 #####このことから「安定」な qsort (Sqsort) (比較ソート) を作りました。 #####最大の特徴は、キー値に同じ値が現れる場合に極めて高速なことです。 Sqsortはjavaで記述してあり、同じくjavaで記述したTimSortより高速です。 大雑把にいうと、Sqsortは補助配列(bas2)と対象配列(base)で 以下のような移動を繰り返します。 ``` bas2:............... → bas2:5555......77787 → bas2:..........77787 base:357358257257237 Ａ base:332223......... Ｂ base:3322235555..... ``` プログラム(約150行 classファイル 3164byte) は最後に記載します。 TimSort(約900行 classファイル 8801byte) よりかなりコンパクトです。 処理時間を測定したものを以下に記載します。 ``` ソート名 キーの種類 　要素数　 　繰返し回数　処理時間(秒) TimSort d=-3 e=10000 R=2000 C=8.21 Sqsort d=-3 e=10000 R=2000 C=5.65 TimSort d=100 e=10000 R=2000 C=6.69 Sqsort d=100 e=10000 R=2000 C=2.81 TimSort d=2 e=10000 R=6000 C=7.41 Sqsort d=2 e=10000 R=6000 C=2.09 d=-3:キーの重複なし　d=100:キーが100種類　d=2:キーが男女など 繰返し回数：処理時間の測定誤差を減らすためにソートを繰り返した回数 ``` すべての場合で、Sqsort は TimSort より高速です。 より詳細な測定結果・ベンチマークプログラム・TimSort/Sqsortのソースコードなどは 　　　　http://ww51.tiki.ne.jp/~srr-cake/qsort/sqs18j/ 　　にあります。 「安定」とは、キー値が同じ時、ソート前の順序をソート後も保持することです。 「安全」とは、「悪意のある配列により、異常に長い処理時間を発生させることができない」 　　　　　　　こととします。 Sqsort では「安全」を実現するために、ピボットの候補を 乱数(System.nanoTime())により決定しています。 これにより、最悪計算時間O(n^2)は変化しませんが、 元々その発生確率は非常に低いものです。 これまで長い間、C言語のnewlibライブラリのqsort()の実装において 最悪計算時間への配慮がなかったことが、その低さを示していると思います。 今回、最悪計算時間の発生確率は変わりませんが、 「悪意のある配列」を作ることは不可能になっていると思います。 以上３種類のソートを比較すると次の表のようになります。 | 　　　　 | TimSort | Sqsort　 | qsort 　 | |:--------|:-------:|:--------:|:--------:| | 速さ　　 | △ | ○ | ◎ | | 作業領域 | △ | △ | ◎ | | 安定性　 | ○ | ○ | × | | 安全性　 | ○ | ○ | × | また、TimSortでは配列に内在するソート済み部分列を有効利用しますが、 Sqsortにその機能はありません。 代わりに、Sqsortは同じキー値が複数回現れる場合に高速です。 TimSortにこの機能はありません。 すなわち、県名別にソートしたり、男女を分けるためにソートする場合に 極めて高速です。 　 お願い： 最悪計算時間や安全性の問題は、乱数による確率の問題として扱おうとしています。 長さｎの配列をクイックソートするとき、要素の比較回数の平均は C*n*log(n) です。 比較回数が C*n*log(n) の a倍(a=1,2,3...)以上 になる確率 P(n,a) は どのように表せばよいのでしょうか？ご存じの方がいらっしゃればお教え下さい。 　 以下が Sqsort のソースコードです。 ``` /***************************************************/ /* Sqsort (stable qsort) */ /* */ /* by 河村 知行 (kawamura tomoyuki) 2021.2.27 */ /* t-kawa@crux.ocn.ne.jp */ /***************************************************/ // Sqsort は安定な比較ソート。TimSortより高速で,作業領域は2n(TimSortはn),安全性はほぼ同じ /* 対象配列(base)と補助配列(bas2)(baseと同じ大きさ)を用いて安定なソートを行う。 以下のように Ａ,Ｂ 2段階で要素を移動する。ここで「5」はピボット(分割要素)を表している。 bas2:............... → bas2:5555......77787 → bas2:..........77787 base:357358257257237 Ａ base:332223......... Ｂ base:3322235555..... 移動Ａで、ピボットと同じ要素をbas2の左端に集め、5より小さい要素をbaseの左端に集め、 5より大きい要素をbas2の右端に集める。このとき77787は初期順序(元順)の逆順になっている。 移動Ｂの完了時点で5555はすでにソート完成状態の位置に収まっている。 Ｂ直後、5555以外の要素は、base上では元順に、bas2上では逆順に並んでいる。 次に332223の{所属フラグ(base/bas2)・先頭位置・末尾位置}をスタックに保存する。 これ以降、77787に対しbaseとbas2の意味を入れ替えて同じ処理を繰り返す。 部分配列が長さ15以下になれば挿入ソートを実施して部分配列のソートを完了し、次に スタックから{フラグ(base/bas2)・先頭位置・末尾位置}を取り出して処理を続ける。 スタックが空になればソートを終了する。 */ #define C(x,y) { x=(y); } /* ソート対象配列の要素のコピーに用いる */ #define S(x,y) {T tmp=(x); x=(y); y=tmp;} /* ソート対象配列の要素のスワップに用いる */ #define CMP(x,y) cmp.compare((x),(y)) #define med3p(x,y,z) (CMP(x,y)<=0 ? (CMP(y,z)<=0 ? y : (CMP(x,z)<=0 ? z : x)) : \ (CMP(y,z)>=0 ? y : (CMP(x,z)<=0 ? x : z)) ) #define I(x) {x++;} /* 配列base,bas2の添字を増やす */ #define D(x) {x--;} /* 配列base,bas2の添字を減らす */ import java.util.Comparator; class Sqsort { static int L,R; // L,Rは、baseまたはbas2上のソート対象となる領域[L〜R]の左端と右端 static boolean flagB; // [L〜R]領域がbase上にあるときtrue、bas2上にあるときfalse // popメソッド内で L,R,flagB へ代入できるように、sortメソッドのローカル変数からここへ移動した //#define base0 base /*これを有効にすると、配列base0を複写しない。 32bitJVMでは有効の方が速い*/ @SuppressWarnings({"unchecked"}) public static void sort( T[] base0, Comparator cmp ) {//base0:ソート対象である配列 // cmp:要素の比較をする関数 int l,r,m; //ptrB[L〜R]間の要素をptrB[L〜l],ptrR[r〜R],ptrR[L〜m]へ振り分ける。l領域 r領域 m領域 T[] ptrB, ptrR; //flagBのとき ptrB==base ptrR==bas2、!flagBのとき ptrB==bas2 ptrR==base。 int n,t,p; // nは、現在ソート中の[L〜R]領域の要素数。tは作業用。pはL〜R間を移動する添字 final long rndm = (System.nanoTime() & 0xFFFFFFFFFFFFL); //nanoTime()を乱数発生器として使用 class StkElt { //スタックをローカルクラスで実装 boolean sB; int sL,sR; void push(boolean b, int l, int r) { sB=b; sL=l; sR=r;} void pop () {flagB=sB; L=sL; R=sR; } } final int STK_LEN=32; // base0.lengthの最大値は2^31-1なので３２で十分 StkElt stk[] = new StkElt[STK_LEN]; for (int i=0; i=2 */ if (n <= 15) { //挿入ソート 結果はbase上に作る n==2でも動く 「15」は実験で得られた値 if (flagB) { //ソート領域base[L〜R]は 元順 になっている if (CMP(base[L],base[L+1])>0) S(base[L],base[L+1]) for (r = L+2; r <= R; r++) { if (CMP(base[r-1],base[r])<=0) continue; T tmp=base[r]; C(base[r],base[r-1]) for (l=r-2; L<=l && CMP(base[l],tmp)>0; l--) C(base[l+1],base[l]) base[l+1]=tmp; } }else{ //ソート領域bas2[L〜R]は 逆順 になっている if (CMP(bas2[R-1],bas2[R])<0) {C(base[L],bas2[R-1]) C(base[L+1],bas2[R]) } else {C(base[L],bas2[R]) C(base[L+1],bas2[R-1])} for (r = R-2; L <= r; r--) { t=L+(R-r); if (CMP(base[t-1],bas2[r])<=0) {C(base[t],bas2[r]) continue;} T tmp=bas2[r]; C(base[t],base[t-1]) for (l=t-2; L<=l && CMP(base[l],tmp)>0; l--) C(base[l+1],base[l]) base[l+1]=tmp; } } break; /*goto nxt;*/ } if (flagB) {ptrB=base; ptrR=bas2;} else {ptrB=bas2; ptrR=base;} {//３点処理（３要素からピボットを選択　高速化のため９点処理や２７点処理の版もある） int rnd = (int)(rndm % ((n >> 1) - 2)); //nanoTime()を乱数発生器として使用 T ll=ptrB[L+rnd], rr=ptrB[R-rnd], //悪意ある攻撃を無効化するため、要素を乱数で選択 mm=ptrB[L + (n >> 1)]; //中央の要素 //３点の内、定点が２点では悪意ある配列が作れてしまう T mmm=med3p(ll,mm,rr); //３点を比較して、mmmにピボットをセットする // l:ピボットより小さい要素(小要素)を次に置く所 r:大要素を次に置く所 m:同要素を次に置く所 // ptrR[L〜m]:左端からm領域を作る ptrR[r〜R]:の右端からr領域を作る(bas2上のr領域は逆順となる) // ptrB[L〜l]:左端からl領域を作る ptrB[L〜R]:この全要素を左端からl領域,r領域,m領域へ振分ける l=m=p=L; r=R; do {T pp=ptrB[p]; if ((t=CMP(pp,mmm)) < 0) {C(ptrB[l],pp) I(l)} else if (t > 0) {C(ptrR[r],pp) D(r)} else {C(ptrR[m],pp) I(m)} I(p)} while(p<=R); } assert L