[C/C++] 백준 #1377 버블 소트(안정적 정렬)

이번 문제는 난이도 Gold V입니다.  저는 이런 문제를 좋아합니다.  알고리즘의 기본을 잘 이해하는지 물어보는 문제이기도 하니까요.  정렬은 알고리즘을 배우면서 가장 먼저 배우는 알고리즘이기도 합니다만, 기본을 충실하게 알고 있는 사람은 많지 않습니다.

 

https://www.acmicpc.net/problem/1377

1377번: 버블 소트

 

대부분 기본정렬은 선택정렬, 삽입정렬, 버블정렬이 있고, 고급정렬은 병합정렬, 힙정렬, 퀵정렬이 있고, 기본정렬은 \(O(N^2)\)이고, 고급정렬은 \(O(N \log N)\)의 성능을 가지고 있다는 것을 배웁니다.  또한 비 비교정렬로 라딕스 정렬 등이 있는 것을 배우죠.

 

정렬에는 또 한가지 중요한 것이 있는데, 바로 같은 값을 가지고 있는 경우에 대처입니다.  같은 값을 가지고 있는 경우 입력 순서를 지키고 있다면 안정적 정렬(stable sort)이라고 합니다.  안정적 정렬은 기본정렬 3가지와 고급정렬 중에는 병합정렬이 가능합니다.  비 비교정렬의 경우에는 순서를 잘 지켜주면, 안정적 정렬이 가능합니다.

 

힙정렬과 퀵정렬을 이용해서도 안정적 정렬을 가능하게 할 수도 있습니다.  예를 들어서 3, 2, 7, 2, 4 와 같이 같은 값을 가지고 있는 수열이라면, 이것을 인덱스와 같이 결합하여, (3, 0), (2, 1), (7, 2), (2, 3), (4, 4) 형태로 비교할 수 있습니다.  비교횟수가 증가하기는 하지만, 같은 값을 가지고 있는 숫자가 많지 않다면, 크게 문제가 되지 않습니다.  단지 공간효율이 떨어질 뿐입니다.

 

Bubble Sorting

 

문제를 풀기 위해서는 일단 버블 정렬의 알고리즘 이해가 필요합니다.  문제에서 주어진 버블정렬은 다음과 같습니다.

 

bool change = false;
for (int i=1; i<=n+1; i++) {
    change = false;
    for (int j=1; j<=n-i; j++) {
        if (a[j] > a[j+1]) {
            change = true;
            swap(a[j], a[j+1]);
        }
    }
    if (change == false) {
        cout << i << '\n';
        break;
    }
}

 

버블정렬에서 데이터가 더이상 바뀌지 않는 상태(즉, 정렬된 상태)가 되면, 루프를 도는 것을 멈추고, 그 때의 i값을 출력하는 코드입니다.

 

예를 들어서 3, 7, 1, 4, 6, 2, 5 라는 수열이 있다고 한다면, 이 수열을 버블정렬을 하면 다음과 같이 됩니다.

 

3

7

1

4

6

2

5

 

첫번째 교환이 이루어지면 다음과 같이 됩니다.  가장 큰 수인 7이 맨 오른쪽으로 이동을 합니다.

 

3

1

4

6

2

5

7

 

바뀐 내용을 보면 가장 큰 수의 오른쪽에 있는 숫자들이 한칸씩 모두 옮겨오게 되었습니다.  사실 그보다는 더 복잡하게 움직이게 되는데,   큰수가 오른쪽으로 이동하다가 더 큰수를 만나면, 그 수의 이동은 멈추고, 더 큰 수가 오른쪽으로 움직이게 됩니다.

 

두번째 교환은 다음과 같습니다.

 

1

3

4

2

5

6

7

 

3이 오른쪽으로 이동하다가 4를 만나면, 4가 이동을 하게 되고, 다시 6을 만나면, 6이 이동을 해서 6번째에 자리잡게 됩니다.  6은 현재 비교해야 하는 수열 중 가장 큰 수입니다.

 

세번째 교환은 다음과 같습니다.

 

1

3

2

4

5

6

7

 

네번째 교환은 다음과 같습니다.

 

1

2

3

4

5

6

7

 

정렬이 완료되었기 때문에 그 다음에는 교환이 발생하지 않아서 이때의 i값이 출력됩니다.

 

이렇게 보면 버블정렬을 직접 구현하지 않으면 풀지 못 할 것 같습니다.  여기서 큰 값 이동을 생각했지만, 매 스텝마다 큰 값은 여러번 이동할 수 있지만, 반대로 작은 값은 최대 한칸씩밖에 못 움직입니다.

 

1을 보면, 첫번째와 두번째 교환에서 각각 한칸씩 두번 움직입니다.

2를 보면, 첫번째와 두번째, 세번째, 네번째 교환에서 각각 한칸씩 네번 움직입니다.

3은 오른쪽으로 한칸.  4는 왼쪽으로 한칸, 오른쪽으로 한칸입니다.  5는 왼쪽으로 두칸.

 

여기서 네번째 교환까지 간 이유는 2때문입니다.  왼쪽으로 한칸씩 계속 움직여서 자신의 자리로 들어가면 이후는 움직이지 않습니다.  오른쪽으로 움직이는 경우가 발생하기 위해서는 2보다 작은 1이 반드시 오른쪽에 있어야 합니다.  그러면 최대로 움직이는 횟수를 좌우하는 것은 1이 됩니다.

 

그래서 이 문제는 모든 수에 대해서 자신의 자리로 돌아가기 위해서 왼쪽으로 얼마나 많이 가야 하는가입니다.  그렇게 하기 위해서는 인덱스를 가지고 정렬을 한 다음, 이 때의 정렬은 고급정렬이 필요합니다.  기본정렬을 쓸거라면, 버블정렬 코딩을 이용해서 출력하는 것이 더 유리합니다.

 

전 따로 안정적 정렬을 구현하지 않고, STL에 있는 stable_sort를 이용해서 구현했습니다.

 

제가 작성한 소스입니다.  참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1377 - Bubble Sort
//    - by Aubrey Choi
//    - created at 2019-12-27
//----------------------------------------------------------
#include <stdio.h>
#include <algorithm>

int v[500000], d[500000];
bool cmp(int a, int b) { return v[a]<v[b]; }
int main()
{
  int i, n, max=0;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",v+(d[i]=i));
  std::stable_sort(d,d+n,cmp);
  for(i=0;i<n;i++) max=(d[i]-i>max)?d[i]-i:max;
  printf("%d\n",max+1);
}