B - Selection Sort

問題

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_B

問題文

選択ソート。各ステップで、未ソート部分の最小値を選んで、前に持ってくる。
疑似コードは以下の通り。

selectionSort(A, N) // N個の要素を含む0-オリジンの配列A
  for i が 0 から N-1 まで
    minj = i
    for j が i から N-1 まで
      if A[j] < A[minj]
        minj = j
    A[i] と A[minj] を交換

数列 $A$ を読み込んで、昇順に並び変えて出力してね。
疑似コード 7 行目 i と minj が異なって実際に交換された回数も出力してね。

制約

• $1 \le N \le 100$
• $0 \le A_i \le 100$

サンプル

I/O 1

6
5 6 4 2 1 3

1 2 3 4 5 6
4

I/O 2

6
5 2 4 6 1 3

1 2 3 4 5 6
3

考察

丁寧にやるだけ。

コード

https://onlinejudge.u-aizu.ac.jp/status/users/a01sa01to/submissions/1/ALDS1_2_B/judge/6379637/C++17

int cnt = 0;

void selectionSort(vector<int>& a, int n) {
  rep(i, n) {
    int minj = i;
    for (int j = i; j < n; ++j) {
      if (a[j] < a[minj]) minj = j;
    }
    if (i != minj) {
      swap(a[i], a[minj]);
      ++cnt;
    }
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  selectionSort(a, n);
  rep(i, n) cout << a[i] << (i == n - 1 ? "\n" : " ");
  cout << cnt << endl;
  return 0;
}