Простейший способ сортировки массива поочередно (например: T, T, F, F, F, T, F, T, F, F, F до T, F, T, F, T, F, T, F, Т, Т, Т)?

Question

Например, у меня есть вектор

vector<pair<bool,int> > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8},{false,9},{false,10},{false,11}}; 

, который я хочу, чтобы отсортировать его так, чтобы значение BOOL соседнего элемента отличается, если это возможно (значение междунар не требует сортировки) выход должен быть что-то как:

0,... 
1,... 
0,... 
1,... 
. 
. 
. 
0,... 
0,... 
0,... 

Я пытался что-то вроде этого:

sort(v.begin(),v.end()); 
for(int i=1;i<v.size()/2;i+=2){ 
    iter_swap(v.begin()+i,v.end()-i); 
} 

, но это не мой желаемый результат:

0,3 
1,8 
0,5 
1,2 
0,9 
0,10 
0,11 
1,1 
0,7 
1,6 
0,4 

есть ли какой-либо алгоритм для этого?

Answer 1

Partition массив, например:

std::vector<std::pair<bool,int> > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8},{false,9},{false,10},{false,11}}; 

auto p = std::partition(v.begin(), v.end(), [](const auto& p) { return !p.first; }); 
auto it1 = v.begin(); 
auto it2 = p; 

while(it1 != p || it2 != v.end()) { 
    if(it1 != p) { 
     std::cout << it1->first << ',' << it1->second << std::endl; 
     ++it1; 
    } 
    if(it2 != v.end()) { 
     std::cout << it2->first << ',' << it2->second << std::endl; 
     ++it2; 
    } 
} 

Answer 2

Я бы создал частотный массив и, в качестве альтернативы, взял один элемент из каждой части.

Answer 3

Переместить все элементы в вспомогательный массив, T слева, F справа (вам даже не нужно копировать логическое значение). Затем скопируйте его чередующимся образом.

С небольшой осторожностью вы можете выполнить две реорганизации на месте.

Answer 4

Вы можете иметь два итератора маршируют над последовательностью, посещения один итератор все истинные пары с первым элементом является true, другие визиты итераторов пары с первым элементом есть false. Затем распечатать значение указует итераторы в переменном порядке:

#include <iostream> 
#include <vector> 
#include <utility> 

int main() 
{ 
    std::vector<std::pair<bool,int> > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8},{false,9},{false,10},{false,11}}; 

    auto isTruePair = [](std::pair<bool, int> p) { return p.first; }; 
    auto isFalsePair = [](std::pair<bool, int> p) { return !p.first; }; 

    auto trueIt = std::find_if(v.begin(), v.end(), isTruePair); 
    auto falseIt = std::find_if(v.begin(), v.end(), isFalsePair); 

    while (trueIt != v.end() || falseIt != v.end()) { 
     if (falseIt != v.end()) { 
      std::cout << "0," << falseIt->second << '\n'; 
      falseIt = std::find_if(++falseIt, v.end(), isFalsePair); 
     } 

     if (trueIt != v.end()) { 
      std::cout << "1," << trueIt->second << '\n'; 
      trueIt = std::find_if(++trueIt, v.end(), isTruePair); 
     } 
    } 
} 

теперь я вижу, что это в основном так же, как std::partition идеи данной в @ ответе Smeeheey, за исключением, что эта версия не требует перемещения элементы вокруг.