Сгруппировать массив - C++

15
9 55 13 4 6 25 7 14 7 21 33 4 12 5 10

4 6 14 4 12 10 9 21 33 55 25 5 7 7 13

vector<int>massiv;
vector<int>poradok;
int n, cis;
cin >> n;
for (int i = 0; i < n; i++)
{
    cin >> cis;
    massiv.pb(cis);
}
for (int i = 0; i < massiv.size(); i++)
{
    if (massiv[i] % 2 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
    else if (massiv[i + 1] % 2 == 0)
    {
        poradok.pb(massiv[i + 1]);
        massiv.erase(massiv.begin() + (i + 1));
    }
}


for (int i = 0; i < massiv.size(); i++)
{
    if (massiv[i] % 3 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
    else if (massiv[i + 1] % 3 == 0)
    {
        poradok.pb(massiv[i + 1]);
        massiv.erase(massiv.begin() + (i + 1));
    }
}
for (int i = 0; i < massiv.size(); i++)
{
    if (massiv[i] % 5 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
}
for (int i = 0; i < massiv.size(); i++)
{
    if (massiv[i] % 7 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
    else if (massiv[i + 1] % 7 == 0)
    {
        poradok.pb(massiv[i + 1]);
        massiv.erase(massiv.begin() + (i + 1));
    }
}
for (int i = 0; i < massiv.size(); i++)
{
    if (massiv[i] % 11 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
    else if (massiv[i + 1] % 11 == 0)
    {
        poradok.pb(massiv[i + 1]);
        massiv.erase(massiv.begin() + (i + 1));
    }
}
for (int i = 0; i < massiv.size(); i++)
{
    poradok.pb(massiv[i]);
}
for (int i = 0; i < poradok.size(); i++)
{
    cout << poradok[i] << " ";
}
cout << endl;

Если применять сортировку, то могут возникнуть проблемы с "хвостом" вектора, так как тот, как я понимаю, должен оставаться не сортированным.

Прямолинейное решение - это решение с использованием стандартного алгоритма std::stable_partition, объявленного в заголовке <algorithm>.

Ниже приведена демонстрационная программа

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
int main() 
{
    std::vector<unsigned int> v = { 9, 55, 13, 4, 6, 25, 7, 14, 7, 21, 33, 4, 12, 5, 10 };
    for ( int x : v ) std::cout << std::setw( 2 ) << x << ' ';
    std::cout << std::endl;
    auto first = v.begin();
    for ( unsigned int i : { 2, 3, 5, 7, 11 } )
    {
        first = std::stable_partition( first, v.end(), [&]( unsigned int x ){ return x % i == 0; } );
    }        
    for ( int x : v ) std::cout << std::setw( 2 ) << x << ' ';
    std::cout << std::endl;
    return 0;
}

Ее вывод на консоль

 9 55 13  4  6 25  7 14  7 21 33  4 12  5 10 
 4  6 14  4 12 10  9 21 33 55 25  5  7  7 13 

Что же касается вашей программы, то циклы, подобные данному

for (int i = 0; i < massiv.size(); i++)
{
    if (massiv[i] % 2 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
    else if (massiv[i + 1] % 2 == 0)
    {
        poradok.pb(massiv[i + 1]);
        massiv.erase(massiv.begin() + (i + 1));
    }
}

являются некорректными. Во-первых, во-втором else предложении происходит выход за диапазон допустимых индексов, так как выражение i + 1 может быть равно значению, возвращаемому функцией size() . Во-вторых, при удалении элемента из вектора происходит смещение всех элементов, расположенных правее удаленного элемента, влево, а потому увеличение индекса в цикле может привести к пропуску некоторых элементов. Правильная идиома удаления элементов из вектора в цикле выглядит следующим образом

for ( std::vector<int>::size_type i = 0; i < massiv.size(); )
{
    if (massiv[i] % 2 == 0)
    {
        poradok.pb(massiv[i]);
        massiv.erase(massiv.begin() + i);
    }
    else
    {
        i++;
    }
}

Или

for ( auto it = massiv.begin(); it != massiv.end(); )
{
    if ( *it % 2 == 0 )
    {
        it = massiv.erase( it );
    }
    else
    {
        ++it;
    }
}

Можно ввести критерий сравнения, согласно которому все числа с минимальным простым делителем до 11 сортируются в соответствии с величиной делителя, а все остальным числам приписывается некий искусственный "большой" делитель (например, 12 :) ) . Далее применяем std::stable_sort и получаем требуемый порядок. Если в лоб

    #include <cassert>  
    #include <algorithm>  
    #include <iostream>
    #include <iterator>
    unsigned min_prime_factor(unsigned v)
    {
      assert(v > 0);
      unsigned i;
      for (i = 2; i <= 11; ++i)
        if (v % i == 0)
          break;
      return i;
    }
    int main() 
    {
      unsigned array[] = { 9, 55, 13, 4, 6, 25, 7, 14, 7, 21, 33, 4, 12, 5, 10 };
      std::stable_sort(std::begin(array), std::end(array), 
        [](unsigned a, unsigned b) 
          { return min_prime_factor(a) < min_prime_factor(b); });
      std::copy(std::begin(array), std::end(array),
        std::ostream_iterator<int>(std::cout, " "));
      std::cout << std::endl;
    }

Разумеется, никто вам не запрещает применить более эффективный метод поиска минимального простого делителя. И понятно что такая реализация может (и будет) заниматься поиском минимального делителя несколько раз для одного и того же значения, что в общем случае неоптимально.

Учитывая, что диапазон входных значений у вас ограничен, при необходимости не составит труда оптимизировать обработку либо путем предварительной генерации таблицы, либо (лучше?) путем мемоизации уже вычисленных факторов. Навскидку

unsigned min_prime_factor(unsigned v)
{
  assert(v > 0 && v <= 1000);
  static unsigned table[1001];
  if (table[v] == 0)
  {
    unsigned i;  
    for (i = 2; i <= 11; ++i)
      if (v % i == 0)
        break;
    table[v] = i;
  }
  return table[v];
}

Навскидку (не самым эффективным способом) - что-то вроде

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
    unsigned int N;
    cin >> N;
    vector<int> s(N);
    for(size_t i = 0; i < N; ++i)
        cin >> s[i];
    int m = 2;
    auto check = [&m](int n){ return n%m == 0;};
    while(s.size())
    {
        copy_if(s.begin(),s.end(),
                ostream_iterator<int>(cout," "),
                check);
        s.erase(remove_if(s.begin(),s.end(),check),s.end());
        m += 1 + (m > 2);
    }
    cout << endl;
}

В вам просьба - не ленитесь, писать pb вместо push_back - это уже просто неуважение к языку и самому себе...

Update

В варианте @AnT - т.е. после 11 не проверяем на делимость, а просто выводим все подряд - достаточно изменить три строчки и добавить еще одну переменную:

int main()
{
    unsigned int N;
    cin >> N;
    vector<int> s(N);
    for(size_t i = 0; i < N; ++i)
        cin >> s[i];
    int m[] = {2, 3, 5, 7, 11, 1};
    int idx = 0;
    auto check = [&m,&idx](int n){ return n%m[idx] == 0;};
    while(s.size())
    {
        copy_if(s.begin(),s.end(),
                ostream_iterator<int>(cout," "),
                check);
        s.erase(remove_if(s.begin(),s.end(),check),s.end());
        ++idx;
    }
    cout << endl;
}

Вот еще более короткое и эффективное решение...

int main()
{
    unsigned int N;
    cin >> N;
    vector<int> s(N);
    for(size_t i = 0; i < N; ++i)
        cin >> s[i];
    int m[] = {2, 3, 5, 7, 11, 1};
    int idx = 0;
    while(s.size())
    {
        s.erase(remove_if(s.begin(),s.end(),
                          [&m,&idx](int n)
                          { return (n%m[idx]) ? false :
                              (cout << n << " ", true); }),
                          s.end());
        ++idx;
    }
    cout << endl;
}

При отсутствии поддержки C++11 - например, так (берет даже Open Watcom):

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;
int m[] = {2, 3, 5, 7, 11, 1};
int idx = 0;
bool pred(int n)
{
    return (n%m[idx]) ? false : (cout << n << " ", true);
}
int main()
{
    unsigned int N;
    cin >> N;
    vector<int> s(N);
    for(size_t i = 0; i < N; ++i)
        cin >> s[i];
    while(s.size())
    {
        s.erase(remove_if(s.begin(),s.end(),pred),s.end());
        ++idx;
    }
    cout << endl;
}