버블 정렬 (Bubble Sort)
개요
버블 정렬(Bubble Sort) 은 인접한 요소들을 반복적으로 비교 및 교환하여 배열을 정렬하는 알고리즘으로, 시간 복잡도는 O(n²)입니다.
왜 ‘버블’ 인가?
버블 정렬의 과정은 문자 그대로 마치 공기방울이 수면 위로 떠오르듯 가장 큰 레코드가 한 칸씩 한 칸씩 오른쪽으로 떠올라오는 과정이다 (주우석, 2015)
위 말 그대로 보면 바로 옆에 있는 데이터와 비교해서 위치를 교환하는 방식이다.
사실 단계별로 볼 때 가장 레코드가 큰 데이터가 맨 뒤로 배치되는 선택 정렬과 결과적으로는 비슷하겠으나, 비교 대상이 바로 옆이며, 교환 과정이 계속 일어난다는 점이 차이점이 된다.
버블정렬(배열 A, 길이 n)
for i = 0 to n-1
for j = 0 to n-2-i
if A[j] > A[j+1]
A[j]와 A[j+1]을 교환
Python
복사
버블 정렬 동작 과정
위 예시를 보면 처음부터 두개만 비교를 하고, 크기가 큰 데이터를 오른쪽으로 이동시킨다.
같은 방식을 끝에 도착할 때까지 반복하여 정렬한다.
버블 정렬을 배열 [6, 5, 3, 1, 8, 7, 2, 4]에 적용한 동작 과정을 단계별로 자세히 설명하자면,
1.
첫 번째 순회 (i = 0):
•
배열의 첫 번째 요소부터 마지막 요소 직전까지 인접한 두 요소를 비교하여 큰 값을 오른쪽으로 이동시킴.
•
6과 5 비교: 6 > 5이므로 교환 → [5, 6, 3, 1, 8, 7, 2, 4]
•
6과 3 비교: 6 > 3이므로 교환 → [5, 3, 6, 1, 8, 7, 2, 4]
•
6과 1 비교: 6 > 1이므로 교환 → [5, 3, 1, 6, 8, 7, 2, 4]
•
6과 8 비교: 6 < 8이므로 교환하지 않음 → [5, 3, 1, 6, 8, 7, 2, 4]
•
8과 7 비교: 8 > 7이므로 교환 → [5, 3, 1, 6, 7, 8, 2, 4]
•
8과 2 비교: 8 > 2이므로 교환 → [5, 3, 1, 6, 7, 2, 8, 4]
•
8과 4 비교: 8 > 4이므로 교환 → [5, 3, 1, 6, 7, 2, 4, 8]
첫 번째 순회가 끝난 후 가장 큰 값(8)이 배열의 끝으로 이동하게 됨.
배열 상태: [5, 3, 1, 6, 7, 2, 4, 8]
2.
두 번째 순회 (i = 1):
•
두 번째로 큰 값을 찾기 위해 첫 번째 요소부터 n-2 (인덱스 기준) 까지 비교함.
•
5와 3 비교: 5 > 3이므로 교환 → [3, 5, 1, 6, 7, 2, 4, 8]
•
5와 1 비교: 5 > 1이므로 교환 → [3, 1, 5, 6, 7, 2, 4, 8]
•
5와 6 비교: 5 < 6이므로 교환하지 않음 → [3, 1, 5, 6, 7, 2, 4, 8]
•
6과 7 비교: 6 < 7이므로 교환하지 않음 → [3, 1, 5, 6, 7, 2, 4, 8]
•
7과 2 비교: 7 > 2이므로 교환 → [3, 1, 5, 6, 2, 7, 4, 8]
•
7과 4 비교: 7 > 4이므로 교환 → [3, 1, 5, 6, 2, 4, 7, 8]
두 번째 순회가 끝난 후 두 번째로 큰 값(7)이 제자리에 위치함.
배열 상태: [3, 1, 5, 6, 2, 4, 7, 8]
3.
세 번째 순회 (i = 2):
•
세 번째로 큰 값을 찾기 위해 다시 비교를 시작함.
•
3과 1 비교: 3 > 1이므로 교환 → [1, 3, 5, 6, 2, 4, 7, 8]
•
3과 5 비교: 3 < 5이므로 교환하지 않음 → [1, 3, 5, 6, 2, 4, 7, 8]
•
5와 6 비교: 5 < 6이므로 교환하지 않음 → [1, 3, 5, 6, 2, 4, 7, 8]
•
6과 2 비교: 6 > 2이므로 교환 → [1, 3, 5, 2, 6, 4, 7, 8]
•
6과 4 비교: 6 > 4이므로 교환 → [1, 3, 5, 2, 4, 6, 7, 8]
세 번째 순회가 끝난 후 세 번째로 큰 값(6)이 제자리에 위치함.
배열 상태: [1, 3, 5, 2, 4, 6, 7, 8]
4.
네 번째 순회 (i = 3):
•
네 번째로 큰 값을 찾음.
•
1과 3 비교: 1 < 3이므로 교환하지 않음 → [1, 3, 5, 2, 4, 6, 7, 8]
•
3과 5 비교: 3 < 5이므로 교환하지 않음 → [1, 3, 5, 2, 4, 6, 7, 8]
•
5와 2 비교: 5 > 2이므로 교환 → [1, 3, 2, 5, 4, 6, 7, 8]
•
5와 4 비교: 5 > 4이므로 교환 → [1, 3, 2, 4, 5, 6, 7, 8]
네 번째 순회가 끝난 후 네 번째로 큰 값(5)이 제자리에 위치함.
배열 상태: [1, 3, 2, 4, 5, 6, 7, 8]
5.
다섯 번째 순회 (i = 4):
•
남은 요소들 중에서 비교.
•
1과 3 비교: 1 < 3이므로 교환하지 않음 → [1, 3, 2, 4, 5, 6, 7, 8]
•
3과 2 비교: 3 > 2이므로 교환 → [1, 2, 3, 4, 5, 6, 7, 8]
다섯 번째 순회가 끝난 후 다섯 번째로 큰 값(4)이 제자리에 위치함.
배열 상태: [1, 2, 3, 4, 5, 6, 7, 8]
6.
여섯 번째 순회 (i = 5):
•
마지막 남은 작은 값들끼리 비교
•
1과 2 비교: 1 < 2이므로 교환하지 않음 → [1, 2, 3, 4, 5, 6, 7, 8]
이 순회 후 모든 값이 정렬됨.
버블 정렬 알고리즘 코드 (C++)
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 마지막 i개의 요소는 이미 정렬되었으므로 비교할 필요가 없음
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 두 요소 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printArray(arr, n);
return 0;
}
C++
복사
•
관련 백준 문제
◦
아무래도 정렬 결과를 하면 다 똑같이 나오니까 문제는 다른 방식을 사용하는 것 같다. 조심할 것은 백준에서 버블 정렬이라고 치면 나오는 대표적인 문제는 버블 정렬 시간 복잡도를 사용하는게 아니다…
#include <iostream>
using namespace std;
int num1, num2;
int count = 0;
int k;
int bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// 마지막 i개의 요소는 이미 정렬되었으므로 비교할 필요가 없음
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 두 요소 교환
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
count++;
if ( count == k ) {
num1 = arr[j];
num2 = arr[j+1];
return 0;
}
}
}
}
return -1;
}
int main() {
int num;
// 배열 및 소트 회수 입력
cin >> num >> k;
int arr[num];
for(int i=0; i<num; i++) {
cin >> arr[i];
}
int n = sizeof(arr) / sizeof(arr[0]);
int res = bubbleSort(arr, n);
if (res != -1) {
cout << num1 << " " << num2;
}
else {
cout << -1;
}
return 0;
}
C++
복사
요약
•
버블 정렬은 인접한 두 요소를 비교하고, 큰 값을 오른쪽으로 이동시키는 과정을 반복하여 배열을 정렬하는 방법임.
•
각 순회가 끝날 때마다 가장 큰 값이 배열의 끝부분으로 이동함.
•
시간 복잡도는
REFERENCES
1.
주우석, 2015, C/C++로 배우는 자료구조론, 한빛미디어
Written by Changyu Lee, 2024-10-13