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

1. 개념

• 인접한 두 값을 비교하여 정한 조건에 맞지 않는 경우 자리를 교환하며 정렬하는 알고리즘
• 정렬 할 때 원소가 이동하는 모습이 마치 거품이 위로 올라오는 듯한 모습과 같다는 점에서 착안함

2. 과정

오름차순 기준(왼쪽 요소의 값 < 오른쪽 요소의 값)

1. 1번째 원소와 2번째 원소, 2번째 원소와 2번째 원소, 3번째 원소와 4번째 원소 ... 이런 식으로 n-1번째 원소와 n번째 원소를 각각 비교하며, 왼쪽 요소의 값이 오른쪽의 값보다 클 경우 서로 교환한다. 이 방식으로 (마지막-1)번째 원소와 마지막 원소까지 비교해준다.
2. 첫 번째 패스(비교·교환 작업)를 수행하고 나면 가장 큰 값이 맨 끝으로 이동하게 된다. 마지막 원소는 정렬된 상태이므로, 마지막 원소를 제외하고 두 번째 패스를 진행한다. 두 번째 패스를 수행하고 나면 정렬된 마지막 두 개의 원소(마지막-1, 마지막)를 제외하고 다음 패스를 수행한다. 이 방식으로 정렬된 원소를 제외하며 패스를 수행하여 모든 원소를 정렬한다.

※ 수행하는 패스의 횟수는 n-1회이다. 그 이유는 패스를 수행할 때마다 마지막 요소는 이미 정렬된 상태기 때문에, 정렬할 요소가 하나씩 줄어들기 때문이다.

3. 구현

void bubbleSort(int[] arr) {
	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.
            	int temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
	}
}

1. 정렬된 원소의 갯수 표현을 위한 반복문(현재 패스에서 제외할 원소의 갯수)
2. 원소 비교를 위한 반복문(패스). j는 현재 인덱스, j-1은 j 앞의 인덱스를 나타내므로 j는 1부터 시작해야 한다(0부터 시작하면 arr[j-1]는 배열의 범위를 벗어나게 된다). 또한 패스를 수행할 때마다 끝 쪽의 요소가 정렬이 된 상태이므로, 정렬된 원소를 제외하기 위해 j를 비교하는 범위는 j<arr.length-i 즉, 배열의 크기-정렬된 원소의 갯수가 된다.
3. 만약 왼쪽의 원소값이 오른쪽의 원소값보다 크다면 서로 교환한다.

4. 성능 분석

/* 배열의 크기를 n으로 가정*/
for(int i=0; i<n; i++) {
	for(int j=1; j<n-i; j++) {
        if(arr[j-1] > arr[j]) {	
            int temp = arr[j-1];
            arr[j-1] = arr[j];
            arr[j] = temp;
        }
    }
 }

바깥 루프 i	안쪽 루프 j에서의 비교 횟수
i=0	n-1
i=1	n-2
i=2	n-3
...	...
i=(n-2)	2
i=(n-1)	1

• 총 비교 횟수 = 안쪽 루프 j에서의 비교 횟수의 합
  (n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2
  ∴ 시간복잡도 O(n^2)

• 원하는 순서로 이미 정렬되어 있는 경우(최선) → O(n)
  10 20 30 40 50

• 역순으로 정렬되어 있는 경우(최악) → O(n^2)
  50 40 30 20 10
40 30 20 10 50 => n-1
  30 20 10 40 50 => n-2
  20 10 30 40 50 => ...
  10 20 30 40 50 => 1

5. 특징

• 한 칸 이상 떨어져 있는 요소를 교환하는 것이 아닌 서로 이웃한 요소에 대해서만 교환하므로 안정적 정렬 알고리즘이라 할 수 있다.
• 데이터 저장 공간으로 입력 배열 arr, 입력 크기 n, 추가적인 저장 공간은 상수 개(제어변수 i와 j, 데이터 교환을 위한 변수 temp)가 필요하므로 제자리 정렬이라 할 수 있다.
• 선택 정렬에 비해 데이터 교환이 더 많이 발생하므로 선택 정렬보다 비효율적이다.

---

📖 참고

• Bohyoh Shibata. (2020). Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바편(강민 옮김). 이지스퍼블리싱
• 거품 정렬 (Bubble Sort)