문제 번호 : 버블 정렬(Bubble Sort)

문제 번호 : 버블 정렬(Bubble Sort)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 322  해결 문제 수: 119
[제출][채점상황][게시판][:]

문제 설명

버블정렬(Bubble Sort)은 데이터 집합을 순회하면서 집합 내의 이웃 요소들끼리의 교환을 통해 정렬을 수행하는 알고리즘으로, 데이터를 정렬하는 과정이 마치 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름입니다.

입력 : 6 4 2 3 1 5

1단계 : 4 2 3 1 5 6

2단계 : 2 3 1 4 5 6

3단계 : 2 1 3 4 5 6

4단계 : 1 2 3 4 5 6 

5단계 : 1 2 3 4 5 6

이런 버블정렬은 구현하기가 쉬운 반면, 위의 예시에서 4단계에 이미 정렬이 완료되었음에도 5단계를 수행하는 것을 볼 수 있습니다.

이렇게 이미 정렬되어 있는경우, 필요 없는 비교를 수행하지 않고 정렬을 종료하기 위해, 정렬이 완료된 시점을 알아야 합니다.

정렬이 완료된 단계가 몇번째 단계인지를 출력하는 프로그램을 작성해 보세요.

입력

첫 줄에는 정렬하고자 하는 데이터의 갯수 n이 입력된다.( 2 <= n <= 100)

둘째 줄에는 n개의 데이터가 공백을 기준으로 입력된다.

출력

정렬이 완료되는 단계를 출력한다.

입력예시

6
6 4 2 3 1 5

출력예시

4

도움말

[제출][채점상황]