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

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

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

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

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

c++ nth-element partial-sort
person aces    schedule 22.05.2015    source источник
comment
В чем проблема с вашим текущим решением?   -  person kraskevich    schedule 22.05.2015
comment
Я ищу очень эффективное решение, особенно часть 2: сортировка только определенных значений вектора по их индексам.   -  person aces    schedule 22.05.2015
comment
Как вы определяете исходный порядок, когда элементы имеют одинаковое значение? Разве это не перестановка, например. {3 3 3 3} первоначальный заказ?   -  person 463035818_is_not_a_number    schedule 22.05.2015
comment
Это k-мерный вектор vector<Point<T>>с struct Point{ num_t x,y,z, ID; };, поэтому существует исходный порядок.   -  person aces    schedule 22.05.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

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 << " ";
}
person 911    schedule 22.05.2015
comment
Это может сработать - стабильный_раздел - это среднее значение O (n), я полагаю, и худшее значение O (nlogn). Хотя мне было бы интересно: как бы вы нашли медиану? С этой опцией вам не разрешено менять порядок при нахождении медианы... верно? - person aces; 22.05.2015
comment
не рассматривал вычисление медианы в приведенном выше коде. вероятно, есть (?) интегрированный алгоритм для поиска медианы при сохранении порядка. - person 911; 22.05.2015