거품 정렬(Bubble sort)

1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다.

2. 현재 원소가 다음 원소보다 크면 원소를 교환한다.

3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다.

4. 맨 마지막 숫자는 정렬된 숫자이다.

5. 맨 마지막 숫자를 제외하고 1번 부터 5번까지 반복한다.

자바 코드로 구현하면 다음과 같다.

static void bubble_sort(int[] arr) {
	bubble_sort(arr, arr.length - 1);
}

static void bubble_sort(int[] arr, int last) {
	if (last > 0) {
    	for (int i = 0; i < last; i++) {
        	if (arr[i] > arr[i+1]) {
            	swap(arr, i, i+1);
            }
        }
    
    	bubble_sort(arr, last - 1);
    }

}

static void swap(int[] arr, int source, int target) {
	int temp = arr[source];
    arr[source] = arr[target];
    arr[target] = temp;
}

시간복잡도는 O(n²)

---

참조한 책, 유튜브 및 사이트

https://www.youtube.com/watch?v=YbsQiiubO74
https://sylagape1231.tistory.com/17