정렬(Sorting)이란?
정렬은 데이터 요소들을 오름차순 또는 내림차순 순서로 배열하는 과정을 의미합니다. 정렬된 데이터는 탐색 속도를 크게 향상시키기 때문에 프로그래밍에서 매우 중요한 기초 개념입니다.
C 언어의 주요 정렬 기법
C 언어에서 널리 사용되는 대표적인 정렬 알고리즘은 다음과 같습니다.
- 버블 정렬(Bubble Sort) – 인접한 두 요소를 반복적으로 비교·교환하며 정렬
- 선택 정렬(Selection Sort) – 최솟값을 찾아 앞쪽에 차례로 배치
- 삽입 정렬(Insertion Sort) – 각 요소를 이미 정렬된 부분의 올바른 위치에 삽입
- 퀵 정렬(Quick Sort) – 분할 교환(Partition Exchange) 방식 기반의 고속 정렬
- 병합 정렬(Merge Sort) – 배열을 분할한 뒤 병합하며 정렬하는 외부 정렬 방식
삽입 정렬(Insertion Sort)의 핵심 로직
삽입 정렬은 카드 게임에서 손에 든 카드를 정렬하는 방식과 유사합니다. 두 번째 요소부터 시작해 현재 요소를 앞쪽의 정렬된 구간과 비교한 후, 적절한 위치에 삽입하는 방식으로 동작합니다.
for(i = 1; i <= n - 1; i++){
for(j = i; j > 0 && a[j - 1] > a[j]; j--){
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}동작 원리 이해하기
정렬되지 않은 상태의 요소들을 예로 들어 살펴보겠습니다. 첫 번째 요소는 이미 정렬되어 있다고 가정하고, 두 번째 요소부터 차례대로 앞쪽의 정렬된 구간과 비교하여 자신의 올바른 자리에 삽입됩니다. 이 과정을 마지막 요소까지 반복하면 전체 배열이 완전히 정렬됩니다.
C 언어 삽입 정렬 예제 코드
다음은 삽입 정렬 기법을 사용해 요소를 정렬하는 C 프로그램입니다.
#include<stdio.h>
int main() {
int a[50], i,j,n,t;
printf("enter the No: of elements in the list:\n");
scanf("%d", &n);
printf("enter the elements:\n");
for(i=0; i<n; i++){
scanf ("%d", &a[i]);
}
for(i = 1; i <= n - 1; i++){
for(j=i; j > 0 && a[j - 1] > a[j]; j--){
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
printf ("after insertion sorting the elements are:\n");
for (i=0; i<n; i++)
printf("%d\t", a[i]);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.
Enter the No: of elements in the list:
10
Enter the elements:
34
125
2
6
78
49
1
3
89
23
After insertion sorting the elements are:
1 2 3 6 23 34 49 78 89 125
삽입 정렬의 시간 복잡도와 특징
- 최선의 경우(이미 정렬된 데이터): O(n)
- 평균 및 최악의 경우: O(n²)
- 공간 복잡도: O(1) – 제자리(in-place) 정렬 방식
삽입 정렬은 구현이 간단하고, 데이터가 거의 정렬되어 있는 경우 매우 효율적으로 동작하며, 같은 값의 상대적 순서가 유지되는 안정 정렬(stable sort)이라는 장점이 있습니다.