C ++ nth_element（STL nth_element）ソートアルゴリズムの詳細

C Nth_element Sorting Algorithm Detailed

nth_element（）のアルゴリズムはpartial_sort（）とは異なります。アプリケーションの範囲は、その1番目と3番目のパラメーターによって指定されます。 2番目のパラメーターは、n番目の要素へのイテレーターです。この範囲の要素が完全に順序付けられている場合、nth_dement（）を実行すると、n番目の要素が適切な位置に配置されます。この範囲内では、n番目の要素の前の要素はn番目の要素よりも小さく、それ以降のすべての要素はそれよりも大きくなります。この結果を生成するために、デフォルトでアルゴリズムが使用されます< Operator。

nth_elemen（）を使用した例を次に示します。

std::vector numbers {22, 7, 93, 45, 19, 56, 88, 12, 8, 7, 15, 10} size_t count {5} // Index of nth element std::nth_element(std::begin(numbers), std::begin(numbers) + count, std::end(numbers))

ここでのn番目の要素はnumbersコンテナの16番目の要素であり、numbers [5]に対応します。図1は、その仕組みを示しています。

図1nth_element（）アルゴリズムの操作

n番目の要素の前の要素はすべてそれよりも小さいですが、順番に並べる必要はありません。同様に、n番目の要素の後の要素はすべてそれよりも大きくなりますが、順序付けする必要はありません。 2番目のパラメーターが3番目のパラメーター（要素セクションの終わり）と同じである場合、このアルゴリズムは無効です。

この章の前半のアルゴリズムと同様に、比較関数を関数の4番目のパラメーターとして自分で定義できます。

std::nth_element(std::begin(numbers), std::begin(numbers) + count, std::end(numbers) , std::greater())

ここで使用>演算子を使用して関数を比較するため、要素が降順で並べ替えられた後、n番目の要素がn番目の要素になります。 n番目の要素の前の要素はすべてそれより大きく、その後の要素はすべてそれより小さくなります。数値コンテナの初期値が以前と同じである場合、結果は次のようになります。

45 56 93 88 22 19 10 12 15 7 8 7

システムでは、n番目の要素の両側の要素の順序が異なる場合がありますが、左側の要素はそれより大きく、右側の要素はそれより小さくする必要があります。