[Algorithms] 버블 정렬

버블 정렬(Bubble Sort)은 매우 간단한 정렬 알고리즘 중 하나입니다.

버블 정렬은 인접한 두 요소를 비교하여 잘못된 순서로 되어 있으면 그 둘을 교환하는 방식으로 동작합니다.

이 과정이 배열이 정렬될 때까지 반복합니다.

 

장점과 단점

• 장점: 구현이 매우 간단하고 코드가 직관적이다.
• 단점: 평균 및 최악의 경우 시간 복잡도가 O(n²)으로, 큰 데이터 집합을 다룰 때 비효율적이다.

public class BubbleSortExample {
    public static void bubbleSort(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 - 1 - i; j++) {
                // 인접한 요소들을 비교하여 잘못된 순서라면 교환
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j] and arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            // 만약 어떤 교환도 일어나지 않았다면 배열이 이미 정렬된 것이므로 종료
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        bubbleSort(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

// 결과: 11 12 22 25 34 64 90

버블 정렬은 작은 배열이나 이미 거의 정렬된 배열에서는 잘 동작하지만, 크거나 무작위로 정렬된 배열에서는 성능이 떨어집니다.

 

끝.