[Algorithm] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

두 개의 인접한 요소를 비교하고 필요한 경우 위치를 교환(Swap)하여 리스트를 정렬합니다.
버블 정렬은 모든 요소를 탐색하며 정렬 조건(오름차순, 내림차순 등)에 해당하는 요소가 가장 뒤로 이동할 때까지 반복됩니다.
정렬 시 거품이 올라오는 것처럼 보여 버블 정렬이라고 이름이 지어졌습니다.

출처

예제

먼저 다음과 같이 정렬되지 않은 배열이 있다고 가정하겠습니다.

위 배열을 오름차순으로 정렬하기 위한 버블 정렬 알고리즘은 다음과 같이 동작합니다.

첫 번째 인덱스부터 시작하여 첫 번째 요소와 두 번째 요소를 비교합니다. 첫 번째 요소가 두 번째 요소보다 크면 교체됩니다. 마지막 요소에 도달할 때까지 이전 절차가 반복됩니다.

첫 번째 인덱스부터 시작하여 첫 번째 요소와 두 번째 요소를 비교하며 프로세스가 반복됩니다. 이미 정렬이 완료된 4번 인덱스에 대한 정렬은 이루어지지 않습니다.

정렬되지 않은 마지막 요소까지 수행됩니다.

정렬되지 않은 모든 요소가 올바른 위치에 배치되며 배열이 정렬됩니다.

출처

시간 복잡도

버블 정렬은 두 개의 반복문을 사용하여 작동합니다. 외부 반복문은 리스트를 한 번 훑어보며 요소를 비교하고 교환하는 역할을 합니다.
내부 반복문은 현재 요소와 다음 요소를 비교하고 교환하는 역할을 수행합니다.
최악의 경우 버블 정렬은 모든 요소를 비교하고 교환해야하므로 비교 횟수와 교환 횟수 모두 n(n-1)/2 번이 되기 떄문에 시간 복잡도는 O(n^2)가 됩니다.
즉 이미 정렬된 리스트를 정렬할 때 또한 교환은 전혀 발생하지 않음에도 불구하고 비교는 여전히 이루어짐으로 동일한 O(n^2) 시간 복잡도를 가집니다.

코드

package io.github.ones1kk.study.sorting;

public class BubbleSort {

    public static void bubbleSort(int[] arr, int size) {
        for (int i = 1; i < size; i++) {
            boolean swapped = false;

            for (int j = 0; j < size - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    swapped = true;
                }
            }

            if (!swapped) {
                break;
            }

        }

    }

    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }

}

좀더 자세한 코드는 이 곳에서 확인 가능합니다.

오탈자 및 오류 내용을 댓글 또는 메일로 알려주시면, 검토 후 조치하겠습니다.