[알고리즘/C언어] 기초 정렬 알고리즘 3종 (버블, 선택, 삽입 정렬) 개념 및 차이점 완전 정리 (시험 단골 주제)

컴퓨터공학과 알고리즘 시험, 자료구조 기말고사, 그리고 정보처리기사 실기 시험에서 가장 기본이 되면서도 단골로 출제되는 주제가 있습니다. 바로 기초 정렬 알고리즘 3가지 (버블 정렬, 선택 정렬, 삽입 정렬)입니다.

세 가지 정렬 알고리즘 모두 평균 시간 복잡도가 $O(N^2)$으로 동일하지만, 데이터를 정렬하는 내부 동작 방식과 특성에서 확실한 차이가 있습니다. 각 정렬의 핵심 개념, C언어 예제, 비교표, 그리고 시험 출제 포인트까지 완벽하게 정리해 드립니다!

1. 버블 정렬 (Bubble Sort) — 인접한 두 원소 비교

버블 정렬은 인접한 두 개의 원소를 비교하여 조건에 맞지 않으면 서로 자리를 바꾸며(Swap) 정렬하는 방식입니다.

• 동작 원리:
  • 첫 번째 원소부터 마지막 원소까지 순차적으로 바로 옆의 원소와 비교합니다.
  • 1회전을 수행하고 나면 가장 큰 데이터가 맨 뒤로 이동하여 고정됩니다. (물속에서 거품이 위로 올라오는 모습과 유사)
• 특징:
  • 구현이 매우 단순하지만, 자리를 바꾸는(Swap) 연산이 너무 자주 일어나 효율성이 가장 떨어집니다.

C

 

// C언어 버블 정렬 (오름차순)
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) { // 인접한 두 원소 비교
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 선택 정렬 (Selection Sort) — 최솟값 찾아서 교환

선택 정렬은 정렬되지 않은 전체 영역에서 가장 작은 값(최솟값)을 '선택'하여 맨 앞의 위치와 교환하는 방식입니다.

• 동작 원리:
  • 1회전에서 전체 원소 중 최솟값을 찾아 첫 번째 자리에 놓습니다.
  • 2회전에서는 첫 번째를 제외한 나머지 원소 중 최솟값을 찾아 두 번째 자리에 놓습니다.
• 특징:
  • 버블 정렬에 비해 데이터 교환(Swap) 횟수가 적습니다. ($1$회전에 최대 $1$번만 교환)
  • 이미 정렬된 상태이더라도 최소값을 찾기 위해 끝까지 비교를 수행합니다.

C

 

// C언어 선택 정렬 (오름차순)
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i; // 최솟값의 인덱스 저장
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        // 최솟값을 맨 앞(i번째)과 교환
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;
    }
}

3. 삽입 정렬 (Insertion Sort) — 알맞은 위치에 끼워 넣기

삽입 정렬은 두 번째 원소부터 시작하여, 자신의 앞쪽에 정렬된 원소들과 비교하여 적절한 위치를 찾아 '삽입'하는 방식입니다.

• 동작 원리:
  • 카드를 손에 쥐고 순서대로 정리하는 과정과 가장 유사합니다.
  • 정렬된 앞부분 영역을 보면서, 현재 대상 원소보다 큰 값들은 뒤로 한 칸씩 밀어내고 알맞은 위치에 쏙 끼워 넣습니다.
• 특징:
  • 이미 거의 정렬되어 있는 배열에서는 최선의 시간 복잡도인 $O(N)$으로 동작하여 기초 정렬 알고리즘 중 가장 빠르고 효율적입니다.

C

 

// C언어 삽입 정렬 (오름차순)
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 알맞은 위치를 찾을 원소
        int j = i - 1;
        // key보다 큰 원소들을 오른쪽으로 한 칸씩 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 적절한 위치에 삽입
    }
}

4. 한눈에 비교하는 핵심 요약 (시험 대비 필수)

시험 문제나 손코딩 면접에서 반드시 나오는 시간 복잡도 및 정렬 안정성 비교표입니다!

구분	버블 정렬 (Bubble)	선택 정렬 (Selection)	삽입 정렬 (Insertion)
핵심 아이디어	인접한 두 원소 비교 및 Swap	최솟값을 찾아 맨 앞과 Swap	알맞은 위치를 찾아 끼워 넣기
최선 시간복잡도	$O(N^2)$ (개선시 $O(N)$)	$O(N^2)$	$O(N)$ (이미 정렬된 경우)
평균 시간복잡도	$O(N^2)$	$O(N^2)$	$O(N^2)$
최악 시간복잡도	$O(N^2)$	$O(N^2)$	$O(N^2)$
정렬 안정성 (Stable)	안정 (Stable)	불안정 (Unstable)	안정 (Stable)

💡 안정 정렬(Stable Sort)이란?

값이 같은 원소들의 입력 전 상대적 순서가 정렬 후에도 그대로 유지되는 정렬을 말합니다. (예: 버블, 삽입)

5. 시험 단골 출제 문제 유형

1. Q. 초기 데이터가 '이미 거의 정렬된 상태'일 때 가장 뛰어난 성능을 보이는 알고리즘은?
2. 👉 삽입 정렬(Insertion Sort)입니다. (시간 복잡도 $O(N)$)
3. Q. 선택 정렬에서 1회전이 수행되고 난 후 확정되는 데이터의 위치와 의미는?
4. 👉 전체 데이터 중 가장 작은 최솟값(Min)이 맨 첫 번째 인덱스(Index 0)에 확정됩니다.
5. Q. 인접한 두 원소를 비교하여 거품이 올라오듯 정렬되는 알고리즘은?
6. 👉 버블 정렬(Bubble Sort)입니다.