정렬 - 버블정렬(Bubble Sort)

버블 정렬(Bubble Sort)란?

버블 정렬은 서로 인접한 두 개의 값을 비교하면서 정렬하는 방식으로, 작은 값을 왼쪽으로, 큰 값을 오른쪽으로 이동시킵니다.
마치 거품(Bubble)이 물 위로 올라가는 것처럼 가장 큰 값이 반복적으로 오른쪽 끝으로 이동하므로 **버블 정렬(Bubble Sort)**이라고 불립니다.

정렬 동작 과정

예제 배열:
[5, 3, 6, 4, 1]

1회전(첫 번째 바깥 루프)

각 숫자를 비교하여 큰 값을 오른쪽으로 이동

[5, 3, 6, 4, 1] → [3, 5, 6, 4, 1]  (5와 3 교환)
[3, 5, 6, 4, 1] → [3, 5, 6, 4, 1]  (5와 6 그대로 둠)
[3, 5, 6, 4, 1] → [3, 5, 4, 6, 1]  (6과 4 교환)
[3, 5, 4, 6, 1] → [3, 5, 4, 1, 6]  (6과 1 교환)

➡ 가장 큰 숫자 6이 맨 끝으로 이동됨.

2회전(두 번째 바깥 루프)

[3, 5, 4, 1, 6] → [3, 5, 4, 1, 6]  (3과 5 그대로 둠)
[3, 5, 4, 1, 6] → [3, 4, 5, 1, 6]  (5와 4 교환)
[3, 4, 5, 1, 6] → [3, 4, 1, 5, 6]  (5와 1 교환)

➡ 두 번째로 큰 숫자 5가 오른쪽으로 이동

이 과정을 반복하면 배열이 완전히 정렬됩니다.

---

코드 설명

const arr = [5, 3, 6, 4, 1]; // 정렬할 배열

for (let i = 0; i < arr.length - 1; i++) { 
    let swapped = false; // 정렬 완료 여부 체크

    for (let j = 0; j < arr.length - i - 1; j++) { // 비교 범위 줄이기
        if (arr[j] > arr[j + 1]) { 
            [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // 구조 분해 할당을 이용한 값 교환
            swapped = true; // 값이 바뀌었음을 표시
        }
    }

    console.log(arr); // 현재 상태 출력

    if (!swapped) break; // 더 이상 바뀔 값이 없으면 정렬 완료 → 반복문 종료
}

---

코드 상세 설명

1. for (let i = 0; i < arr.length - 1; i++)

• 배열의 전체 크기에서 1을 뺀 횟수만큼 반복 (i가 증가할수록 정렬 범위가 줄어듦)
• i가 클수록 가장 오른쪽 부분은 이미 정렬됨 → arr.length - i - 1까지 비교

2. let swapped = false;

• 교환이 발생했는지 체크하는 플래그
• 한 번도 교환이 발생하지 않으면 이미 정렬이 완료된 것이므로 반복 종료

3. for (let j = 0; j < arr.length - i - 1; j++)

• j는 arr.length - i - 1까지 반복하여 정렬된 부분은 제외
• arr[j]와 arr[j+1]을 비교하여 큰 값을 오른쪽으로 이동

4. [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];

• 구조 분해 할당을 사용하여 tmp 변수를 쓰지 않고 두 값을 교환

5. if (!swapped) break;

• 교환이 한 번도 일어나지 않으면 배열이 이미 정렬되었으므로 루프를 종료하여 불필요한 연산을 줄임 (최적화)

---

코드 실행 예제

[3, 5, 6, 4, 1]
[3, 5, 4, 6, 1]
[3, 5, 4, 1, 6]
[3, 4, 5, 1, 6]
[3, 4, 1, 5, 6]
[3, 1, 4, 5, 6]
[1, 3, 4, 5, 6] (정렬 완료)

최적화(swapped) 덕분에 이미 정렬된 경우 불필요한 반복을 줄일 수 있음.

---

결론

- 버블 정렬은 서로 인접한 값을 비교하여 정렬하는 방식
- swapped 플래그를 추가하여 불필요한 반복을 줄여 최적화
- **구조 분해 할당([] 사용)**으로 값을 교환하여 코드 간결화
- 정렬할 필요 없는 부분은 arr.length - i - 1을 사용하여 반복 횟수 단축

이제 더 효율적이고 최적화된 버블 정렬 코드가 완성되었습니다! 

const arr = [5,3,6,4,1];
    let tmp, count=1;
    
    for(let i=0; i<arr.length-1; i++) {

        for(let i=0; i<arr.length-count; i++) {
            if(arr[i] > arr[i+1]) {
                tmp = arr[i+1];
                arr[i+1] = arr[i];
                arr[i] = tmp;        
            }
        }
        console.log(arr);
        count++;
        
    }

    
    
    /*
    for(let i=0; i<arr.length-1; i++) {
        if(arr[i] > arr[i+1]) {
            tmp = arr[i+1];
            arr[i+1] = arr[i];
            arr[i] = tmp;        
        }
    }
    console.log(arr);
    for(let i=0; i<arr.length-2; i++) {
        if(arr[i] > arr[i+1]) {
            tmp = arr[i+1];
            arr[i+1] = arr[i];
            arr[i] = tmp;        
        }
    }
    console.log(arr);
    */