1. 문제 설명
버블 정렬(Bubble Sort)은 가장 간단한 정렬 알고리즘 중 하나로, 인접한 두 개의 요소를 비교하여 정렬하는 방식입니다. 이 알고리즘의 특징은 직관적이고 구현이 간단하다는 것입니다. 하지만, 효율성 면에서는 다른 정렬 알고리즘에 비해 느린 편입니다.
문제
주어진 정수 배열을 버블 정렬을 이용해 오름차순으로 정렬하시오.
입력 예시:
[64, 34, 25, 12, 22, 11, 90]
출력 예시:
[11, 12, 22, 25, 34, 64, 90]2. 문제 분석
버블 정렬의 핵심 아이디어는 인접한 두 요소를 비교하여 정렬하는 것입니다. 배열의 첫 번째 요소부터 시작해 두 개씩 비교해 나가며, 더 큰 값을 뒤쪽으로 보내는 과정을 반복합니다. 이 과정을 여러 번 반복하여 전체 배열이 정렬되게 됩니다.
버블 정렬 알고리즘 작동 원리
예를 들어, 배열 [64, 34, 25, 12, 22, 11, 90]에 버블 정렬을 적용하는 과정을 살펴보겠습니다:
- 1차 반복:
- 64과 34 비교 → [34, 64, 25, 12, 22, 11, 90]
- 64과 25 비교 → [34, 25, 64, 12, 22, 11, 90]
- 64과 12 비교 → [34, 25, 12, 64, 22, 11, 90]
- 64과 22 비교 → [34, 25, 12, 22, 64, 11, 90]
- 64과 11 비교 → [34, 25, 12, 22, 11, 64, 90]
- 64과 90 비교 → [34, 25, 12, 22, 11, 64, 90] (변화 없음)
- 2차 반복: (앞의 가장 큰 수가 뒤로 이동했으므로, 마지막 요소는 비교하지 않음)
- 34과 25 비교 → [25, 34, 12, 22, 11, 64, 90]
- 34과 12 비교 → [25, 12, 34, 22, 11, 64, 90]
- 34과 22 비교 → [25, 12, 22, 34, 11, 64, 90]
- 34과 11 비교 → [25, 12, 22, 11, 34, 64, 90]
- 34과 64 비교 → [25, 12, 22, 11, 34, 64, 90] (변화 없음)
- (이러한 과정을 반복하여 최종적으로 정렬된 배열을 얻게 됩니다.)
3. 시간 복잡도
버블 정렬의 시간 복잡도는 최악의 경우 O(n^2)입니다. 이는 배열의 크기가 n일 때 모든 쌍을 비교해야 하므로 발생합니다. 평균적인 경우에도 O(n^2)의 성능을 가지며, 최상의 경우(이미 정렬된 경우)에는 O(n)입니다.
4. 코드 구현
다음은 C++로 구현한 버블 정렬 코드입니다:
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
cout << "정렬된 배열: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}5. 코드 설명
#include <iostream>: C++ 표준 입출력 라이브러리를 포함합니다.void bubbleSort(int arr[], int n): 정렬할 배열과 배열의 크기를 매개변수로 받는 함수입니다.- 이중 for 루프를 사용하여 배열의 요소를 비교하고, 필요시 스왑을 수행합니다. 내부 루프에서
arr[j]와arr[j+1]를 비교하여 더 큰 값을 뒤로 이동시킵니다. int main(): 프로그램의 진입점이며, 정렬할 배열을 초기화하고,bubbleSort함수를 호출하여 정렬합니다.- 정렬된 배열을 출력합니다.
6. 성능 분석
버블 정렬은 구현이 간단하다는 장점이 있지만, 큰 규모의 데이터에 대해서는 비효율적입니다. 실제로 실전에서 자주 사용되지는 않지만, 자료구조와 알고리즘을 학습하는 과정에서 이해도를 높이는 데에 좋은 예제가 될 수 있습니다.
7. 마무리
이번 강좌를 통해 버블 정렬의 개념과 C++ 구현을 살펴보았습니다. 알고리즘 문제를 풀 때는 단순히 문제를 해결하는 것뿐만 아니라, 그 과정에서 다양한 최적화 기법을 고려하는 것이 중요합니다. 다음 강좌에서는 더 효율적인 정렬 알고리즘, 예를 들어 퀵 정렬이나 병합 정렬에 대해 알아보겠습니다. 감사합니다!