[알고리즘] 버블 정렬(bubble sort)

버블 정렬이란?

버블 정렬(거품 정렬): 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하여 정렬하는 알고리즘이다.

버블 정렬

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 이를 양방향으로 번갈아 수행하면 칵테일 정렬이 된다.

 

 

1) 그림과 같이 정렬되지 않은 배열이 있다고 가정하자.

2) 맨 앞부터 비교를 하게 된다. 그럼 7과 2를 비교하게 되는데, 7이 더 크기 때문에 두 수를 바꾼다.

* 버블 정렬을 동그라미 표시(거품)를 하며 바꾼다는 의미로 외웠음

3)  2와 7을 바꾼 뒤 한 칸 앞으로 가서 다시 7과 0을 비교한다.

4) 마찬가지로 7이 더 크기 때문에 두 원소를 교환한다. 이런 식으로 제일 큰 수 부터 정렬하는 방법이 bubble sort 이다.

 

시간복잡도

(n-1) + (n-2) + (n-3) ... + 1 이므로 O(n^2)이다. 정렬이 돼있던 안돼있던, 무조건 비교를 해야하기 때문에 최선, 평균, 최악의 경우 같은 시간복잡도를 가진다.

 

JAVA CODE

public class BubbleSort {
    public int[] bubbleSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) Sort.swap(arr, j, j + 1);
            }
        }
        return arr;
    }
}

public class Sort {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}