버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

인접한 두 요소를 비교하여 큰 값을 뒤로 보내는 과정을 반복하여 정렬하는 단순한 알고리즘

목적: 교육용, 소규모 데이터, 단순 구현

특징: 단순, 안정 정렬, 제자리 정렬, 비효율적

동작: n-1번 패스 수행. 각 패스마다 배열의 처음부터 인접한 두 요소를 비교하여 왼쪽이 크면 교환. 한 패스가 끝나면 가장 큰 값이 배열 끝으로 "버블링"되어 이동. 다음 패스에서는 마지막 요소를 제외하고 반복

• •예: [5,3,8,1] → 패스1: [3,5,1,8] → 패스2: [3,1,5,8] → 패스3: [1,3,5,8]

시간 복잡도: 최선 O(n) - 이미 정렬됨(최적화 시), 평균·최악 O(n²)

공간 복잡도: O(1) - 제자리

최적화: 교환 없으면 조기 종료

장점: 단순한 구현, 안정 정렬, 제자리

단점: 매우 느림(O(n²)), 실용성 없음

적용사례: 교육, 소규모 데이터(<10개)

비교: 버블(단순/느림) vs 삽입(적응적) vs 병합(빠름/O(n log n))

연관: 정렬, 삽입 정렬, 선택 정렬, O(n²)