[Codeup] 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단계에서 정렬이 완료가 된다.

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

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

 

아이디어

버블 정렬 알고리즘의 코드를 효율적으로 짜는 것과 관련이 있습니다.

비효율적으로 작성한 버블 정렬은 이미 정렬이 끝난 상황을 구분하지 못하는데요.

위 문제의 예시처럼 2단계에 정렬이 끝났어도 4단계까지 프로그램이 실행되는 불필요한 과정을 거칠 수 있습니다.

이 비효율을 해결하는 것이 결국 이 문제를 풀 수 있는 아이디어입니다.

 

소스코드에서 정렬은 특정 조건(if문)을 만족할 때 주어진 리스트의 원소끼리 swap을 함으로써 이루어집니다.

그렇다면 이미 정렬이 되어 있어 특정 조건을 만족하지 않는다면 swap을 하지 않을 것입니다.

이를 이용하여 특정 단계에서 swap 여부를 판단해 반복문으로부터 break를 실행하고

그 상황에서의 단계를 출력하면 됩니다.

 

소스코드

 

#include <iostream>
using namespace std;
int n,inp[1001],cnt;
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++) scanf("%d",&inp[i]);

    for(int i=1;i<=n;i++)
    {
        cnt=i;
        bool check=0;//swap 여부를 check이 0인지 1인지로 판단
        for(int j=2;j<=n-1;j++)
        {
            if(inp[j]<inp[j-1])
            {
                swap(inp[j-1],inp[j]);
                check=1;//check 변경
            }
        }
        if(check==0) break;//swap이 실행되지 않았다면
    }
    
    if(cnt==1) printf("1");
    else printf("%d",cnt-1);
    return 0;
}