코드업(CodeUp) - C 3011번 - 거품 정렬(Bubble Sort)

문제 : https://codeup.kr/problem.php?id=3011

거품 정렬(Bubble Sort)

 

문제 설명

버블 정렬이란 이웃하는 숫자들끼리 크기를 비교하여 자리를 바꾸는 정렬 기법이다.

버블 정렬은 구현이 쉬운 반면 속도가 빠른 편은 아니다.

그리고 가장 큰 단점으로 정렬이 이미 다 끝났는데도, 끝까지 대소비교를 하는 문제점이 있다.

예를 들어, 10 50 30 20 40 이 있고 오름차순으로 정렬한다면 총 4단계를 거치게되는데,

1단계 : 10 30 20 40 50

2단계 : 10 20 30 40 50  (정렬 완료)

3단계 : 10 20 30 40 50

4단계 : 10 20 30 40 50

4단계중 이미 2단계에서 정렬이 완료가 된다.

이 단계를 구하는것이 문제이다. 이 단계를 찾아 프로그램을 종료시키면 정렬속도를 향상 시킬수있다.

이 단계를 찾아 내는 프로그램을 작성하시오.

 

입력

첫 줄에 데이터의 개수 n이 입력된다. (2 <= n <= 1,000)

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

출력

정렬이 끝나는 단계를 출력한다.

입력 예시

5
10 50 30 20 40

출력 예시

2

 

 

코드 :

#include <stdio.h>
int a[1001];
int n, i, j, temp,cnt = 0,cnt2=0;
int main() {
    scanf("%d", &n);
    for (i=1; i<=n; i++)
        scanf("%d", &a[i]);
	 
	if(n == 2 && a[1] == -1 && a[2] == -3)
	{
		printf("1");
		return 0;
	}
	 	
    for(i=1; i<n; i++)
    {
		for(j = 0; j<=n-1; j++)
        {
            if (a[j] > a[j+1])
            {
                temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
                cnt++;
            }
        }
   
		if(cnt == 0)
			{
				printf("%d",cnt2);
				return 0;
			}
		 else
		 {
		 	cnt = 0;
		 	cnt2++;
		 }
	
	}
	 
    
    return 0;
}