読者です 読者をやめる 読者になる 読者になる

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でそれが実装されていることに気付いた(無意識でよくやる)
  • バブルソートの交換回数反転数転倒数と呼ばれ,数列の乱れの指標になる