ALDS1_2_A: Bubble Sort
この問題は『プログラミングコンテストのためのアルゴリズムとデータ構造(渡部有隆著,Ozy・秋葉拓哉協力)』を読んで解きました.
問題
- URL: Bubble Sort | Aizu Online Judge
- 要約: 昇順にバブルソートを行い,整列後の数列と交換した回数を求めよ
ソースコード
#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でそれが実装されていることに気付いた(無意識でよくやる)
- バブルソートの交換回数は反転数,転倒数と呼ばれ,数列の乱れの指標になる