버블 정렬(Bubble Sort) 알고리즘 이해하기

정렬 알고리즘 중에서 가장 기본적인 버블 정렬(Bubble Sort) 알고리즘에 대해 이야기하려고 합니다. 이 글에서는 버블 정렬의 원리와 Java 코드 예제를 통해 알고리즘을 구현하는 방법을 알아보겠습니다.

 

1. 버블 정렬(Bubble Sort)이란?
버블 정렬은 인접한 두 원소를 비교하면서 정렬하는 간단한 정렬 알고리즘입니다. 원소들을 정렬된 상태로 만들기 위해 연속된 원소들을 교환해 나가는 방식으로 진행됩니다.

2. 버블 정렬의 원리
버블 정렬의 기본 원리는 다음과 같습니다:

리스트의 처음부터 끝까지 인접한 원소들을 비교합니다.
만약 인접한 두 원소의 순서가 잘못되어 있다면, 서로 위치를 바꿉니다.
위 과정을 리스트의 끝까지 반복합니다.
리스트의 끝에서부터 정렬된 원소들을 제외하고, 1~3단계를 전체 리스트가 정렬될 때까지 반복합니다.

 

3. 버블 정렬 구현하기

public class BubbleSortExample {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        bubbleSort(arr);

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

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

위 코드에서 bubbleSort 메소드는 버블 정렬 알고리즘을 구현한 것입니다. 이 메소드는 정수 배열을 입력으로 받아 배열을 오름차순으로 정렬합니다. 이를 위해 두 개의 중첩된 반복문을 사용하여, 배열의 인접한 원소들을 비교하고 필요한 경우 서로 교환합니다.

 

4. 버블 정렬의 시간 복잡도 및 공간 복잡도
버블 정렬의 시간 복잡도는 다음과 같습니다.

최선의 경우: O(n)
평균의 경우: O(n^2)
최악의 경우: O(n^2)
최선의 경우는 이미 정렬된 배열이 주어졌을 때입니다. 이 경우, 한 번의 순회로 정렬 여부를 확인할 수 있습니다. 그러나 일반적인 경우와 최악의 경우에는 배열의 모든 원소를 반복적으로 비교해야 하므로 시간 복잡도가 O(n^2)입니다.

버블 정렬의 공간 복잡도는 O(1)입니다. 이는 원래의 배열에 대한 몇 개의 추가 변수만 필요하기 때문입니다.

 

5. 결론
이 글에서는 Java를 사용하여 버블 정렬 알고리즘을 구현하는 방법을 알아보았습니다. 버블 정렬은 기본적인 정렬 알고리즘이며, 프로그래밍을 공부하는 데 있어 중요한 개념입니다. 그러나 대용량 데이터를 처리할 때는 더 효율적인 정렬 알고리즘을 사용하는 것이 좋습니다. 다음에는 더 복잡하지만 효율적인 정렬 알고리즘을 다룰 예정이니, 기대해 주세요!