초보 자바 프로그래밍(18) - 버블정렬 (Bubble Sort)

버블 정렬 대표 이미지

🔖 INDEX

 

 

배열은 프로그래밍에서 가장 기본적인 자료 구조 중 하나로, 여러 데이터를 저장하고 접근하는 데 사용됩니다. 이번 파트부터 배열을 정렬하는 다양한 알고리즘에 대해 자세하게 설명합니다. 정렬 알고리즘은 데이터를 오름차순이나 내림차순으로 정렬하는 데 사용됩니다. 다양한 정렬 알고리즘들이 있으며, 각 알고리즘은 효율성, 안정성, 메모리 사용량 등에 따라 다른 특성을 가집니다. 각 알고리즘의 원리와 효율성을 분석하고, 실제로 자바 코드로 구현하는 방법을 살펴봅니다.

 

버블 정렬의 작동 원리

버블 정렬(Bubble Sort)은 가장 기본적이고 직관적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 인접한 원소들끼리 반복적으로 비교하고 교환하여 정렬을 수행합니다. 버블 정렬은 이해하기 쉽고 구현하기 간단하지만, 효율성이 떨어져 큰 데이터 셋에서는 사용하지 않는 것이 좋습니다.

 

버블 정렬의 작동 원리는 다음과 같습니다:

1. 배열의 첫 번째 원소부터 시작하여 인접한 원소와 비교합니다.
2. 만약 인접한 원소끼리 순서가 잘못되어 있다면(즉, 앞에 있는 원소가 뒤에 있는 원소보다 크다면), 두 원소의 위치를 교환합니다.
3. 배열의 끝까지 이 과정을 반복하며, 가장 큰 원소가 배열의 끝으로 이동합니다. 이 과정을 한 번 거치면 배열의 가장 큰 원소가 정렬된 위치에 있게 됩니다.
4. 배열의 끝에서부터 정렬된 원소들을 제외하고, 다시 처음부터 위 과정을 반복합니다.
5. 이 과정을 배열의 모든 원소가 정렬될 때까지 계속합니다.

 

버블 정렬의 특징

버블 정렬의 특징은 다음과 같습니다:

1. 안정적인 정렬(Stable Sort): 같은 값의 원소들은 정렬 과정에서 상대적인 순서가 변경되지 않습니다.
2. 제자리 정렬(In-place Sort): 추가적인 메모리를 사용하지 않고 입력 배열 안에서 정렬이 이루어집니다.
3. 시간 복잡도(Time Complexity): 평균적으로 O(n^2)의 시간 복잡도를 가지며, 최선의 경우에도 O(n)의 시간이 소요됩니다. 이로 인해 큰 데이터 셋에서는 사용하지 않는 것이 좋습니다.
4. 적응 정렬(Adaptive Sort): 이미 정렬된 부분에 대해서는 빠르게 수행할 수 있는 특징이 있습니다.

버블 정렬은 작은 데이터 셋이나 간단한 프로젝트에 적합한 정렬 알고리즘이지만, 성능이 중요한 상황에서는 더 효율적인 알고리즘을 사용하는 것이 좋습니다. 예를 들어 퀵 정렬, 병합 정렬, 힙 정렬 등이 더 큰 데이터 셋에서 더 좋은 성능을 보입니다.

 

 

버블 정렬의 구현 예제

버블 정렬은 다음과 같이 구현할 수 있습니다.

// BubbleSort 클래스 선언
public class BubbleSort {
    // 버블 정렬 알고리즘을 수행하는 함수
    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;
                }
            }
        }
    }

    // 메인 함수
    public static void main(String[] args) {
        // 정렬할 배열
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        // 정렬 전 배열 출력
        System.out.println("Unsorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }

        // 버블 정렬 실행
        bubbleSort(arr);

        // 정렬 후 배열 출력
        System.out.println("\nSorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}