C++/quicksort の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• C++/quicksort へ行く。
• C++/quicksort の差分を削除

* 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 < pivot ) )
            {// 左端の値と等しく、領域内で最小値の場合、無限ループする可能性があるので、それを防ぐ
                for ( i = range.left; i <= range.right; ++i )
                {
                    if ( aArray[i] < pivot )
                    {
                        break;
                    }
                    else if ( pivot < aArray[i] )
                    {
                        pivot = aArray[i];
                        break;
                    }
                }
            }
            
            // 1.左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
            // 2.右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
            // 3.iがjより左にあるのならばその二つの位置を入れ替え、1に戻る。ただし、次の1での探索はiの一つ右、次の2での探索はjの一つ左から行う。
            // 4.1に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分ける。
            i = range.left;
            j = range.right;
            while (1) 
            {
                while ( i < range.right
                    && aArray[i] < pivot // pivot 以上が見つかるまで探す(pivot未満の間ループ)
                    ) 
                { 
                    ++i; 
                }
                while ( range.left < j
                    && pivot < aArray[j] // pivot 以下が見つかるまで探す(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 );
	    }
	}
    
}
}}