Partial sorting: nth elements having preseved order

Question

The task is to partially sort a vector with duplicates s.t. the median (nth-element) is at the position it would be, if the vector were sorted. All smaller elements should be on the left, all larger elements on the right. All elements with value same as median have to be in original order - but only these not the rest of the elements.

How would you solve this?

My initial solution:

1. Use std::nth_element() to find median element
2. traverse vector and sort only the elements with same value as median with respect to their index. How would I do this efficiently?

Answer 1

Use partition or stable_partition (to preserve original order).

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