Sorting - (2)

버블 정렬 프로그램 (백준 1377번, 시간 제한: 2초)

문제
버블 소트 알고리즘을 다음과 같이 C++로 작성했다.

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

위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.
위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.

입력
첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력
정답을 출력한다.

입력 예시
5
10
1
5
2
3

출력 예시
3

코드 예시

import sys
input=sys.stdin.readline
n=int(input())
a=[]
for i in range(n):
    a.append((int(input(),i)))
Max=0
sort_a=sorted(a)
for i in range(n):
    if Max<sort_a[i][1]-i:#정렬 전 index-정렬 후 index
        Max=sort_a[i][1]-i
print(Max+1)

해당 문제는 시간 제한이 2초인 반면 n이 50만 이기 때문에 O(n^2) 으로 문제를 해결하지 못한다.

그래서 기본 내장 함수인 sorted 함수를 써서 O(nlogn) 시간복잡도가 필요하다.

idea는 sorting을 했을 때 이전 index 와 sorting 후 index 를 비교하는 것이다.
둘을 빼게 된다면 이동한 index 가 나오는데 양수일 경우 오른쪽에서 왼쪽으로 이동한 경우이다.

bubble sort 특성상 항상 오른쪽 끝부터 채워지기 때문에, 최대 오른쪽에서 왼쪽 이동한 것을 찾는다면 그 다음 for문 이후로는 sorting 과정이 필요 없이, 이미 sorting 되어 있다는 것을 알 수 있다. 즉 break를 걸어도 상관 없다는 뜻이다.

=> Bubble sort 의 개념을 완벽히 이해해야만 풀 수 있는 생각보다 어려운 문제였다..