C++/quicksort
をテンプレートにして作成
ホーム
検索
最終更新
ヘルプ
Wiki書式ヘルプ(整形ルール)
開始行:
* quicksort [#e48519fa]
簡単なクイックソートのコード。
#code(c,){{
template< typename T >
void bubbleSort(
T* aArray
, const uint aLeft
, const uint aRight
)
{
uint i;
bool loop;
loop = true;
while ( loop )
{
loop = false;
for ( i = aLeft+1; i <= aRight; ++i )
{
if ( aArray[i] < aArray[i-1] )
{
std::swap( aArray[i] , aArray[i-1] );
loop = true;
}
}
}
}
template< typename T , uint STACK_DEPTH >
void quickSort(
T* aArray
, const uint aCount
)
{
struct SortRange
{
uint left;
uint right;
};
uint i, j;
uint sp;
SortRange range;
SortRange rangeStack[ STACK_DEPTH ];
T pivot;
T* pivotPtr;
if ( aCount <= 1 )
{
return;
}
// スタック初期化
rangeStack[0].left = 0;
rangeStack[0].right = aCount-1;
sp = 1;
// スタックが空になるまで繰り返す
while( 0 < sp )
{
// スタック pop
--sp;
range = rangeStack[sp];
if ( range.left < range.right
&& (range.right - range.left) <= 4
)
{// 要素が少ない時はバブルソートを使用
bubbleSort( aArray , range.left , range.right...
}
else if (range.left < range.right)
{
// Pivotの選択
pivot = aArray[ (range.left+range.right)/2 ];
pivotPtr = &aArray[range.left];
if ( !(pivot < *pivotPtr) && !(*pivotPtr < pi...
{// 左端の値と等しく、領域内で最小値の場合、...
for ( i = range.left; i <= range.right; +...
{
if ( aArray[i] < pivot )
{
break;
}
else if ( pivot < aArray[i] )
{
pivot = aArray[i];
break;
}
}
}
// 1.左から順に値を調べ、P以上のものを見つけ...
// 2.右から順に値を調べ、P以下のものを見つけ...
// 3.iがjより左にあるのならばその二つの位置を...
// 4.1に戻らなかった場合、iの左側を境界に分割...
i = range.left;
j = range.right;
while (1)
{
while ( i < range.right
&& aArray[i] < pivot // pivot 以上が...
)
{
++i;
}
while ( range.left < j
&& pivot < aArray[j] // pivot 以下が...
)
{
--j;
}
if( j <= i )
{
break;
}
std::swap( aArray[i] , aArray[j] );
++i;
--j;
}
// スタック push
rangeStack[sp].left = range.left;
rangeStack[sp].right = i-1;
++sp;
rangeStack[sp].left = i;
rangeStack[sp].right = range.right;
++sp;
assert( sp < STACK_DEPTH );
}
}
}
}}
終了行:
* quicksort [#e48519fa]
簡単なクイックソートのコード。
#code(c,){{
template< typename T >
void bubbleSort(
T* aArray
, const uint aLeft
, const uint aRight
)
{
uint i;
bool loop;
loop = true;
while ( loop )
{
loop = false;
for ( i = aLeft+1; i <= aRight; ++i )
{
if ( aArray[i] < aArray[i-1] )
{
std::swap( aArray[i] , aArray[i-1] );
loop = true;
}
}
}
}
template< typename T , uint STACK_DEPTH >
void quickSort(
T* aArray
, const uint aCount
)
{
struct SortRange
{
uint left;
uint right;
};
uint i, j;
uint sp;
SortRange range;
SortRange rangeStack[ STACK_DEPTH ];
T pivot;
T* pivotPtr;
if ( aCount <= 1 )
{
return;
}
// スタック初期化
rangeStack[0].left = 0;
rangeStack[0].right = aCount-1;
sp = 1;
// スタックが空になるまで繰り返す
while( 0 < sp )
{
// スタック pop
--sp;
range = rangeStack[sp];
if ( range.left < range.right
&& (range.right - range.left) <= 4
)
{// 要素が少ない時はバブルソートを使用
bubbleSort( aArray , range.left , range.right...
}
else if (range.left < range.right)
{
// Pivotの選択
pivot = aArray[ (range.left+range.right)/2 ];
pivotPtr = &aArray[range.left];
if ( !(pivot < *pivotPtr) && !(*pivotPtr < pi...
{// 左端の値と等しく、領域内で最小値の場合、...
for ( i = range.left; i <= range.right; +...
{
if ( aArray[i] < pivot )
{
break;
}
else if ( pivot < aArray[i] )
{
pivot = aArray[i];
break;
}
}
}
// 1.左から順に値を調べ、P以上のものを見つけ...
// 2.右から順に値を調べ、P以下のものを見つけ...
// 3.iがjより左にあるのならばその二つの位置を...
// 4.1に戻らなかった場合、iの左側を境界に分割...
i = range.left;
j = range.right;
while (1)
{
while ( i < range.right
&& aArray[i] < pivot // pivot 以上が...
)
{
++i;
}
while ( range.left < j
&& pivot < aArray[j] // pivot 以下が...
)
{
--j;
}
if( j <= i )
{
break;
}
std::swap( aArray[i] , aArray[j] );
++i;
--j;
}
// スタック push
rangeStack[sp].left = range.left;
rangeStack[sp].right = i-1;
++sp;
rangeStack[sp].left = i;
rangeStack[sp].right = range.right;
++sp;
assert( sp < STACK_DEPTH );
}
}
}
}}
ページ名: