ALDS1_2_B: Selection Sort
この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造(渡部有隆著,Ozy・秋葉拓哉協力)』を読んで解きました.
問題
- URL: Selection Sort | Aizu Online Judge
- 要約: 選択ソートを行い,整列後の数列と最低限の交換回数を求めよ
ソースコード
- AOJ: AIZU ONLINE JUDGE: Code Review
- GitHub: AOJ/ALDS1_2_B_Selection-Sort.cpp at master · canon4444/AOJ · GitHub
- ソースコード:
#include <iostream> #include <cstdio> using namespace std; int selectionSort(int A[], const int N) { int cnt = 0; for( int i = 0; i < N; ++i ){ int min = i; //iより後でA[i]より最も小さい値の添字を求める for( int j = i; j < N; ++j ) if( A[j] < A[min] ) min = j; //iとminが異なれば交換 if( i != min ){ swap(A[i], A[min]); ++cnt; } } return cnt; } int main() { int N; scanf("%d", &N); int A[N]; for( int i = 0; i < N; ++i ) scanf("%d", &A[i]); int cnt = selectionSort(A, N); for( int i = 0; i < N; ++i ){ if( i ) printf(" "); printf("%d", A[i]); } printf("\n%d\n", cnt); return 0; }