Частичная сортировка: n-ые элементы, имеющие заданный порядок

Question

Задача состоит в том, чтобы частично отсортировать вектор с дубликатами s.t. медиана (n-й элемент) находится в положении, которое было бы, если бы вектор был отсортирован. Все меньшие элементы должны быть слева, все более крупные элементы справа. Все элементы со значениями, такими же, как медианные, должны быть в исходном порядке, но только эти не остальные элементы.

Как бы вы это разрешили?

Мое начальное решение:

1. Использование станд :: nth_element(), чтобы найти медиану элемент
2. траверс вектор и сортировать только элементы с одинаковым значением в среднем по отношению к их индексу. Как я могу сделать это эффективно?

Answer 1

Используйте раздел или stable_partition (чтобы сохранить исходный порядок).

class Predicate{ 
    int median_value; 
    public: 
    Predicate(int med) : median_value(med) {} 
    bool operator()(int x){ 
    return x < median_value; 
    } 
}; 

int main(){ 

vector<int> v{ 10, 20, 30, 10, 30}; 

int median = 20; 

cout << "median = " << median << endl; 

stable_partition(v.begin(), v.end(), Predicate(median)); 

for (auto i : v) 
    cout << i << " "; 
}