Bubble Sort - related problems. ( writing )

#1. Count the number of outer loops.

버블 소트에서의 바깥 루프 세기.

약간 최적화된 버블 소트에서의 바깥 루프가 얼마나 도는지 세는 문제입니다.

아래 문제를 보세요 ( 출처 : http://www.acmicpc.net/problem/1377 ).

int i;

for ( i=1; i<=N; i++ ) {

int working = 0;

for ( int j=1; j<=N-i; j++ ) {

if ( arr[j] > arr [j+1] ) {

swap ( arr[j], arr[j+1] );

working = 1;

}

}

if ( !working ) break;

}

printf ( "%d\n", i );

여기서 과연 몇이 출력될까요?

잘 생각해보면 정말 간단합니다.

한 번의 루프마다, 가장 작은 원소는 한 칸씩 왼쪽으로 가죠?

간단하게 생각해보세요, 가장 큰 것부터 맨 오른쪽으로 움직이는데,

그 과정에서 작은건 왼쪽으로 한 칸씩 움직이잖아요.

그러니까 답은 간단하게,

"자기 자신이 "있어야 할" 자리와, 현재 자리의 차이" 의 최댓값 입니다.

#2. Count the number of swaps.

버블 소트에서의 스왑 횟수 세기.

이건 아까의 문제보다 약간 더 복잡합니다.

생각이 복잡한건 아닌데, 코딩이 복잡하죠 ㅋㅋ

두 가지의 풀이법이 있는데,

하나는 Binary Indexed Tree ( Low Bit라고도 부르더군요 ) 를 이용한 풀이,

다른 하나는 Merge Sort를 이용한 풀이입니다.

(작성중)