버블 정렬 알고리즘 이해(Java 예제 포함)

버블 정렬에 대한 자세한 설명: 간단한 정렬 알고리즘

버블 정렬은 가장 간단한 정렬 알고리즘 중 하나입니다. 인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교체하는 방식으로 작동합니다. 예를 들어 정렬 순서가 오름차순인 경우 인접한 요소를 비교하여 더 큰 요소가 오른쪽에 배치됩니다. 각 반복에서 정렬되지 않은 요소만 비교하고 배열에서 정렬되지 않은 요소의 마지막 위치에 가장 큰 요소를 배치합니다.

이 알고리즘은 거품이 물 표면으로 떠오르는 것처럼 각 반복마다 요소가 배열의 오른쪽을 향해 이동하기 때문에 버블 정렬이라는 이름이 붙었습니다.

버블정렬 작동 원리

이 배열을 오름차순으로 정렬한다고 가정해 보겠습니다.

첫 번째 반복

첫 번째 반복에서는 가장 큰 요소를 배열의 끝으로 이동하려고 합니다. 따라서 우리는 인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교체합니다.

올바른 위치로 이동된 요소는 정렬된 것으로 간주됩니다.

다음 반복

배열이 정렬될 때까지 모든 반복에 대해 이 프로세스가 반복됩니다. 각 반복에서는 정렬된 요소가 이미 올바른 순서로 되어 있으므로 정렬되지 않은 요소만 비교합니다.

배열을 n-1회 반복합니다. 여기서 n은 배열의 길이입니다. 즉, 배열에 요소가 6개 있으므로 배열을 5번만 반복합니다. 이는 다섯 번째 반복 후에 다섯 개의 요소가 올바른 위치에 배치되었으므로 정렬되지 않은 최종 요소가 정렬된 것으로 간주되기 때문입니다. 모든 반복이 완료되면 정렬된 배열을 얻게 됩니다.

버블정렬 구현

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

이 코드를 실행하면 콘솔에 다음 출력이 인쇄됩니다.

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

이 버블 정렬 구현에서는 배열이 이미 정렬된 경우에도 매번 배열을 반복합니다. 배열이 정렬되면 정렬이 중지되도록 코드를 더욱 최적화할 수 있습니다.

최적화된 버블정렬

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果没有交换，则数组已排序
        if(!swapped) break;
    }
}

이 구현을 사용하면 이미 정렬된 배열을 정렬하려고 하면 한 번만 반복하고 정렬이 발생하지 않으면 중지합니다.

버블정렬의 복잡성

시간 복잡도:

최상의 경우(O(n)):

가장 좋은 시나리오는 입력 배열이 이미 정렬되어 있다는 것입니다. 알고리즘은 배열을 한 번만 반복하여 정렬되었는지 확인하고 스와핑을 수행하지 않습니다.

평균 사례(O(n²)):

입력 배열 요소가 임의의 순서로 되어 있는 경우. 알고리즘은 배열을 정렬하기 위해 여러 번 반복하고 교체를 수행해야 합니다.

최악의 경우(O(n²)):

최악의 시나리오는 입력 배열이 역순으로 정렬되는 것입니다. 알고리즘은 n-1 반복을 거쳐 최대 교환 횟수를 수행합니다.

공간 복잡도 O(1):

버블 정렬은 내부 정렬 알고리즘입니다. 즉, 입력 배열의 크기에 비례하는 추가 메모리가 필요하지 않습니다.

결론

버블 정렬은 이해하기 쉽고 구현하기 쉬운 알고리즘입니다. 그러나 시간 복잡도가 높아 대규모 데이터 세트를 처리하는 데는 적합하지 않습니다. 버블 정렬은 작은 데이터 세트로 작업할 때나 복잡성을 고려하지 않을 때 사용할 수 있습니다.

위 내용은 버블 정렬 알고리즘 이해(Java 예제 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!