[Java] 왜 가운데에 boolean 을 자꾸 추가해요

 

훌륭한 개발자인 당신이 "알고리즘"을 공부하다 보면, 가끔 boolean 값이 for loop 안에 있다는 것을 확인할 수 있을 것이다. 

AI 한테 물어봐도 "ㅇㅇ 이건 당연한거고 지당한 거야"라는 "원론적인 대답"만 돌아온다

 

 

 

오늘은 그걸 알아볼것이다

 

 

---

 

 

Heap이니 Stack이니 Garbage collect 니, 그건 나중에 알아보고, 오늘은 bubble sort 를 예시로 알아볼것이다 

 

물론, "실무"를 하다보면 굳이 구태여 "Bubble Sort" 를 구현할려고 하지 않고 

 

Arrays.sort() 로 내부 method 를 부르는 것으로 Array 를 차순으로 빠르게 정리하지만.

그래도 "원리"는 알고있어야지 코딩이 재밌어지니까.

 

 

그럼 일단 코드를 봐보자

훌륭한 당신의 조수 (ChatGPT 가 씀)

 

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        // 1. 외부 루프: 배열의 모든 원소를 순회
        for (int i = 0; i < n - 1; i++) {
            swapped = false; // 매 라운드 시작 시 교환 여부 초기화

            // 2. 내부 루프: 인접한 원소끼리 비교 (정렬된 끝부분은 제외)
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 3. Swap: 앞의 숫자가 더 크면 위치를 바꿈
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    
                    swapped = true; // 교환이 일어났음을 표시
                }
            }

            // 4. Early Exit: 이번 라운드에서 교환이 한 번도 없었다면 이미 정렬된 상태!
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] data = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(data);
        
        System.out.println("정렬된 배열:");
        for (int i : data) System.out.print(i + " ");
    }
}

 

 

이 코드를 보자마자 그럼 이제 당신은 머릿속에 그려야하는 그림은, 

 

인데, 그건 훌륭하고 훌륭한 "개발자 (개고수)" 가 아닌 이상 바로 이미지로 연상은 되지 않을 것이다. 

 

 

애초에, 초보자 수준에서 "temp" 는 또 뭐고 왜 내부 loop 는 n - 1 - i 를 했는지도 잘 이해 안 갈 것이다

밑으로 설명을 계속해보자

---

🔹 Bubble Sort, 겉으로 보기엔 단순하지만…

Bubble Sort는 말 그대로 거품처럼 큰 값이 위로 올라가는 방식이다.

배열을 처음부터 끝까지 쭉 훑으면서, 옆의 값과 비교해 더 큰 값이면 서로 바꾼다.

이 과정을 한 바퀴 돌면, 가장 큰 값이 마지막 자리로 이동한다.

 

이걸 반복해서 전체 배열이 정렬될 때까지 계속한다.

 

 

Ex) 김철수 어린이 (키 195 거구) , 김민수 어린이(키 240cm) 는 육안으로 서로의 키가 다르다는 것을 알고 있기때문에,

바로 자리를 옮겨서 키순으로 줄을 설텐데, 그러니까, 이들은 서로의 키는 모르는 상태에서 엄마가 적어준 종이에

"너의 키는 195란다 철수야" 라고 적혀있는 종이를 서로 "우리반 모든이들"과 비교하면서 자리를 바꾼다

 

그럼 이들이 자리를 바꾸기 위해선, 그러니까 자리를 비교하기 위해선 , 적어도 다른 하나의 자리가 잇어야할 것이다

왜냐하면 철수는 거기에 서서 계속 옆에있는 아이와 키를 비교해야하니까

 

 

// j는 현재 종이를 들고 옆 친구와 비교 중인 어린이의 번호
for (int j = 0; j < n - 1 - i; j++) {
    
    // 내 종이(arr[j])가 옆 친구 종이(arr[j+1])보다 숫자가 크면?
    if (arr[j] > arr[j + 1]) {
        
        int temp = arr[j];  // 내가 잠시 옆으로 비켜주고
        arr[j] = arr[j+1];  // 옆 친구가 내 자리로 오고
        arr[j+1] = temp;    // 내가 옆 친구 자리로 이동!
        
    }
}

 

 

 

그럼 왜 n - 1 은 알겠는데 (왜냐하면 index 는 0부터 시작하니까) , 왜 n - 1  - i 야? 

그건 바로 철수가 아닌, 거구의 김민수(240cm) 가 들어갈 장소가 필요하기 때문이다. 

 

버블 정렬을 한 바퀴(i가 한 번 증가) 돌 때마다, 반드시 한 명은 자기 자리를 찾습니다. * i = 0 (첫 바퀴): 반에서 제일 키 큰 애가 맨 뒤로 갑니다. (이제 맨 뒷자리는 '완료 구역')

• i = 1 (두 번째 바퀴): 남아있는 애들 중 제일 큰 애가 뒤에서 두 번째로 갑니다. (이제 뒤에 두 자리는 '완료 구역')

 

그럼 n-2 로 하면되지 않냐? (왜냐하면 김민수는 한명이니까)

 

그건 우리가 "정답"을 알고있을때의 문제고,

실제로는 어린이가 30명일지, 3만명일지, 35만명일지 모른다.

 

 

 

그러면 다음 문제

 

---

🔹 boolean 값은 왜 필요할까?

여기서 등장하는 boolean 값, 예를 들어 swapped 같은 변수는 이번 한 바퀴(pass) 동안 변화가 있었는지 체크하는 장치이다.

• 한 바퀴 동안 한 번도 swap이 발생하지 않았다면
  → 이미 배열은 정렬된 상태
  → 반복을 더 이상 돌릴 필요가 없다

즉, "얘랑은 한번 키 잿어, 다음애랑 재자!" 라는 index 인셈

 

---

🔹 boolean은 매 바퀴마다 새로 초기화한다

여기서 중요한 포인트!
swapped 같은 변수는 반복 단위마다 새로 초기화해야 한다.

(그래서 loop 안에 잇음)

 

• 초기화 안 하면, 이전 바퀴에서 swap이 있었던 기록이 남아
• 지금 아무도 움직이지 않아도 프로그램은 “아직 정렬 안 됐어!”라고 착각한다.

비유하자면, 매 회전마다 김민수 어린이는 어머니가 써준 키를 확인하는 종이를 꺼내서 체크하는 것과 같다.
한 바퀴 도는 동안 변화가 있었는지 새로 기록하는 거다.

---

🔹요약 Bubble Sort의 핵심 구조

1. 배열을 처음부터 끝까지 훑는다
2. 옆 값과 비교해서 더 큰 값이면 swap
3. boolean으로 이번 바퀴에서 swap이 있었는지 체크
4. swap 없으면 반복 종료
5. swap 있으면 다음 바퀴 반복

---

🔹 오늘 배운 핵심

• boolean 값은 과거 기록이 아니라, 현재 한 바퀴의 상태만 판단하는 도구
• 반복마다 초기화해서 정렬 완료 여부를 효율적으로 판단
• 이 패턴은 bubble sort뿐 아니라 DFS, BFS 등 반복 구조에서도 자주 등장

---

다음 글에서는 이 패턴을 선택 정렬, 삽입 정렬, 고급 정렬에도 적용하면서,
각각 언제 쓰는지, stable/un-stable 특징까지 연결해볼 예정이다.

 

 

---

결어

사실,  해결책을 한번 제시하고 -> 이걸 어케 효율화하고 메모리값을 아끼는 코드로 하지? 라는 것이 중요한데..

요즘 개발은 AI 로 딸깍 해버리니까 할말 없긴함...