[알고리즘]버블 정렬(Bubble Sort)

Goal

• 버블 정렬에 대해 설명할 수 있다.
• 버블 정렬 과정에 대해 설명할 수 있다.
• 버블 정렬을 구현할 수 있다.
• 버블 정렬의 시간복잡도와 공간복잡도를 계산할 수 있다.

Abstract

Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

Process

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를.. 이와 같은 방식으로 N-1번째 원소와 N번째 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.
2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

Code

void bubbleSort(int[] arr) {
	int temp = 0;
    for(int i = 0; i < arr.length; i++) {     // 1
    	for(int j = 1; j < arr.length-i; j++) { // 2
        	if(arr[j-1] > arr[j]) {           // 3
            	temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

1. 제외될 원소의 갯수를 의미한다. 1회전이 끝난 후 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다.
2. 원소를 비교할 index를 뽑을 반복문이다. j는 현재 원소를 가르키고 j-1은 이전 원소를 가리키게 되므로, j는 1부터 시작하게 된다.
3. 현재 가르키고 있는 두 원소의 대소를 비교한다. 현재 원소보다 이전 원소가 더 크다면 이전 원소가 뒤로 가야하기 때문에 자리를 교환한다.

시간복잡도

시간복잡도를 계산하면 (n-1) + (n-2) + ... + 2 + 1 => n(n-1)/2이므로, O(n^2)이다. 버블정렬은정렬이 되어있던, 되어있지않던 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(n^2)으로 동일하다.

공간복잡도

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

장점

• 구현이 간단하고, 소스코드가 직관적이다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬
• 안정 정렬이다.

단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(n^2)으로 비효율적이다.
• 정렬이 되어있지 않은 원소가 정렬이 되기 위해 교환연산이 많이 발생한다.