[정렬] 버블 정렬

목차

1. 버블 정렬
2. 버블정렬 특징
3. 버블정렬 수행 방식
4. 핵심 이론

 

 

---

 

 

버블 정렬

인접한 데이터의 크기를 비교해서 순서가 잘못된 경우 서로 교환하는 방법입니다. 

 

 

---

 

 

버블정렬 특징

• 시간 복잡도는 O(n²)으로 다른 정렬 알고리즘보다 속도가 느린 편입니다.
• Loop를 돌면서 인접한 데이터 간의 swap 연산으로 정렬합니다.

 

---

 

 

버블정렬 수행 방식

버블 정렬 수행 방식

• 루프 한 번 : n의 시간 복잡도
• n번 만큼 루프를 돈다 : N의 시간 복잡도
• 따라서 `n × n` 이므로 총 시간 복잡도는 `n²`이다.

 

 

---

 

 

핵심 이론

• 한 번의 루프마다 배열의 끝으로 가장 큰 값이 이동한다.
• 정렬 과정은 최대 n-1번의 패스로 이루어진다. (n은 배열 크기)
• 반복문 중 교환(SWAP)이 한 번도 일어나지 않으면, 정렬 완료로 간주하고 종료할 수 있다. (최적화 가능)

public void bubble_sort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        
        // 마지막 i개는 이미 정렬
        for (int j = 0; j < n - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // swap
                int temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                swapped = true;
             }
         }
         
         if (!swapped) break;
     }
}

• 한 번의 루프마다 배열의 끝으로 가장 큰 값이 이동하기 때문에, `n - i - 1`을 하였다.
• `SWAP`이 일어나지 않을 시, 종료하는 로직을 수행할 수 있다.