Szukałem na std :: nth_element algorytm, który najwyraźniej:Jaka jest praktyczna różnica między std :: nth_element a std :: sort?
zmienia kolejność elementów w przedziale [pierwszy i ostatni), w taki sposób, że element w uzyskanej pozycji n jest element, który w tej pozycji byłby w tej pozycji uporządkowany, przy czym żaden z elementów nie byłby większy i żaden z elementów po nim nie byłby mniejszy niż on. Ani elementy poprzedzające go, ani następujące po nim elementy nie mogą być uporządkowane.
Jednak z mojego kompilatora, uruchamiając następujące:
vector<int> myvector;
srand(GetTickCount());
// set some values:
for (int i = 0; i < 10; i++)
myvector.push_back(rand());
// nth_element around the 4th element
nth_element (myvector.begin(), myvector.begin()+4, myvector.end());
// print results
for (auto it=myvector.begin(); it!=myvector.end(); ++it)
cout << " " << *it;
cout << endl;
zawsze zwraca całkowicie posortowaną listę liczb całkowitych w dokładnie taki sam sposób, jak std :: sort robi. Czy czegoś brakuje? Do czego jest przydatny ten algorytm?
EDIT: Ok następujący przykład stosując znacznie większy zestaw pokazuje, że nie jest dość różnica:
vector<int> myvector;
srand(GetTickCount());
// set some values:
for (int i = 0; i < RAND_MAX; i++)
myvector.push_back(rand());
// nth_element around the 4th element
nth_element (myvector.begin(), myvector.begin()+rand(), myvector.end());
vector<int> copy = myvector;
std::sort(myvector.begin(), myvector.end());
cout << (myvector == copy ? "true" : "false") << endl;
Tylko dlatego, że implementacja wydaje się robić to za proste przykłady, nie oznacza, że zawsze to robi, ani że wszystkie inne implementacje to robią. – PlasmaHH
Jaki kompilator, jaka implementacja biblioteki? Wypróbuj większe tablice w liczbie 10000. –
Używanie "sortowania" wewnętrznie jako aliasu dla 'nth_element' spełnia formalną regułę. –