問題
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] を交換
数列 を読み込んで、昇順に並び変えて出力してね。
疑似コード 7 行目 i と minj が異なって実際に交換された回数も出力してね。
制約
サンプル
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
考察
丁寧にやるだけ。
コード
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;
}