C 언어 정렬 기법 총정리 – 버블 정렬의 원리와 구현 예제

문제

C 언어에서 사용할 수 있는 다양한 정렬 기법에는 어떤 것들이 있을까요? 그중 하나를 골라 예제와 함께 자세히 설명해 보겠습니다.

해결 방법

C 언어에서 널리 사용되는 대표적인 정렬 기법은 다음과 같이 다섯 가지입니다.

• 버블 정렬(Bubble Sort), 또는 교환 정렬(Exchange Sort)
• 선택 정렬(Selection Sort)
• 삽입 정렬(Insertion Sort), 또는 선형 정렬(Linear Sort)
• 퀵 정렬(Quick Sort), 또는 파티션 교환 정렬(Partition Exchange Sort)
• 병합 정렬(Merge Sort), 또는 외부 정렬(External Sort)

버블 정렬(Bubble Sort)이란?

버블 정렬은 '교환 정렬'이라고도 불리는 가장 단순한 정렬 기법입니다. 두 요소의 값을 비교하여 순서가 맞지 않으면 서로 자리를 교환(swap)하는 방식으로 동작하며, 값이 거품처럼 떠오르며 제자리를 찾아간다고 해서 '버블'이라는 이름이 붙었습니다.

동작 절차

• 첫 번째 요소를 목록의 나머지 요소들과 차례대로 비교하고, 순서가 맞지 않으면 서로 교환(swap)합니다.

• 모든 요소가 정렬될 때까지 목록의 다른 요소들에 대해서도 같은 과정을 반복합니다.

이해를 돕기 위해 다음과 같은 요소들이 주어졌다고 가정해 보겠습니다.

30 50 40 10 20

1회전 (First Pass)

첫 번째 요소(a[0])를 나머지 요소들과 비교합니다.

a[0] > a[1] : 30 > 50 (거짓) → 교환 없음
a[0] > a[2] : 30 > 40 (거짓) → 교환 없음
a[0] > a[3] : 30 > 10 (참)   → 교환
a[0] > a[4] : 10 > 20 (거짓) → 교환 없음

1회전 후 배열의 상태:

10 50 40 30 20

2회전 (Second Pass)

두 번째 요소(a[1])를 나머지 요소들과 비교합니다.

a[1] > a[2] : 50 > 40 (참) → 교환
a[1] > a[3] : 40 > 30 (참) → 교환
a[1] > a[4] : 30 > 20 (참) → 교환

2회전 후 배열의 상태:

10 20 50 40 30

3회전 (Third Pass)

세 번째 요소(a[2])를 나머지 요소들과 비교합니다.

a[2] > a[3] : 50 > 40 (참) → 교환
a[2] > a[4] : 40 > 30 (참) → 교환

3회전 후 배열의 상태:

10 20 30 50 40

4회전 (Fourth Pass)

네 번째 요소(a[3])를 나머지 요소들과 비교합니다.

a[3] > a[4] : 50 > 40 (참) → 교환

4회전 후 최종적으로 정렬된 배열:

10 20 30 40 50

핵심 로직 (의사 코드)

버블 정렬의 핵심 로직은 아래와 같이 중첩 반복문으로 간단하게 표현할 수 있습니다.

for (i=0; i<n-1; i++){
    for (j=i+1; j<n; j++){
        if (a[i] > a[j]){
            t=a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
}

시간 복잡도와 특징

버블 정렬의 시간 복잡도는 최악 및 평균 경우 O(n²), 이미 정렬된 데이터의 최선의 경우 O(n)입니다. 추가 메모리가 필요 없는 제자리(in-place) 정렬이라 공간 복잡도는 O(1)입니다. 구현이 매우 직관적이라 학습용으로 적합하지만, 데이터 양이 많아지면 성능이 급격히 저하되므로 실무에서는 퀵 정렬이나 병합 정렬 같은 고성능 알고리즘이 주로 사용됩니다.

예제 프로그램

다음은 버블 정렬 기법을 구현한 완전한 C 프로그램입니다.

#include<stdio.h>
int main(){
    int a[50], i,j,n,t;
    printf("enter the No: of elements in the list:
");
    scanf("%d", &n);
    printf("enter the elements:
");
    for(i=0; i<n; i++){
        scanf ("%d", &a[i]);
    }
    printf("Before bubble sorting the elements are:
");
    for(i=0; i<n; i++)
        printf("%d 	
", a[i]);
    for (i=0; i<n-1; i++){
        for (j=i+1; j<n; j++){
            if (a[i] > a[j]){
                t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
    printf ("after bubble sorting the elements are:
");
    for (i=0; i<n; i++)
        printf("%d	", a[i]);
    return 0;
}

실행 결과

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

enter the No: of elements in the list:
5
enter the elements:
12 11 45 26 67
Before bubble sorting the elements are:
12
11
45
26
67
after bubble sorting the elements are:
11 12 26 45 67

마무리

버블 정렬은 비교와 교환이라는 기본 개념만으로 정렬을 수행하는 가장 직관적인 알고리즘입니다. 효율성 면에서는 다소 떨어지지만, 정렬 알고리즘의 동작 원리를 이해하는 첫걸음으로 가장 적합하며, 이를 익힌 후 선택 정렬, 삽입 정렬, 퀵 정렬 등 더 발전된 기법으로 확장해 나가면 됩니다.