• 인접한 데이터끼리 비교하여 정렬하는 방식
  • 한 번 순회할 때마다 가장 큰 값이 맨 뒤로 떠오르는 모습이 거품과도 같다 하여 붙은 이름이라 함
• 코드가 단순하여 추가 메모리는 필요 없지만, 대규모 데이터 측면에선 비효율적
• 시간 복잡도 : 평균 또는 최악 O(n²), 최선은 O(n) 이지만 이미 정렬된 경우
• 공간 복잡도 : O(1)
• 안정 정렬 : 인접한 두 값이 같으면 교환하지 않으므로 같은 값의 기존 순서가 유지됨
• 최선 O(n)은 한 번의 순회에서 교환이 한 번도 없으면 멈추는 조기 종료를 넣었을 때만 성립, 아래 코드처럼 조기 종료가 없으면 이미 정렬된 배열도 O(n²)
• 실무에서 직접 쓸 일은 없고, 교환 과정이 눈에 보여 교육용으로 남아 있음

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n) {
        for (j in 0 until n-1-i) {
            // 인접 요소끼리 비교하여 swap 진행
            if (arr[j] > arr[j + 1]) {
                val temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
}