VM
какая для случайной перестановки первых N натуральных чисел сложность сортировки следующим алгоритмом?
#include <utility>
#include <algorithm>
#include <vector>
#include <random>
#include <iostream>
int main()
{
std::vector<size_t> v(10);
std::iota(std::begin(v), std::end(v), size_t{0});
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(std::begin(v), std::end(v), g);
for (size_t i = 0; i < std::size(v); ++i) {
size_t j = v[i];
while (j != i) {
std::swap(v[j], j);
}
v[i] = j;
}
std::copy(std::cbegin(v), std::cend(v), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
}
Сейчас бы перестановку сортировать...
