4541 - Bubble Sort

• Submit
• Status
• Discuss
• Summary

Description

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

Bubble Sort로 배열을 오름차순으로 정렬한 결과와 교환 횟수를 구해보자. 

어느 방향으로 정렬해도 상관없으나, 이 문제에서는 앞에서부터 검사하여 최댓값을 맨 뒤로 보내는 방법으로 정렬한다.

Input

* Line 1 : 정렬할 배열 갯수 N (1≤N≤1000)

* Line 2~N+1 : 배열 arr의 크기 n이 입력되고 그 뒤로 배열 arr의 원소들이 공백으로 구분되어 입력된다. (1 ≤ n ≤ 100, -2000 ≤ arr[i] ≤ 2000)

Output

* Line 1~N : 정렬 중의 교환 횟수와 정렬 결과가 공백으로 구분되여 한 줄로 출력한다.

Sample Input

3
3 0 2 1
4 4 3 2 1
7 1 5 3 3 2 6 4

Sample Output

1 0 1 2
6 1 2 3 4
7 1 2 3 3 4 5 6

Hint

{3, 4, 1, 2} 를 Bubble Sort로 정렬하기

1~4번째 요소 검사하기:

    3<4이므로 교환안함

    4>1이므로 교환(1회) -> {3, 1, 4, 2}

    4>2이므로 교환(2회) -> {3, 1, 2, 4}

1~3번째 요소 검사하기:

    3>1이므로 교환(3회) -> {1, 3, 2, 4}

    3>2이므로 교환(4회) -> {1, 2, 3, 4}

1~2번째 요소 검사하기:

    1<2이므로 교환안함

{3, 4, 1, 2}를 Bubble Sort로 정렬하면 교환은 총 4번 발생한다.