ノームソート

 

 ノームソート(gnome sort)は、バブルソートのように隣どうしのデータの大小関係を比べる方法ですが、比較位置を変える方法を工夫しているため、処理が速いという技法です。

 なお、英語版 Wikipedia では、「テレポート機能」と称する最適化処理を組み込むことで、更に処理速度を向上させた例も紹介しています。

 植木鉢の並び替えの記事が書かれていますが、現実作業で考えると、この方法は画期的です。高速なソート法は他にもありますが、持ちにくくて重たい植木鉢を遠くまで運んでスワップするのは体力が必要です。しかし、この方法だと、短い距離をずるずると引っ張ればよいだけなので、腰も痛くならないことでしょう。

 日本語版 Wikipedia では、「挿入ソートにせまるくらい速い」という表現がありますが、質の悪い低速の挿入ソートと比べると、それに迫る速さがあります。質の悪い低速挿入ソートは、「C言語講座」のようなタイトルのサイトでいくらでも配信していますから、容易に入手できることでしょう。きちんとした、高速型の挿入ソートと比べると、実行速度は2倍の開きがあります。

特 徴

実行速度の例

 win32 環境での速度例です。レコード数 10 万件、レコード長8バイト、数値の単位はミリ秒です。ちなみにバブルソートの Random32 は 15 秒台です。

  Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer
Type A(VC) 6021.64 6099.64 6068.44 6037.24 0.00 12152.48 0.00 6052.84
Type B(VC) 6021.64 6099.64 6068.44 6021.64 0.00 12105.68 0.00 6052.84
Type C(VC) 4539.63 4555.23 4524.03 4539.63 0.00 8798.46 0.00 4555.23
Type D(VC) 3806.42 3853.22 3822.02 3900.03 0.00 7784.45 0.00 3915.63

 x64 環境での速度例です。レコード数 10 万件、レコード長 16 バイト、数値の単位はミリ秒です。ちなみにバブルソートの Random32 は 16 秒台です。

  Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer
Type A(VC) 8221.25 8408.45 8392.85 8377.25 0.00 16785.71 0.00 8377.25
Type B(VC) 6130.84 6271.24 6208.84 6224.44 0.00 12542.48 0.00 6271.24
Type C(VC) 5319.63 5350.83 5335.23 5319.63 0.00 10670.47 0.00 5335.23
Type D(VC) 4009.23 4071.63 4040.43 4071.63 0.00 8236.85 0.00 4056.03

 ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。

GnomeSort.txt stdafx.txt

Type A

static DWORD __stdcall GnomeSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
size_t sztPtr, sztGurd;

if( pTop < pBtm )
{
sztGurd = sztPtr = pTop + 1;
do
{
if( pArray[ sztPtr - 1 ].Key <= pArray[ sztPtr ].Key )
{
sztPtr++;
}
else
{
SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] );
if( sztPtr > sztGurd )
sztPtr--;
else
{
sztPtr++;
if( *pAbort ) return 1223;
}
}
}
while( sztPtr <= pBtm );
}
return 0;
}

DWORD __stdcall GnomeSortA(SortRecStruct* pArray, size_t pRecordCount, bool* pAbort)
{
return GnomeSortAR( pArray, 0, pRecordCount - 1, pAbort );
}

Type B

static DWORD __stdcall GnomeSortBR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{

SortRecStruct *RecPtr, *RecGurd;

if( pTop < pBtm )
{
RecGurd = RecPtr = pTop + 1;
do
{
if( ( RecPtr - 1 )->Key <= RecPtr->Key )
{
RecPtr++;
}
else
{
SwapUU( RecPtr - 1, RecPtr );
if( RecPtr > RecGurd )
RecPtr--;
else
{
RecPtr++;
if( *pAbort ) return 1223;
}
}
}
while( RecPtr <= pBtm );
}
return 0;
}

DWORD __stdcall GnomeSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return GnomeSortBR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}

Type C

static DWORD __stdcall GnomeSortCR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
size_t sztTeleportPtr, sztPtr, sztGurd;

if( pTop < pBtm )
{
sztTeleportPtr = pTop; sztGurd = sztPtr = pTop + 1;
do
{
if( pArray[ sztPtr - 1 ].Key <= pArray[ sztPtr ].Key )
{
if( sztTeleportPtr != pTop )
{
if( *pAbort ) return 1223;
sztPtr = sztTeleportPtr; sztTeleportPtr = pTop;
}
sztPtr++;
}
else
{
SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] );
if( sztPtr > sztGurd )
{
if( sztTeleportPtr == pTop )
sztTeleportPtr = sztPtr;
sztPtr--;
}
else
{
sztPtr++;
}
}
}
while( sztPtr <= pBtm );
}
return 0;
}

DWORD __stdcall GnomeSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return GnomeSortCR( pArray, 0, pRecCount - 1, pAbort );
}

Type D

static DWORD __stdcall GnomeSortDR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct *RecTeleportPtr, *RecPtr, *RecGurd;

if( pTop < pBtm )
{
RecTeleportPtr = pTop; RecGurd = RecPtr = pTop + 1;
do
{
if( ( RecPtr - 1 )->Key <= RecPtr->Key )
{
if( RecTeleportPtr != pTop )
{
if( *pAbort ) return 1223;
RecPtr = RecTeleportPtr; RecTeleportPtr = pTop;
}
RecPtr++;
}
else
{
SwapUU( RecPtr - 1, RecPtr );
if( RecPtr > RecGurd )
{
if( RecTeleportPtr == pTop )
RecTeleportPtr = RecPtr;
RecPtr--;
}
else
{
RecPtr++;
}
}
}
while( RecPtr <= pBtm );
}
return 0;
}

DWORD __stdcall GnomeSortD(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return GnomeSortDR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}

 Type D ですが、テレポート機能を使って元の位置に戻る判定のところで、CMOV 命令のコードが生成されていますので、本来の能力ではありません。しかし、その実行回数が少ないために影響は小さくなっています。CMOV 命令の弊害については、次のセレクションソートの記事を参照してください。

注意事項

 このサイトの冒頭でも記事にしていますが、比較の順序を左右逆にすると処理速度が速くなることもあります。いろいろなパターンのうち、どの方法が最良なのかはそれぞれの環境で異なります。

 このような組み合わせはまだまだ考えられます。スキャン方向を逆にすると速いのか遅いのかなども含まれます。全部の組み合わせは書ききれないので、今回は4つのリストのみ掲載しています。


Cocktail Sort | Selection Sort


contents
Top Page caution Bubble Sort Odd Even Sort Cocktail Sort  Gnome Sort Selection Sort  Min Max Sort Insertion Sort Shell Sort Heap Sort Comb Sort Merge Sort Quick Sort Do-Re-Mi-Fa Sort chat
inserted by FC2 system