2021.1.20.(목) ~ 1.21.(금) 에 SFPC가 열립니다. 자세한 사항은 11월에 학교로 안내될 공문을 참고해주세요.
문제1372--버블정렬의 용솟음

1372: 버블정렬의 용솟음

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MB

제출
문제 설명
가장 앞의 두 원소를 비교하여 큰 원소가 앞에 있으면 바꾸고, 그 다음 원소들끼리 비교하여 필요하면 바꾸고, 그 다음... 그 다음... 마지막까지...
그러면 가장 큰 원소가 제일 뒤로 가게 된다.
그 다음에는 제일 뒤로 가게 된 원소를 제외하고 같은 작업을 실시한다.
그 다음에는 제일 뒤에서 두 번째 원소까지 제외하고 또 같은 작업을 실시한다.
그 다음... 또... 또... 또...

가장 큰 원소가 밑에서부터 위로 점점점 올라가는 모습이 물속의 공기방울이 뽀글뽀글 위로 올라가는 것 같다 하여 버블정렬이라 부른다.
어떤 원소는 강력한 힘을 바탕으로 가장 밑바닥에서 가장 마지막까지 치고 올라가기도 한다.
정렬 과정 중에서 연속적으로 가장 많이 올라가는 원소는 몇 걸음을 올라갔는지 구해보자.
입력 설명
첫째 줄에 원소의 갯수 n(1 <= n <= 1,000)
둘째 줄에 n개의 원소(1 <= 원소 <= 10,000)


출력 설명
연속적으로 가장 많이 치고 올라간 거리
입력 예시 복사
5
7 9 5 3 1 
출력 예시 복사
4
도움
배열 a에서 index 0부터 index n-1까지 n개의 원소를 비내림차순(오름차순) 정렬하는 버블정렬 알고리즘은 다음과 같다.
void bubble(int a[], int n) {
    for(int i=n-1; i>0; i--) {
        for(int j=0; j<i; j++) {
            if(a[j] > a[j+1]) {
                int t = a[j];
                a[j] = a[j+1];
                a[j+1] = t;
            }
        }
    }
}
출처/분류