Cycle Sort

    1#include <bits/stdc++.h>
    2using namespace std;
    3 
    4int n;
    5vector<int> arr;
    6 
    7// put the right numbers after 1
    8vector<int> solve1(vector<int> a) {
    9    a.insert(a.end(), a.begin(), a.end());
    10    int idx1 = find(a.begin(), a.end(), 1) - a.begin();
    11    vector<int> b(a.begin() + idx1, a.end());
    12    for (int i = 0; i < n; i++) {
    13        if (b[i] != i + 1) {
    14            int miss = find(b.begin(), b.end(), i + 1) - b.begin();
    15            swap(b[i], b[miss]);
    16            break;
    17        }
    18    }
    19    b.resize(n);
    20    return b;
    21}
    22 
    23// move the 1 in front of the 2
    24vector<int> solve2(vector<int> a) {
    25    int pos2 = find(a.begin(), a.end(), 2) - a.begin();
    26    int pos1 = find(a.begin(), a.end(), 1) - a.begin();
    27    // swap 1 into the slot just before 2
    28    swap(a[(pos2 - 1 + n) % n], a[pos1]);
    29    // rotate so that 1 is at front
    30    int start = find(a.begin(), a.end(), 1) - a.begin();
    31    vector<int> b;
    32    b.reserve(n);
    33    for (int i = 0; i < n; i++)
    34        b.push_back(a[(start + i) % n]);
    35    return b;
    36}
    37// if 1 is already right after 2, just swap them
    38vector<int> solve3(vector<int> a) {
    39    int pos2 = find(a.begin(), a.end(), 2) - a.begin();
    40    vector<int> b(n);
    41    for (int i = 0; i < n; i++)
    42        b[i] = a[(pos2 + i) % n];
    43    if (b[1] == 1)
    44        swap(b[0], b[1]);
    45    return b;
    46}
    47 
    48int main() {
    49    ios::sync_with_stdio(0);
    50    cin.tie(0);
    51    cin >> n;
    52    arr.resize(n);
    53    for (int i = 0; i < n; i++)
    54        cin >> arr[i];
    55    if (n == 1) {
    56        cout << "1" << "\n";
    57        return 0;
    58    }
    59    auto a1 = solve1(arr);
    60    auto a2 = solve2(arr);
    61    auto a3 = solve3(arr);
    62    // pick lexicographically smallest
    63    vector<int> ans = min(min(a1, a2), a3);
    64    for (int i = 0; i < n; i++)
    65        cout << ans[i] << (i + 1 == n ? '\n' : ' ');
    66    return 0;
    67}
    68