버블 정렬(Bubble Sort)

개념

버블 정렬은 바로 옆에 있는 값과 비교해서 우선 순위가 높은 값을 앞으로 보낸다.

예제

다음은 5개의 정수 배열 {5, 3, 4, 2, 1} 을 오름차순으로 버블 정렬하는 과정을 보여준다.

다음 그림과 같이 인접한 두 수를 비교하고 앞에 있는 수가 뒤에 있는 수보다 클 때 교환하는 과정을 반복하며 끝까지 진행하면 가장 큰 수인 5가 맨 뒤에 오게 된다. 이렇게 되면 첫 번째 순회가 끝난다. 그 이후에는 마지막 인덱스를 제외하면서 계속 순회하며 정렬하는 과정을 반복한다.

구현

class Sort {
	public static void 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]) {
                    swap(j, j + 1, arr);
                }
            }
        }
    }

    public static void swap(int idx1, int idx2, int[] arr) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}

시간복잡도

N 개의 데이터를 버블 정렬한다면 연산횟수는 다음과 같다.

N + (N -1) + (N-2) + ... + 3 + 2 + 1

 

이를 등차수열의 합 공식으로 표현하면 다음과 같다.

(N + 1) * N /2

 

위 공식에서 최고차항을 제외하면 N^2 로

버블정렬은 O (N^2) 의 시간 복잡도를 가진다고 말할 수 있다.