[ Algorithm ] Bubble Sort(버블 정렬)

버블 정렬(Bubble Sort)

버블 정렬은 가장 간단한 정렬 알고리즘(sorting algorithm) 중 하나이다

• 기본기 중의 기본기
• 스스로 이 알고리즘을 고안하지 못해도 됨
• 하지만 한 번이라도 이해하면 언제라도 작성 가능해야 함

작동 원리

• 이웃 요소 둘을 비교해서 올바른 순서로 고치는 과정을 반복
• 한 번 목록을 순회할 때마다 가장 큰 값이 제일 위로 올라감
  • 기포가 수면으로 떠오르는 모습을 닮았다고 해서 버블 정렬이라 부름
  • 큰 기포일수록 수면으로 더 빨리 떠오름

버블 정렬은 간단한 아이디어를 구현한 것이다. 오름차순으로 정렬하려는 정수 컬렉션이 있다고 가정하자. 버블 정렬은 두 개의 인접한 요소를 한 번에 고려한다. 이 두 인접 요소가 순서가 잘못되었다면(이 경우, 왼쪽 요소가 오른쪽 요소보다 엄격히 크다면), 버블 정렬은 이들을 교환한다. 그런 다음 다음 쌍의 인접 요소로 진행한다. 버블 정렬의 첫 번째 패스에서는 컬렉션의 모든 인접 요소 세트를 한 번씩 처리하며 필요에 따라 교환을 수행한다. 버블 정렬의 핵심 아이디어는 단일 패스에서 더 이상 교환이 이루어지지 않을 때까지 이 과정을 반복하는 것이며, 이는 리스트가 정렬되었음을 의미한다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)

• 평균 수행 시간: O(N^2)
• 최악 수행 시간: O(N^2)
• 메모리(공간 복잡도): O(1)
• 안정성: O

버블 정렬의 실행 시간은 배열이 정렬될 때까지 수행해야 하는 패스 횟수에 전적으로 기반한다. 배열에 n개의 요소가 있다면, 각 패스는 (n-1) 쌍을 고려한다. 최악의 경우, 최소 요소가 리스트의 끝에 있을 때, 리스트의 앞쪽 적절한 위치로 이동시키는 데 (n-1) 패스가 필요하고, 더 이상 교환이 필요 없다는 것을 확인하기 위해 추가로 한 번의 패스가 필요하다.

버블 정렬은 안정적인(stable) 정렬 알고리즘이다. 동일한 요소들의 상대적 순서가 보존되기 때문이다.

전반적으로 버블 정렬은 구현하기 쉽고 안정적이지만, 그 외에는 바람직한 특징이 많지 않다. 대부분의 입력에 대해 상당히 느리며, 따라서 실제로는 거의 사용되지 않는다.

Java 구현

public static void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = 0; j < nums.length - 1 - i; j++) {
            if (nums[j] > nums[j+1]) {
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }
        }
    }
}

또는 최적화된 버전

public class Solution {
    public void bubbleSort(int[] arr) {
        boolean hasSwapped = true;
        while (hasSwapped) {
            hasSwapped = false;
            for (int i = 0; i < arr.length - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    hasSwapped = true;
                }
            }
        }
    }
}

이 최적화된 버전은 이미 정렬된 배열에 대해 O(n)의 시간 복잡도를 가진다.