ALDS1_2_A: Bubble Sort

AOJ AOJ本

この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造（渡部有隆著，Ozy・秋葉拓哉協力）』を読んで解きました．

　

問題

　

ソースコード

#include <stdio.h>

void bubbleSort(int A[], const int N)
{
    int i;
    int flag = 1, cnt = 0;

    while( flag ){ //ここを消して下2行でも可 (1)
    //int j;
    //for( j = 0; flag; ++j ){
        flag = 0;

        for( i = N-1; 0 < i; --i ) //ここを消して下1行でも可 (1)
        //for( i = N-1; j < i; --i )
            if( A[i] < A[i-1] ){
                int tmp = A[i];
                A[i] = A[i-1];
                A[i-1] = tmp;

                flag = 1;
                ++cnt;
            }
    }

    for( i = 0; i < N; ++i ){
        if( 0 < i ) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n%d\n", cnt);
}

int main()
{
    int i;

    int N;
    scanf("%d", &N);
    int A[N];
    for( i = 0; i < N; ++i )
        scanf("%d", &A[i]);

    bubbleSort(A, N);

    return 0;
}

　

反省点

  • flagを用意することで，一番外のループをwhile文にするのが賢い
  • 多くの本は二重for文にしている（for(i=0; i<N; ++i) for(j=N-1; i<j; --j)）
  • 私も二重for文派（for(i=0; i<N; ++i) for(j=i+1; j<N; ++j)）
  • flagを使った方が良さそう
  • 解説を読んで，jで止めた方が計算量が落ちてより賢い
  • 私のfor文ではj=i+1でそれが実装されていることに気付いた（無意識でよくやる）
  • バブルソートの交換回数は反転数，転倒数と呼ばれ，数列の乱れの指標になる