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

---

버블 정렬 기본

• 인접한 두 원소를 비교해 가면서 자리를 바꾸는 방식의 알고리즘
• 배열의 맨 뒤부터 정렬이 됨

---

정렬 과정

과정 예시

(28 13) 23 25 19 : 28 > 13 스왑

13 (28 23) 25 19 : 28 > 23 스왑

13 23 (28 25) 19 : 28 > 25 스왑

13 23 25 (28 19) : 28 > 19 스왑

(13 23) 25 19 28 : 28 최댓값으로 고정, 13 < 23 스왑 X

13 (23 25) 19 28 : 23 < 25 스왑 X

13 23 (25 19) 28 : 25 > 19 스왑

(13 23) 19 25 28 : 25 다음 최댓값으로 고정, 13 < 23 스왑 X

13 (23 19) 25 28 : 23 > 19 스왑

(13 19) 23 25 28 : 23 다음 최댓값으로 고정, 13 < 19 스왑 X

13 19 23 25 28 : 19 다음 최댓값으로 고정, 정렬 완료

---

시간 복잡도

$O(N^2)$

---

구현

void bubbleSort(int[] arr) {
    int temp = 0;
    for(int i = 0; i < arr.length; i++) {
        for(int j= 1 ; j < arr.length-i; j++) {
            if(arr[j]<arr[j-1]) {
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

---