[Java] 버블 정렬 개념

버블 정렬은 두 인접한 요소를 비교하여 크기가 더 큰 값을 뒤로 이동시키는 방식으로 정렬하는 가장 간단한 정렬 알고리즘 중 하나이다.

이름처럼 "거품(bubble)"이 위로 올라오는 방식으로 동작하기 때문에 버블 정렬이라고 한다.

 

버블 정렬은 간단한 정렬 알고리즘으로 정렬 과정을 이해하는 데 유용하다.

하지만 배열 크기가 크거나 성능이 중요한 경우 더 효율적인 정렬 알고리즘(예: 병합 정렬, 퀵 정렬)을 사용하는 것이 좋다.

 

그럼 버블 정렬의 논리적 과정 , 코드 구현,  특징과 자주 사용되는 최적화에 대해 알아보자.

---

<1> 논리적 과정

1. 배열 탐색 :

배열의 첫 번째 요소부터 시작하여 두 인접한 값을 비교한다.

2. 교환(Swap) :

두 값 중 앞의 값이 뒤의 값보다 크다면 위치를 바꾼다. 이는 작은 값이 앞으로, 큰 값이 뒤로 이동하도록 만든다.

3. 가장 큰 값 배치 :

첫 번째 반복에서 가장 큰 값은 배열의 맨 끝에 위치한다.

4. 반복 :

위의 과정을 배열 크기만큼 반복한다. 매 반복마다 비교 대상 범위는 줄어든다.

이미 정렬된 값은 다시 비교할 필요가 없으므로 n-1,n-2...식으로 범위를 좁힌다. 

5. 정렬 완료:

배열이 완전히 정렬될 때까지 계속 비교하고 교환한다.

---

<2> 버블 정렬의 구현

import java.util.Arrays;

public class BubbleSort {
   public static void bubbleSort(int[] arr) {
       int n = arr.length;
       
       // 배열 크기만큼 반복
       for (int i = 0; i < n-1; i++) {
            // 내부 반복문 : 비교 대상 범위를 점점 줄임
            for (int j = 0; j < n -1 -i; j++) {
                 // 앞의 값이 뒤의 값보다 크면 교환
                 if (arr[j] > arr[j + 1]) {
                     // Swap(교환) 로직
                     int temp = arr[j];
                     arr[j] = arr[j + 1];
                     arr[j + 1] = temp;
                 }
            }
       }
   }
   public static void main(String[] args) {
     int[] arr = {5, 3, 8, 4, 2};
        System.out.println("Before Sorting: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("After Sorting: " + Arrays.toString(arr));
    }
   }
}

 

 

사전 준비

1. 배열의 숫자 적기:
• 주어진 배열 [5, 3, 8, 4, 2]의 숫자를 포스트잇에 하나씩 적습니다.
• 포스트잇 하나에 숫자 하나씩 적어서 총 5장을 준비하세요.
• 예: 5, 3, 8, 4, 2
2. 배열 순서대로 배치:
• 테이블 위에 숫자 순서대로 포스트잇을 나란히 놓으세요.
• 예: 5, 3, 8, 4, 2

버블 정렬 과정

첫 번째 라운드 (맨 큰 숫자 찾기)

1. 첫 번째 비교:
• 첫 번째 포스트잇(5)과 두 번째 포스트잇(3)을 비교합니다.
• 둘 중 큰 숫자가 뒤로 가야 해요.
• 5 > 3이니까 자리 바꾸기!
• 결과: 3, 5, 8, 4, 2
2. 두 번째 비교:
• 두 번째 포스트잇(5)과 세 번째 포스트잇(8)을 비교합니다.
• 5 < 8이니까 그대로 두기!
• 결과: 3, 5, 8, 4, 2
3. 세 번째 비교:
• 세 번째 포스트잇(8)과 네 번째 포스트잇(4)을 비교합니다.
• 8 > 4이니까 자리 바꾸기!
• 결과: 3, 5, 4, 8, 2
4. 네 번째 비교:
• 네 번째 포스트잇(8)과 다섯 번째 포스트잇(2)을 비교합니다.
• 8 > 2이니까 자리 바꾸기!
• 결과: 3, 5, 4, 2, 8

• 첫 번째 라운드 끝:
  가장 큰 숫자 8이 맨 뒤로 갔어요.
----
두 번째 라운드 (두 번째로 큰 숫자 찾기)

1. 첫 번째 비교:
• 첫 번째 포스트잇(3)과 두 번째 포스트잇(5)을 비교합니다.
• 3 < 5이니까 그대로 두기!
• 결과: 3, 5, 4, 2, 8
2. 두 번째 비교:
• 두 번째 포스트잇(5)과 세 번째 포스트잇(4)을 비교합니다.
• 5 > 4이니까 자리 바꾸기!
• 결과: 3, 4, 5, 2, 8
3. 세 번째 비교:
• 세 번째 포스트잇(5)과 네 번째 포스트잇(2)을 비교합니다.
• 5 > 2이니까 자리 바꾸기!
• 결과: 3, 4, 2, 5, 8

• 두 번째 라운드 끝:
   두 번째로 큰 숫자 5가 네 번째 자리에 고정!
----
세 번째 라운드 (세 번째로 큰 숫자 찾기)

1. 첫 번째 비교:
• 첫 번째 포스트잇(3)과 두 번째 포스트잇(4)을 비교합니다.
• 3 < 4이니까 그대로 두기!
• 결과: 3, 4, 2, 5, 8
2. 두 번째 비교:
• 두 번째 포스트잇(4)과 세 번째 포스트잇(2)을 비교합니다.
• 4 > 2이니까 자리 바꾸기!
• 결과: 3, 2, 4, 5, 8

•. 세 번째 라운드 끝:
 - 세 번째로 큰 숫자 4가 세 번째 자리에 고정!

----
네 번째 라운드 (마지막 숫자 정렬)

1. 첫 번째 비교:
• 첫 번째 포스트잇(3)과 두 번째 포스트잇(2)을 비교합니다.
• 3 > 2이니까 자리 바꾸기!
• 결과: 2, 3, 4, 5, 8


포스트잇이 완전히 정렬되었습니다!
• 최종 배열: 2, 3, 4, 5, 8

추가 팁

• 정렬이 끝난 후, 각 라운드에서 무엇이 변했는지 확인하기.
• 각 라운드가 끝날 때마다 어떤 숫자가 확정되었는지 알아두기.
• 예: “이번 라운드에서는 가장 큰 숫자 8이 고정되었어!”
• 마지막으로 정렬된 배열을 보고 버블 정렬이 어떻게 동작했는지 정리해보자.

이 버블 배열의 과정도 손으로 적어가면서 그 과정을 익혔다. 절대 암기는 지양...

 

1. 큰 숫자가 "뒤로 밀려나는" 과정 :

  - 버블정렬에서는 가장 큰 숫자가 비교할 때마다 뒤로 밀려나면서 정렬이 된다. 첫번째 라운드에서 가장 큰 숫자 8을 맨 뒤로 보낸것 처럼 말이다.

2. 비교와 교환 :

 - 두 숫자를 비교했을 때 앞의 숫자가 더 크면 자리를 바꿔야 한다. 이렇게 해야 작은 숫자가 앞으로 오고, 큰 숫자는 뒤로 간다.

3. 반복하면서 점점 줄어드는 비교 범위 :

  - 처음에는 다섯 개를 전부 비교했지만, 한 라운드가 끝날 때마다 정렬이 완료된 숫자는 건드리지 않아도 됐다. 그래서 점점 비교할 숫자가 줄어든다. 그래서 j에 관한 for문은 for(int j = 0; j < n-1-i ; j++)로 설정한 것이다.

 

4. 가장 큰 숫자는 어떻게 정해졌을까?

 - 제일 큰 숫자가 비교하면서 맨 뒤로 갔다.

5. 왜 점점 비교하는 숫자가 줄어들었을까?

 - 한 번 끝날 때마다 제일 큰 숫자가 뒤로 가서 정렬이 됐으므로.

6. 자리 바꿈은 언제 했을까?

 - 앞 숫자가 더 클 때 자리를 바꿨다.

7. 어떤 순서로 정렬되었는가?

 - 처음에는 큰 숫자부터 뒤로 가고, 그다음에는 두번째 큰 숫자가 뒤로 간다. 마지막에는 작은 숫자들이 제자리를 찾는다. 

---

<3> 버블 정렬의 특징

 

1. 시간 복잡도:

   • 최악, 평균: O(n^2) (반복문 두 번)

   • 최선: O(n) (이미 정렬된 경우)

2. 공간 복잡도:

   • O(1) (추가 메모리 사용 없음)

3. 단점:

   • 배열 크기가 클수록 속도가 매우 느려집니다.

   • 비교 및 교환 작업이 많아 비효율적입니다.

4. 장점:

   • 구현이 매우 간단합니다.

   • 작은 배열에서는 충분히 유용할 수 있습니다.

 

---

<4> 자주 사용되는 최적화

이미 정렬된 경우 반복 중단

 

버블 정렬의 단점은 불필요한 반복이 많다는 점이다.

배열이 이미 정렬된 경우 더이상 비교와 교환이 필요하지 않으므료, 이를 체크하는 Flag 변수를 추가하면 성능을 향상시킬 수 있다.

public staic void optimizedBubbleSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 0; i < n -1; i++) {
        boolean swapped = false; // 교환 발생 여부 확인
        
        for (int j = 0; j < n -1 -i; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // 교환이 없으면 정렬 완료
        if (!swapped) break;
    }
}

 

 i=0일 때 1라운드, i=1일 때 2라운드이다.

 교환이 발생하지 않는 상황을 만들어서 자세히 설명해보겠다.

 

< 5 >라운드와 루프의 관계

1. 1라운드 (i=0):

 • 배열의 처음부터 끝까지 비교하며 가장 큰 숫자를 맨 뒤로 보낸다.

2. 2라운드 (i=1):

 • 이미 맨 뒤에 정렬된 숫자를 제외하고 다시 비교한다.

 • 이 과정이 계속 반복되며, 정렬이 완료될 때까지 진행된다.

3. 교환이 발생하지 않는 경우:

 • 이미 정렬된 배열이라면 숫자를 바꿀 필요가 없다.

•  이때 swapped = false로 유지되며, 다음 라운드로 넘어가지 않고 멈춘다.

 

교환이 발생하지 않는 예제

 

배열: [1, 2, 3, 4, 5] (이미 정렬됨)

 

이 배열로 최적화된 버블 정렬을 진행해 보겠다.

 

1라운드 (i=0):

 

1. 비교: 1과 2 → 1 < 2 → 교환 없음

• 그대로: [1, 2, 3, 4, 5]

2. 비교: 2과 3 → 2 < 3 → 교환 없음

• 그대로: [1, 2, 3, 4, 5]

3. 비교: 3과 4 → 3 < 4 → 교환 없음

• 그대로: [1, 2, 3, 4, 5]

4. 비교: 4과 5 → 4 < 5 → 교환 없음

• 그대로: [1, 2, 3, 4, 5]

 

1라운드가 끝난 후

 

• swapped = false:

   1라운드 동안 교환이 한 번도 발생하지 않았다.

   따라서 이미 배열이 정렬되었음을 알 수 있다.

• 반복 종료:

   정렬이 완료되었으므로 더 이상 라운드를 진행하지 않고 멈춘다.

 

  최종 배열: [1, 2, 3, 4, 5]

 

 

 

1. 왜 1라운드에서 멈췄을까?

• 교환이 한 번도 일어나지 않았으니까!

2. 교환이 없으면 무슨 뜻일까?

• 숫자들이 이미 정렬되어 있는 것이다.

3. 라운드마다 무슨 일이 일어날까?

• 숫자들을 비교해서 큰 숫자를 뒤로 보낸다.