寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

Aizu Online Judge in C #ALDS1_2_A Bubble Sort

Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。

・問題
 バブルソートはその名前が表すように、泡(Bubble)が水面に上がっていくように配列の要素が動いていきます。
 バブルソートは次のようなアルゴリズムで数列を昇順に並び変えます。
f:id:neguse_atama:20200423161927p:plain
 数列 A を読み込み、バブルソートで昇順に並び変え出力するプログラムを作成してください。
 また、バブルソートで行われた要素の交換回数も報告してください。

・入力される値
 入力の最初の行に、数列の長さを表す整数 N が与えられます。
 2行目に、N 個の整数が空白区切りで与えられます。

・期待する出力
 出力は 2 行からなります。
 1行目に整列された数列を 1 行に出力してください。
 数列の連続する要素は1つの空白で区切って出力してください。
 2 行目に交換回数を出力してください。

・条件
   1 ≤ N ≤ 100
   0 ≤ A の要素 ≤ 100

僕が作成、提出したコードは、以下のとおりです。

/*
 ALDS1_2_A Bubble Sort
 http://judge.u-aizu.ac.jp/
 提出コードの解答例
 https://neguse-atama.hatenablog.com
*/
#include<stdio.h>
#include<stdlib.h>
#define swap(type,x,y) do{type val=x;x=y;y=val;}while(0)
int sum=0;
void BubbleSort(int a[],int n){
    int loop,loop2;
    for(loop=0;loop<n-1;loop++){
        for(loop2=n-1;loop2>loop;loop2--){
            if(a[loop2-1]>a[loop2]){
                swap(int,a[loop2-1],a[loop2]);
                ++sum;
            }
        }
    }
}
int main(void){
    int loop,n;
    int *num;
    scanf("%d",&n);
    num=calloc(n,sizeof(int));
    for(loop=0;loop<n;loop++){
        scanf("%d",&num[loop]);
    }
    BubbleSort(num,n);
    for(loop=0;loop<n;loop++){
        printf("%d",num[loop]);
        if(loop!=n-1){
            putchar(' ');
        }else{
            putchar('\n');
        }
    }
    printf("%d\n",sum);
    free(num);
    return 0;
}

設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/
ALDS1_2_A Bubble Sort