[알고리즘] 자바 Bubble Sort(버블 정렬) 알고리즘 / 정렬 알고리즘 기초

Bubble Sort(버블 정렬)이란?

버블 정렬은 정렬 과정에서 원소의 이동이 마치 거품이 수면 위로 올라오는 것과 같다고 해서 '버블'이라는 이름이 붙여졌습니다.

버블 정렬은 정렬 알고리즘 중 가장 간단한 알고리즘 중 하나로, 두 개의 인접한 원소를 비교해서 정렬하는 방식으로 정렬합니다.

보통 버블 정렬은 구현이 간단하지만 비효율적이므로, 교육용으로 알고리즘의 기본 개념을 설명하거나 작은 데이터셋에 사용하고 있습니다.

• 사용 사례
  • 대규모 데이터에는 적합하지 않기 때문에 데이터 셋이 작은 경우에 사용합니다.
  • 초기 프로그래밍 교육 시 자료로 사용합니다.

버블 정렬의 특징

버블 정렬은 데이터를 비교하면서 찾기 때문에 비교 정렬이며,

정렬의 대상이 되는 데이터 외에 추가적인 공간을 거의 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이라고도 합니다.

비록 데이터를 교환하는 과정(SWAP)에서 임시 변수를 사용해야 하지만, 이는 매우 작은 양의 메모리이므로 제자리 정렬로 간주됩니다.

버블 정렬은 간단하지만 비효율적은 알고리즘으로, 데이터가 많을 경우에는 사용하기 적합하지 않을 수 있습니다.

그러나, 기본적인 정렬 개념을 이해하고, 간단한 상황에서 사용할 수 있는 좋은 학습 도구로 활용될 수 있습니다.

• SWAP 과정
  • 왼쪽부터 탐색하여 인접한 요소를 비교하고 더 높은 요소를 오른쪽에 배치합니다. 
  • 다음과 같은 방식으로 가장 큰 요소가 가장 오른쪽 끝으로 이동됩니다. 
  • 그다음 이 프로세스는 데이터가 정렬될 때까지 두 번째로 큰 것을 찾아 배치하는 등의 작업을 계속합니다.
• 장점
  • 추가적인 메모리 소비가 적은 편이며, 안정적인 정렬이 가능합니다.
  • 코드가 직관적으로 구현하기 쉬운 알고리즘입니다.
  • 대부분의 정렬 알고리즘을 배우기 전, 기초적인 정렬 개념을 익히기에 적합합니다.
• 단점
  • 다른 정렬 알고리즘에 비해 교환 과정이 다소 많아 시간이 많이 소요됩니다.
  • 버블 정렬 알고리즘은 최악의 경우가 O(N^2)로 비효율적인 시간 복잡도로, 대규모 데이터 세트에는 비효율적입니다.
  • 데이터가 이미 정렬된 경우에도 불필요한 비교를 수행할 수 있습니다.

정렬 방법 및 구현

• 정렬 방법
  • 앞에서부터 현재 원소와 바로 인접한 다음의 원소를 비교합니다.
  • 현재 원소가 다음 원소보다 비교하여 크면 원소를 교환합니다.
  • 다음 원소로 이동하여 해당 원소와 그다음 원소를 비교합니다.
  • 위 과정을 정렬될 때까지 반복적으로 진행합니다.

아래는 자바 코드로 구현한 버블 정렬의 예시입니다.

❗️꿀팁
swap 플래그를 사용하여 반복 차수 마다 여떤 요소도 교환하지 않으면, 배열이 이미 정렬된 것으로 간주하여 더 이상 정렬을 진행하지 않게 만들어 버블 정렬의 성능을 약간이라도 최적화할 수 있습니다.

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 7, 1, 3, 2, 9, 6, 8};
        bubbleSort(arr);

        System.out.println(Arrays.toString(arr));
        // [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    // 기본 버블 정렬 알고리즘
    private static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        // 반복문을 통해 배열을 순차적으로 정렬
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            // 인접한 두 원소를 비교하여 교환(swap)
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j+1]) {
                    // swap 과정
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    swapped = true;
                }
            }
            
            if (!swapped) {
                break;
            }
        }
    }
}

버블 정렬의 시간 복잡도 및 공간 복잡도

• 시간 복잡도
  • 버블 정렬의 시간 복잡도는 최선의 경우 O(n), 최악의 경우 O(n^2)입니다.
  • 따라서 대부분의 경우, 데이터 양이 많을 때는 비효율적입니다.
• 공간 복잡도 : 버블 정렬은 제자리 정렬로, 추가적인 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다.

결론

버블 정렬은 기초적인 정렬 알고리즘이긴 하지만, 사실상 거의 사용하지 않는 교육용으로 알고리즘의 기본 개념을 설명할 때 사용합니다.

삽입 정렬 또는 선택 정렬과 같은 O(N^2)의 시간 복잡도를 갖긴 하지만 버블 정렬의 교환 횟수가 평균적으로 더 많기 때문에 삽입, 선택 정렬보다 시간 더 많이 소요되기 때문에 버블 정렬은 거의 사용하지 않습니다.

하지만 버블 정렬에서 사용하는 Swap연산이 중요하기 때문에 프로그래밍 교육할 때 자주 사용되는 예제 중 하나입니다.

REF.

https://www.geeksforgeeks.org/bubble-sort-algorithm/

Bubble Sort Algorithm - GeeksforGeeks