[PAT-A] 1067 Sort with Swap(0, i)

Java

import java.util.Scanner;

public class Main {
    static final int N = 100010;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] pos = new int[N];

        for (int i = 0; i < n; ++i) {
            int x = scanner.nextInt();
            pos[x] = i;
        }

        int cnt = 0;
        for (int i = 1; i < n; ) {
            while (pos[0] != 0) {
                swap(pos, 0, pos[0]);
                cnt++;
            }

            while (i < n && pos[i] == i) i++;
            if (i < n) {
                swap(pos, 0, i);
                cnt++;
            }
        }
        System.out.println(cnt);

        scanner.close();
    }

    private static void swap(int[] pos, int a, int b) {
        int temp = pos[a];
        pos[a] = pos[b];
        pos[b] = temp;
    }
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int pos[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int x;
        scanf("%d", &x);
        pos[x] = i;
    }

    int cnt = 0;
    for (int i = 1; i < n;) {
        while (pos[0] != 0) {
            swap(pos[0], pos[pos[0]]);
            cnt++;
        }

        while (i < n && pos[i] == i) i++;
        if (i < n) {
            swap(pos[0], pos[i]);
            cnt++;
        }
    }
    printf("%d\n", cnt);

    return 0;
}