버블 정렬과 삽입 정렬
간단한 정렬을 알아봅니다
버블 정렬과 삽입 정렬은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
간단한 정렬
버블 정렬과 삽입 정렬은 가장 간단한 두 가지 비교 정렬입니다. 두 정렬 모두 최악의 경우 O(n²)이지만 이해하기 쉽고 크기가 작거나 거의 정렬된 배열에 유용합니다.
버블 정렬의 작동 방식
버블 정렬은 배열을 반복해서 순회하며 순서가 잘못된 인접한 쌍을 교환합니다. 한 번의 전체 순회가 끝나면 아직 정렬되지 않은 원소 중 가장 큰 원소가 거품처럼 올라와 배열 끝의 최종 위치에 놓입니다.
두 정수 교환하기
재사용 가능한 교환 보조 함수가 정렬 코드를 깔끔하게 만들어 줍니다.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}버블 정렬 구현
중첩 반복문을 사용합니다. 바깥 반복문은 순회 횟수를 세고, 안쪽 반복문은 인접한 쌍을 비교해 교환합니다. i번째 순회가 끝나면 마지막 i개 원소가 정렬됩니다.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}조기 종료 최적화
전체 순회에서 한 번도 교환하지 않았다면 배열은 이미 정렬된 상태이므로 중단할 수 있습니다. 따라서 이미 정렬된 입력에서는 버블 정렬이 O(n)이 됩니다.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}삽입 정렬의 작동 방식
삽입 정렬은 앞부분에 정렬된 영역을 만듭니다. 새로운 원소마다 정렬된 영역의 더 큰 원소를 오른쪽으로 이동한 뒤 새 원소를 알맞은 위치에 넣습니다. 손에 든 카드를 정렬하는 방식과 비슷합니다.
삽입 정렬 구현
key = a[i]인 원소를 가져온 다음, a[0..i-1]에서 더 큰 모든 원소를 한 칸씩 오른쪽으로 이동하고 빈자리에 key를 삽입합니다.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}거의 정렬된 데이터에서의 삽입 정렬
삽입 정렬은 배열이 거의 정렬된 상태일 때 뛰어난 성능을 보입니다. 각 원소가 몇 자리만 이동하므로 O(n)에 가까워집니다. 이러한 이유로 혼합 정렬의 마무리 단계에 사용됩니다.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}안정성
두 정렬 모두 안정적입니다. 엄격한 초과 비교를 할 때만 교환하거나 이동하므로 같은 원소는 원래의 상대적 순서를 유지합니다. 여러 키를 기준으로 레코드를 정렬할 때 안정성이 중요합니다.
복잡도 비교
두 정렬 모두 평균과 최악의 경우 O(n²)이지만 실제 동작은 다릅니다.
- 버블 정렬: 교환이 많아 실제 코드에서는 거의 사용하지 않습니다
- 삽입 정렬: 쓰기 작업이 적고 작거나 거의 정렬된 배열에 매우 적합합니다
최적화를 적용하면 두 정렬 모두 최선의 경우 O(n)입니다.
연산 횟수 세기
최악의 경우인 역순 배열에서 삽입 정렬이 수행하는 비교 횟수를 세어 보겠습니다.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}빠른 확인
간단한 정렬에 대한 이해도를 확인해 보세요.
정리
두 가지 간단한 O(n²) 정렬을 배웠습니다.
- 버블 정렬은 매 순회마다 인접한 쌍을 교환합니다
- 삽입 정렬은 정렬된 앞부분에 원소를 이동하고 삽입합니다
- 두 정렬 모두 안정적이며, 최적화를 적용하면 정렬된 입력에서 O(n)이 됩니다
- 작은 데이터에서는 삽입 정렬이 실용적으로 더 나은 선택입니다
자주 묻는 질문
“버블 정렬과 삽입 정렬” 강의는 무료인가요?
네 — “버블 정렬과 삽입 정렬” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“버블 정렬과 삽입 정렬”에서 뭘 배우나요?
간단한 정렬을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“버블 정렬과 삽입 정렬” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.