Сортировка массива "сменой мест" за один проход

void part_123(unsigned a[], unsigned n)
{
  unsigned dst1 = 0, dst3 = n;
  
  for (unsigned i = 0; i < dst3; )
    if (a[i] == 1)
      std::swap(a[dst1++], a[i++]);
    else if (a[i] == 3)
      std::swap(a[--dst3], a[i]);
    else
    {
      assert(a[i] == 2);
      ++i;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
 
std::vector<unsigned> vct({ 3,3,1,3,1,1,3,2,2,2 }); // массив
 
// ф-ция упорядочения на основе принципа «смены мест»
void partition()
{
    unsigned i{}, j{ vct.size() - 1 };
    for ( ; i < j; ++i)
    {
        if (vct[i] != vct.front())
            break;
    }
    if (i == j)
        return;
    if (vct[j] == vct[i - 1])
    {
        std::swap(vct[j], vct[i]);
        while (vct[i] == vct.front())
            ++i;
        while (vct[j] == vct.back())
            --j;
    }
    for ( ; j > i; --j)
    {
        if (vct[j] != vct.back())
            break;
    }
    for (int k = i; k <= j; )
    {
        if (vct[k] == vct.front() || vct[k] == vct.back())
        {
            while (k <= j && (vct[k] == vct.front() || vct[k] == vct.back()))
            {
                if (vct[k] == vct.front())
                {
                    std::swap(vct[k], vct[i]);
                    while (vct[i] == vct.front())
                        ++i;
                    k = i;
                }
                if (vct[k] == vct.back())
                {
                    std::swap(vct[k], vct[j]);
                    while (vct[j] == vct.back())
                        --j;
                    while (vct[i] == vct.front())
                        ++i;
                    k = i;
                }
            }
        }
        else
        {
            ++k;
        }
    }
}
 
int main()
{
#if 0
    // тест для одного конкретного массива
    for (auto val : vct)
    {
        std::cout << val << " ";
    }
    std::cout << "\n\n";
    partition();
    for (auto val : vct)
    {
        std::cout << val << " ";
    }
    std::cout << "\n\n";
#else
    // тест для пяти рандомных массивов
    std::mt19937 eng{ (unsigned)time(nullptr) };
    std::uniform_int_distribution uid{ 1,3 };
    for (int i = 0; i < 5; ++i)
    {
        for (auto& val : vct)
        {
            val = uid(eng);
            std::cout << val << ",";
        }
        std::cout << "\n";
        partition();
        for (auto val : vct)
        {
            std::cout << val << " ";
        }
        std::cout << "\n\n";
    }
    
#endif
}