[Algorithm] 버블 정렬

[2d3k]

1. 버블 정렬 구현 방법?

2. 시간복잡도, 공간복잡도?

3. 장단점?

[2d3k]

1 버블 정렬(Bubble Sort)은 인접한 두 개의 원소를 비교하여 정렬하는 알고리즘입니다. 구현 방법은 다음과 같습니다.

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; 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;
            }
        }
    }
}

[2d3k]

2 버블 정렬의 시간 복잡도는 O(n^2)입니다. 이는 배열의 크기가 커질수록 정렬에 소요되는 시간이 기하급수적으로 늘어남을 의미합니다.

버블 정렬의 공간 복잡도는 O(1)입니다. 버블 정렬은 추가적인 배열이나 메모리를 필요로 하지 않고, 주어진 배열 내에서 값의 위치를 변경하므로, 입력 배열의 크기와 상관없이 일정한 공간만을 필요로 합니다.

[2d3k]

3 버블 정렬은 간단하게 구현할 수 있는 정렬 알고리즘이며, 이해하기 쉬운 알고리즘입니다.

하지만, 최악의 경우 시간 복잡도가 O(n^2)이며, 정렬 대상이 많아질수록 성능이 급격하게 저하됩니다. 또한, 이미 정렬된 배열의 경우에도 모든 요소를 비교하고 교환하는 과정을 거치기 때문에 성능 저하가 발생할 수 있습니다.

따라서, 버블 정렬은 소규모의 데이터 정렬에 적합합니다. 대용량의 데이터 정렬에는 다른 정렬 알고리즘이 보다 효율적입니다.

[hyeonayou]

1. 버블 정렬 구현 방법? 버블정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. -> 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다.

public class Bubble_Sort {

    public static void bubble_sort(int[] a) {
        bubble_sort(a, a.length);
    }

    private static void bubble_sort(int[] a, int size) {

        // round는 배열 크기 - 1 만큼 진행됨 
        for(int i = 1; i < size; i++) {

            // 각 라운드별 비교횟수는 배열 크기의 현재 라운드를 뺀 만큼 비교함
            for(int j = 0; j < size - i; j++) {

                /*
                 *  현재 원소가 다음 원소보다 클 경우
                 *  서로 원소의 위치를 교환한다. 
                 */
                if(a[j] > a [j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

2. 시간복잡도, 공간복잡도?

Bubble Sort는 중간에 정렬이 완료되었음에도, 마지막 회차까지 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2) 으로 동일하다.

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.

3. 장단점?

Bubble Sort는 성능이 좋지 않으나 코드가 단순하여 간단한 데이터의 정렬에는 사용되기도 한다.