[알고리즘-이론] 버블 정렬 (Bubble Sort)

---

버블 정렬 (Bubble Sort)이란?

 

버블 정렬은 인접한 두 원소를 비교하여 큰/작은 수를 기준으로 자리를 교환하는 방식으로 정렬하는 알고리즘을 뜻한다.

 

선택정렬과 같이 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는데 제일 큰 원소를 옮기는 방법의 차이가 있다.

 

버블정렬을 간단하게 설명하자면.

라운드의 순서별로 임의의 포인터를 만들어 뒷 값과 비교를 하는 과정을 반복한다. 만약 뒷 값보다 크게되면 자리를 옮겨 그 다음 값과 비교하고 크지 않다면 포인터를 뒤로 넘겨 포인터가 정렬되지 않은 배열의 끝까지 도달했을 때 한 라운드가 종료된다.

 

pseudo 코드를 먼저 보자면

bubbleSort(A[], n){                    .... 1
    for last <- n downto 2            .... 2
        for i <- i to last - 1        .... 3
            if (A[i] > A[i+1]) then A[i] <-> A[i+1]        .... 4 
}

---

• 정렬되지 않은 배열{7, 22, 31, 4, 11, 40}이 있다고 치자. 각 정렬은 라운드를 통해 진행된다.

 

첫 번째 라운드

• *: 위치 포인터

• 최초 포인터 위치: {*7, 22, 31, 4, 11, 40}

7과 22를 비교한다 -> 7과 22중 22가 더 크므로 포인터를 22로 옮긴다. 결과: {7, *22, 31, 4, 11, 40}

22와 31을 비교한다 -> 22와 31중 31이 더 크므로 포인터를 31로 옮긴다. 결과: {7, 22, *31, 4, 11, 40}

31과 4를 비교한다 -> 31와 4중 31이 더 크므로 4와 자리 교환을 한다. 결과: {7, 22, 4, *31, 11, 40}

31과 11을 비교한다 -> 31과 11중 31이 더 크므로 11과 자리를 교환한다. 결과: {7, 22, 4, 11, *31, 40}

31과 40을 비교한다 -> 31과 40중 40이 더 크므로 포인터를 40으로 옮긴다. 결과: {7, 22, 4, 11, 31, *40}

[40 정렬 완료]

포인터의 위치가 정렬되지 않은 배열의 끝에 도달했으므로 1번째 라운드를 종료시킨다.

두 번째 라운드

• *: 위치 포인터

• 최초 포인터 위치: {*7, 22, 31, 4, 31}

7과 22를 비교한다 -> 7과 22중 22가 더 크므로 포인터를 22로 옮긴다. 결과: {7, *22, 4, 11, 31}

22와 4를 비교한다 -> 22와 4중 22가 더 크므로 4와 자리를 교환한다. 결과: {7, 4, *22, 11, 31}

22와 11을 비교한다 -> 22와 11중 22가 더 크므로 11과 자리를 교환한다. 결과: {7, 4, 11, *22, 31}

22와 31을 비교한다 -> 22와 31중 31이 더 크므로 포인터를 31로 옮긴다 결과: {7, 4, 11, 22 ,*31}

[{31, 40} 정렬 완료]

포인터의 위치가 정렬되지 않은 배열의 끝에 도달했으므로 2번쨰 라운드를 종료시킨다.

세 번째 라운드

• *: 위치 포인터

• 최초 포인터 위치: {*7, 4, 11, 22}

7과 4를 비교한다 -> 7과 4중 7이 더 크므로 4와 자리를 교환한다. 결과: {4, *7, 11, 22}

7과 11을 비교한다 -> 7과 11중 11이 더 크므로 포인터를 11로 옮긴다 결과: {4, 7 ,*11, 22}

11과 22를 비교한다 -> 11과 22중 22가 더 크므로 포인터를 22로 옮긴다 결과: {4, 7 ,11 ,*22}

[{11 22 31 40} 정렬 완료]

포인터의 위치가 정렬되지 않은 배열의 끝에 도달했으므로 3번쨰 라운드를 종료시킨다.

네 번째 라운드

• *: 위치 포인터

• 최초 포인터 위치: {*4, 7, 11}

4와 7을 비교한다 -> 4와 7중 7이 더 크므로 포인터를 7로 옮긴다. 결과: {4, *7, 11}

7과 11을 비교한다 -> 7과 11중 11이 더 크므로 포인터를 11로 옮긴다 결과: {4, 7 ,*11}

[{7 11 22 31 40} 정렬 완료]

포인터의 위치가 정렬되지 않은 배열의 끝에 도달했으므로 4번쨰 라운드를 종료시킨다.

마지막 라운드

• *: 위치 포인터

• 최초 포인터 위치: {*4, 7}

4와 7을 비교한다 -> 4와 7중 7이 더 크므로 포인터를 7로 옮긴다 결과: {4, *7}

[{4 7 11 22 31 4} 정렬 완료]

---

버블 정렬(Bubble Sort)의 시간 복잡도

위의 pseudo 코드를 봤을 때 입력 배열 A[n]이면 (n은 입력의 크기)

for 반복

• ...2 는 선택정렬의 for 루프와 같은 역할을 하고 루프를 돌 때마다 제일 큰 원소를 맨 오른쪽으로 보내고 정렬할 배열의 크기를 하나씩 줄여나간다.

• ...3 는 안쪽 루프로써 가장 큰 원소를 맨 오른쪽으로 보내는 역할을 한다. 이 부분이 선택정렬과 다르다. 선택정렬은 가장 큰 수를 찾은 다음 맨 왼쪽으로 보내는 반면, 버블정렬은 왼쪽부터 이웃한 수를 비교해가며 순서를 바꾸는 것이다.

결론: ...2 번의 for 루프에서는 n-1번 순환하고 ...3번의 for 루프에서는 last-1 번 순환하는데 last가 2까지 1씩 감소하므로 n(n-1)/2 이다. 따라서 버블정렬의 수행시간은 ∂(n^2)이다.

Best	Avg	Worst
n^2	n^2	n^2

---

버블 정렬 (Bubble Sort)의 특징

장점

• 구현이 매우 간단하다.

단점

• 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
• 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
• 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

• 일반적으로 교환이 이동보다 더 복잡하기때문에 거의 쓰지 않는다

---

버블 정렬의 최고 효율

앞에서 소개한 버블정렬 알고리즘은 알고리즘이 수행을 시작할 때나 중간에 배열이 이미 정렬이되어 있는 상태라도 계속 끝까지 무의미한 순환을 계속한다. 이를 위해 알고리즘에 한 가지 장치츨 하는 방법이 있다.

bubbleSort(A[], n){
    for last <- 2{                    .... 1
        sorted <- true;
        for i <- 1 to last - 1;{        .... 2
               if(A[i]>A[i+1]) then{        
                A[i] <-> A[i+1];        .... 3
                sorted <- false;        .... 4
            }
        }
        if(sorted = true) then return;        .... 5
    }

}

sorted <- true; 이 부분을 sorted Flag라고 칭하고 플래그가 동작하기 위해서는 ...2의 반복문을 동작시켜야 한다.

즉 정렬이 이루어지면 자동적으로 sorted 플래그가 동작하여 플래그 값을 false로 바꿔놓고 만약 ....2의 반복문이 동작하지 않으면 바로 return 하게 된다.

 

---

버블 정렬(Bubble Sort)의 자바 코드