C와 C++의 버블 정렬(bubble sort)
이 레슨에서는 순서가 잘못된 이웃 요소 쌍을 계속 맞바꾸는 버블 정렬을 구현합니다.
소개
버블 정렬은 배열을 여러 번 훑으면서 이웃한 두 요소를 비교하고, 순서가 잘못되어 있으면 맞바꿉니다. 한 번 훑을 때마다 아직 정렬되지 않은 값 중 가장 큰 값이 조금씩 배열 끝으로 이동합니다.
핵심 정리
- 빈 입력, 요소 하나, 중복 값, 이미 정렬된 데이터로 테스트하세요.
- 먼저 코드가 올바르게 동작하게 만든 다음 최적화하세요.
- 실제 코드에서는 표준 라이브러리의 이미 만들어진 함수를 우선 쓰세요.
C와 C++의 버블 정렬(bubble sort) 시각화
O(n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
C와 C++ 코드 예제
C
main.c
#include <stdio.h>
int main(void) {
int values[] = {5, 1, 4, 2};
for (int end = 3; end > 0; --end) {
int changed = 0;
for (int index = 0; index < end; ++index) {
if (values[index] > values[index + 1]) {
int temporary = values[index];
values[index] = values[index + 1];
values[index + 1] = temporary;
changed = 1;
}
}
if (!changed) break;
}
for (int index = 0; index < 4; ++index) {
printf("%d ", values[index]);
}
}
1 2 4 5C++
main.cpp
#include <iostream>
#include <vector>
int main() {
std::vector values{5, 1, 4, 2};
for (auto end = values.end(); end != values.begin(); --end) {
bool changed = false;
for (auto item = values.begin(); item + 1 != end; ++item) {
if (*item > *(item + 1)) {
std::iter_swap(item, item + 1);
changed = true;
}
}
if (!changed) break;
}
for (int value : values) {
std::cout << value << ' ';
}
}
1 2 4 5C와 C++ 비교
변수 changed는 그 훑기에서 교환이 한 번이라도 있었는지를 나타냅니다. 교환이 없었다면 배열은 이미 정렬된 것이므로 반복을 일찍 끝내며, 이미 정렬된 배열은 O(n)이면 됩니다. 최악의 경우 O(n²)이 필요하므로 주로 학습용으로 씁니다. 실제 C++ 코드에서는 보통 std::sort를 씁니다.
C
반복문, 포인터, 길이, 임시 버퍼를 모두 명시적으로 작성합니다.
C++
반복자와 표준 알고리즘이 처리 방식과 데이터를 저장하는 방식을 분리합니다.
연습 문제
두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.
- 종이에 비교 과정을 하나씩 따라가 보세요.
- 중복 값과 아주 크거나 작은 값으로 테스트해 보세요.
- 직접 작성한 코드의 실행 시간을 재고 표준 라이브러리와 비교해 보세요.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지