[Algorithm] 2-1 Bubble Sort(거품 정렬)

정렬 알고리즘
1. Bubble Sort(거품 정렬) ⇠
2. Selection Sort(선택 정렬)
3. Insertion Sort(삽입 정렬)
4. Quick Sort(퀵 정렬)
5. Merge Sort(병합 정렬)
6. Heap Sort(힙 정렬)
7. Radix Sort(기수 정렬)
8. Counting Sort(계수 정렬)

기본 개념

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘, 더 작은 값을 앞으로 보내는 정렬
• 선택 정렬과 기본 개념이 유사하다
• 원소의 이동이 마치 거품이 수면 위로 올라오는 것과 같다고 해서 거품이라는 단어가 붙여졌다.

특징

• 거품 정렬은 한번의 정렬이 끝날 때마다 점점 큰 값들이 뒤에서부터 앞으로 하나씩 쌓이기 때문에 후반으로 갈수록 정렬 범위가 하나씩 줄어들게 된다.
  (∵ 다음 순서에서는 이전 순서에서 뒤로 보내놓은 가장 큰 값이 있는 위치 전까지만 비교해서 정렬하기 때문)
• 제일 작은 값을 찾아서 맨 앞에 위치시키는 선택 정렬과 비교했을 때 정반대의 정렬 방향을 가진다.
• 다른 정렬 알고리즘에 비해서 자리 교대(swap)가 빈번하게 일어나는 경향이 있다.

구현(Java)

public class Bubble {
	public static void sort(int[] arr) {
    	for (int i = arr.length - 1; i > 0; i--) {
        	// 1. i 길이 만큼 arr 앞에서부터 인접한 두 수 비교
            // 2. 한번의 loop이 끝나면 맨 뒤에 있는 수는 정렬된 수 이므로 길이를 1 줄이고 다음 loop 진행
        	for (int j = 0; j <= i; j++) {
            	if (arr[j] > arr[j+1]) {
                	swap(arr, j, j+1);
                }
            }
        }
    }
    
    private static void swap(int[] arr, int a, int b) {
    	int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}

복잡도

• 공간 복잡도 : 별도의 추가 공간을 사용하지 않고 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가진다.
• 시간 복잡도 : 루프문을 통해 맨 뒤에서부터 맨 앞까지 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N)의 시간을 소모하며, 하나의 루프에서는 인접한 값들의 대소 비교 및 자리 교대를 위해서 O(N)의 시간이 필요하게 된다. 따라서 총 시간 복잡도는 O(N^2) 이다.
• 하지만, 부분적으로 정렬되어 있는 배열에 대해서는 최적화를 통해서 성능을 개선할 수 있으며, 완전히 정렬되어 있는 배열이 들어올 경우 O(N)까지도 시간 복잡도를 향상 시킬 수 있다.