버블정렬(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단계를 수행하는 것을 볼 수 있습니다.
이렇게 이미 정렬되어 있는경우, 필요 없는 비교를 수행하지 않고 정렬을 종료하기 위해, 정렬이 완료된 시점을 알아야 합니다.
정렬이 완료된 단계가 몇번째 단계인지를 출력하는 프로그램을 작성해 보세요.