C++/quicksort

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

 
 
 
 
 
 
-
|
|
|
|
|
-
|
|
-
|
-
|
|
!
!
!
!
 
 
 
 
 
 
-
|
-
|
|
!
|
|
|
|
|
|
|
|
|
-
|
!
|
|
|
|
|
|
|
|
-
|
|
|
|
|
|
|
-
|
!
|
-
|
|
|
|
-
|
-
|
-
|
!
|
-
|
|
!
!
!
|
|
|
|
|
|
|
|
-
|
|
|
-
|
!
|
|
|
-
|
!
|
-
|
!
|
|
|
|
!
|
|
|
|
|
|
|
|
|
!
!
|
!

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 );
        }
    }
    
}