高速選択アルゴリズム

高速選択アルゴリズム
高速ソートアルゴリズムを少し修正して選択問題に適用できます.このアルゴリズムは高速選択アルゴリズムと呼ばれ、複雑度O(NlogN)、最悪の場合はO(N^2)です.Aの中の要素の個数にして、Aの中のk番目の最小要素を探します.アルゴリズムのステップは以下の通りです.
1)|A 124;＝1の場合、k=1はAの要素を答えとして返します.
2)Aの中の一つの元素Vを取って、ハブといいます.
3)A−｛V｝を二つの交差しないセットに分けます.A 1とA 2は、A 1の要素値がV以下であり、A 2の要素値はVに等しい値より大きいです.
4)k<=|A 1|の場合、k番目の最小要素はA 1に必ずあり、この場合にはquciksort(A 1,k)に戻ります.k=1＋124; A 1|なら、ハブ元はK番目の要素です.私たちはそれを返します.そうでなければ、k番目の最小要素は、|A 2|の中にあり、A 2の中の第(k-124; A 1|-1)番目の最小要素であると、再帰的に呼び出してquicksort(A 2,k-124; A 1|-1)に戻ります.

  #define Cutoff ( 10 )

        void
        Qselect( ElementType A[ ], int k, int Left, int Right )
        {
            int i, j;
            ElementType Pivot;

/* 1*/      if( Left + Cutoff <= Right )
            {
/* 2*/          Pivot = Median3( A, Left, Right );
/* 3*/          i = Left; j = Right - 1;
/* 4*/          for( ; ; )
                {
/* 5*/              while( A[ ++i ] < Pivot ){ }
/* 6*/              while( A[ --j ] > Pivot ){ }
/* 7*/              if( i < j )
/* 8*/                  Swap( &A[ i ], &A[ j ] );
                    else
/* 9*/                  break;
                }
/*10*/          Swap( &A[ i ], &A[ Right - 1 ] );  /* Restore pivot */

/*11*/          if( k <= i )
/*12*/              Qselect( A, k, Left, i - 1 );
/*13*/          else if( k > i + 1 )
/*14*/              Qselect( A, k, i + 1, Right );
            }
            else  /* Do an insertion sort on the subarray */
/*15*/          InsertionSort( A + Left, Right - Left + 1 );
        }

このアルゴリズムが終了すると、k番目の小さい要素は配列のk番目の位置にあります.