#include <iostream>
#include <deque>
#include <algorithm>
namespace
{
typedef std::deque<int> array;
}
class number_max
{
public :
void operator()(std::deque<int>& n, int swaps)
{
// no elements in array
if(n.empty()) return;
nmax(n, swaps);
}
private :
void nmax(std::deque<int>& n, int& swaps)
{
// Scan from beginning and get the maximum value in swaps number of elements, swap this value with the last unvisited digit
for(size_t n_i(0), n_size(n.size()); (n_i < n_size) && (swaps > 0); ++n_i)
{
// get maximum value in the range [unvisited (n_i), element accessible by remaining number of swaps (n_i + swaps + 1) )
size_t imax(get_max(n_i, n_i + swaps + 1, n));
/*
* if the maximum index is same as the digit unvisited (n_i), then no need to swap as it is already in it's currect position. If not same, then we need to swap
* and reduce the number of remaining allowed swaps
*/
if(imax != n_i) { swap(n[imax], n[n_i]); swaps -= imax; }
}
}
size_t get_max(size_t start, const size_t& end, const std::deque<int>& n)
{
size_t imax(start);
for(size_t s(n.size()); (start < end) && (start < s); ++start)
{ if(n[imax] < n[start]) imax = start; }
return imax;
}
void swap(int& first, int& second)
{
first ^= second;
second ^= first;
first ^= second;
}
};
int main()
{
array a{2, 5, 1, 9, 3, 7, 2, 8, 9, 3};
int swaps(5);
number_max()(a, swaps);
for(const int& e : a) std::cout << e;
return 0;
}