02. 정렬 (Sorting Theory, c++) - Bubble Sort

Bubble Sort?

O(N^2)에 수행되는 간단한 알고리즘입니다.

짧은 두개의 중첩된 Loop로 구성됩니다.

 

Bubble Sort는 N개의 round가 있습니다. 각 round마다 배열의 요소들을 순회합니다.

두개의 정확한 순서로 배치되어 있지 않은 연속적인 요소가 발견되면 두개를 변경합니다.

아래와 같은 코드로 수행됩니다.

    REP(i, 0, N) {
        REP(j, 0, N-1) {
            if (a[j] > a[j+1]) {
                swap(a[j], a[j+1]);
            }
        }
    }

 

첫 번째 round가 끝나게 되면, 가장 큰 요소는 정확한 위치 (맨 끝)에 위치하게 됩니다.

그리고 K 번째 round가 끝나게 되면 K 번째 큰 요소는 정확한 위치에 위치하게 됩니다.

그러므로 아무리 늦어도 N round 이후에는 모든 배열은 정렬되게 됩니다.

---

Inversions

Bubble Sort는 배열 내에서 항상 연속적인 요소들을 변경합니다.

Inversion은 정렬 알고리즘을 최적화하는데 사용되는 유용한 개념입니다.

 

Inversion이란 잘못된 순서로 배열되어 있는 요소들의 쌍입니다.

예를 들면, 1 2 2 6 3 5 9 8 이라는 배열이 있을 때

(6,3) (6,5) (9,8) 이라는 3개의 Inversion이 존재하는 것입니다.

 

그리고 Inversion의 갯수는 이 배열을 정렬하기 위해서 얼마나 많은 작업을 해야하는지를 나타냅니다.

만약 Inversion이 없다면 완전하게 정렬되어 있는 상태입니다.

 

잘못된 순서로 배열된 연속적인 요소들의 쌍을 변경하는 작업은 정확하게 배열에서 1개의 Inversion을 제거합니다.