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

버블 정렬 (Bubble Sort)

인접한 데이터를 비교하며 필요한 경우 자리를 바꾸는 정렬 방식

시간복잡도 : (n-1) + (n-2) + (n-3) + ... + 2 + 1 -> n(n-1)/2 즉, O(n^2)

공간복잡도 : O(n)

장점

• 구현이 간단하고 이해하기 쉽다.
  • 기본적인 비교와 교환 과정으로 이루어져 있어 구현하기가 간단하다.
  • 알고리즘의 동작 방식도 직관적이어서 이해하기 쉽다.
    
    
• 추가적인 메모리 공간이 필요하지 않다. 
  • 주어진 배열 안에서 비교와 교환을 수행하므로, 정렬을 위한 추가적인 메모리 공간이 필요하지 않다.
    
    
• 안정적인 정렬 알고리즘이다. (Stable Sort)
  • 동일한 값에 대해서는 상대적인 순서가 변하지 않는다.
    
    

단점

• 성능이 비효율적이다.
  • 시간 복잡도가 O(n^2)으로 배열의 크기가 커질수록 성능이 저하된다.
  • 모든 인접한 원소를 비교하고 교환하는 고자어을 반복해야 하기 때문에, 다른 고급 정렬 알고리즘에 비해 효율이 낮다.
    
    
• 최선의 경우에도 비교 연산이 많이 필요하다.
  • 배열이 이미 정렬되어 있는 경우에도 버블 정렬은 비교와 교환을 모두 수행한다.
    
    

버블 정렬 구현

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // 인접한 두 원소를 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}