Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
数列Aを読み込み、選択ソートのアルゴリズムで昇順に並び替え出力するプログラムです。
・問題
選択ソートは、各計算ステップで1つの最小値を「選択」していく、直観的なアルゴリズムです。
数列Aを読み込み、選択ソートのアルゴリズムで昇順に並び替え出力するプログラムを作成してください。
上の疑似コードに従いアルゴリズムを実装してください。
疑似コード 7 行目で、i と minj が異なり実際に交換が行われた回数も出力してください。
・入力される値
入力の最初の行に、数列の長さを表す整数 N が与えられます。
2行目に、N 個の整数が空白区切りで与えられます。
・期待する出力
出力は 2 行からなります。
1行目に整列された数列を 1 行に出力してください。
数列の連続する要素は1つの空白で区切って出力してください。
2 行目に交換回数を出力してください。
・条件
1 ≤ N ≤ 100
0 ≤ A の要素 ≤ 100
僕が作成、提出したコードは、以下のとおりです。
/* ALDS1_2_B Selection Sort http://judge.u-aizu.ac.jp/ 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<stdio.h> void SelectionSort(int a[],int n){ int loop,loop2,swap,min; int c=0; for(loop=0;loop<n;loop++){ min=loop; for(loop2=loop;loop2<n;loop2++){ if(a[loop2]<a[min]){ min=loop2; } } if(loop!=min){ swap=a[loop]; a[loop]=a[min]; a[min]=swap; c++; } } for(loop=0;loop<n;loop++){ printf("%d",a[loop]); if(loop==n-1){ printf("\n%d\n",c); }else{ putchar(' '); } } } int main(void){ int n,loop,a[101]; scanf("%d",&n); for(loop=0;loop<n;loop++){ scanf("%d",&a[loop]); } SelectionSort(a,n); return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_2_B Selection Sort