12. 정렬(1) - 개념, 버블정렬, 삽입정렬, 퀵정렬, 병합 정렬

 

💡 TL;DR — 이 글의 핵심 요약

· 정렬(Sorting) : 순서 없는 데이터를 오름차순·내림차순으로 재배열하는 것
· 버블 정렬 : 인접한 두 원소를 비교해 교환 — 구현 쉬우나 느림
· 삽입 정렬 : 카드 정렬처럼 정렬된 영역에 하나씩 끼워 넣는 방식
· 퀵 정렬 : 피벗(pivot)을 기준으로 분할 정복 — 평균적으로 매우 빠름
· 병합 정렬 : 리스트를 반으로 나누고 정렬 후 합치는 분할 정복 방식

 

 

 

01 정렬(Sorting)이란?

 

📘 정렬(Sorting) 정의
순서가 없는 데이터(레코드)들을 특정 기준(키, key)에 따라 순서대로 재배열하는 것.
오름차순(ascending)과 내림차순(descending) 두 가지 방향이 있으며,
숫자·문자·날짜 등 비교 가능한 것이면 무엇이든 정렬 기준이 될 수 있다.

 

▶ 정렬이 필요한 이유

상황	정렬 기준 예시
도서관 책 정리	제목, 저자명, 발간 연도 순
인터넷 쇼핑몰	판매 인기순, 가격 낮은순, 신규상품순
성적 처리 (엑셀)	학번, 기말성적, 실습성적 순

 

▶ 레코드와 키(Key)

정렬 대상 데이터를 레코드(record)라 부르며, 레코드는 여러 필드(field)로 구성됩니다.
예: 학생 레코드 = {이름, 학번, 주소, 연락처}
이 중 레코드를 식별하고 정렬 기준이 되는 필드를 키(key)라고 합니다.

 

 

 

02 정렬 알고리즘의 분류

 

▶ ① 정렬 장소에 따른 분류

 

🖥 내부 정렬 (Internal Sorting) · 정렬할 모든 데이터가 메인 메모리(RAM)에 올라와 있는 상태에서 진행 · 데이터 수가 적을 때 적합 예: 버블, 삽입, 선택, 퀵, 힙, 병합, 기수 정렬

💾 외부 정렬 (External Sorting) · 데이터가 너무 커서 외부 기억 장치(HDD 등)에 저장된 채로 일부만 메모리에 올려 정렬 · 대용량 파일 처리에 사용 예: 대규모 로그 파일, DB 외부 정렬

 

▶ ② 효율성에 따른 분류

 

🐢 단순하지만 비효율적 · 삽입 정렬 (Insertion Sort) · 선택 정렬 (Selection Sort) · 버블 정렬 (Bubble Sort) 구현은 쉬우나 데이터 수가 많으면 느림

🚀 복잡하지만 효율적 · 퀵 정렬 (Quick Sort) · 힙 정렬 (Heap Sort) · 병합 정렬 (Merge Sort) · 기수 정렬 (Radix Sort) 구현이 까다롭지만 대용량 데이터에 유리

 

▶ ③ 안정성(Stability)에 따른 분류

 

✅ 안정성(Stability)이란?
동일한 키 값을 가진 레코드가 여러 개 있을 때, 정렬 후에도 원래의 상대적 순서가 유지되는 성질.

· 안정 정렬 : 삽입 정렬, 버블 정렬, 병합 정렬
· 불안정 정렬 : 퀵 정렬, 선택 정렬, 힙 정렬

 

▶ 정렬 방식별 분류 한눈에 보기

 

방식	해당 정렬
삽입법	삽입 정렬, 쉘 정렬
교환법	버블 정렬, 선택 정렬, 퀵 정렬
병합법	병합 정렬
선택법	힙 정렬 (이진 트리 활용)
분배법	기수 정렬

 

 

 

03 버블 정렬 (Bubble Sort)

 

📘 버블 정렬 개념
인접한 두 원소를 비교하여 순서가 맞지 않으면 서로 교환(swap)하는 방식.
한 번의 패스(pass)가 끝나면 가장 큰 값이 리스트의 맨 오른쪽으로 이동하며,
마치 물속의 거품(bubble)이 떠오르는 모습과 유사해 버블 정렬이라 부른다.

 

▶ 동작 원리

 

① 비교 인접한 두 원소 비교

→

② 교환 순서 안 맞으면 swap

→

③ 반복 끝까지 반복 후 최대값 오른쪽 확정

 

▶ C언어 구현 예시

 

bubble_sort.c — 버블 정렬

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {  // 인접 원소 비교
                temp = arr[j];
                arr[j] = arr[j + 1];   // 교환(swap)
                arr[j + 1] = temp;
            }
        }
    }
}

 

⚠️ 버블 정렬 특징 정리
· 시간 복잡도: 최선/평균/최악 모두 O(n²)
· 안정 정렬(Stable Sort) — 동일 키 값의 순서 유지
· 구현이 매우 간단하지만 데이터가 많을수록 비효율적
· 이미 정렬된 경우 최적화 시 O(n) 가능 (swap 발생 여부 체크)

 

 

04 삽입 정렬 (Insertion Sort)

 

📘 삽입 정렬 개념
카드 게임에서 손에 쥔 카드를 정렬하는 방법과 유사.
이미 정렬된 부분을 왼쪽에 유지하면서, 정렬 안 된 새 원소를 적절한 위치에 끼워 넣는(삽입) 방식.
A[0]을 정렬된 원소로 가정하고, A[1]부터 차례로 삽입 위치를 찾아간다.

 

▶ 동작 원리

 

① 시작 A[0]을 정렬 완료 구간으로 설정

→

② 선택 다음 원소를 꺼냄

→

③ 삽입 정렬 구간에서 맞는 자리 찾아 삽입

→

④ 반복 정렬 안된 원소가 없을 때까지

 

▶ C언어 구현 예시

 

insertion_sort.c — 삽입 정렬

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];   // 삽입할 원소 저장
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j]; // 원소를 오른쪽으로 이동
            j--;
        }
        arr[j + 1] = key;    // 올바른 위치에 삽입
    }
}

 

✅ 삽입 정렬이 효율적인 경우
· 데이터 수가 적을 때 — 알고리즘이 단순해 오버헤드가 없음
· 대부분 정렬되어 있는 경우 — 비교만 하고 이동이 거의 없어 빠름 (거의 O(n))
· 이미 정렬된 경우 비교만 수행하여 처리 속도 우수

 

❌ 삽입 정렬의 단점
· 입력 데이터 상태에 매우 민감 — 원하는 방향과 반대로 정렬된 경우 최악 O(n²)
· 데이터가 많고 역순에 가까울수록 매우 느림

 

 

 

05 퀵 정렬 (Quick Sort)

 

📘 퀵 정렬 개념
리스트에서 하나의 원소를 피벗(pivot)으로 선택하고,
피벗보다 작은 원소 → 왼쪽, 큰 원소 → 오른쪽으로 분할한 뒤,
각 부분을 재귀적으로 다시 퀵 정렬하는 분할 정복(Divide & Conquer) 방식.

 

▶ 동작 원리

 

① 피벗 선택 리스트에서 임의의 원소 하나를 피벗으로 선택

→

② 분할 피벗 기준으로 작은 것 왼쪽, 큰 것 오른쪽으로 이동

→

③ 재귀 정렬 왼쪽·오른쪽 부분을 각각 다시 퀵 정렬 (순환 호출)

 

 

▶ C언어 구현 예시

 

quick_sort.c — 퀵 정렬

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 마지막 원소를 피벗으로 선택
    int i = low - 1, temp;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
        }
    }
    temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp;
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);  // 왼쪽 재귀
        quickSort(arr, pi + 1, high); // 오른쪽 재귀
    }
}

 

✅ 퀵 정렬 특징
· 평균 시간 복잡도 O(n log n) — 실제로 매우 빠른 정렬
· 병합 정렬과 달리 균등하게 분할할 필요 없음
· 추가 메모리 없이 제자리(in-place) 정렬 가능
· 피벗 선택이 나쁘면 최악 O(n²) 발생 (이미 정렬된 경우)

 

❌ 퀵 정렬 최악의 경우 O(n²)가 되는 이유
선택한 피벗이 매번 배열의 최솟값이나 최댓값으로 치우치는 경우 분할의 이점이 사라집니다.
예: 이미 오름차순으로 정렬된 배열에서 맨 뒤 원소를 피벗으로 잡으면, 매 단계마다 한쪽 부분 배열에 원소가 0개, 반대쪽에 n-1개가 몰려 분할이 전혀 이루어지지 않습니다.

🔑 해결책 — Median-of-Three 기법
배열에서 임의의 세 값(첫째, 중간, 마지막)을 뽑아 중간값(median)을 피벗으로 선택하면 최악의 분할을 효과적으로 방지할 수 있습니다. 실무용 퀵 정렬 라이브러리(C의 qsort 등)는 대부분 이 기법을 변형해서 사용합니다.

 

 

 

06 병합 정렬 (Merge Sort)

 

📘 병합 정렬 개념
리스트를 두 개의 균등한 크기로 분할하고, 각각을 정렬한 뒤 다시 합쳐 전체를 정렬하는 방법.
분할 정복(Divide & Conquer)에 기반하며, 원소가 하나가 될 때까지 반복적으로 나눈 후
정렬하며 합쳐간다.

 

▶ 분할 정복 3단계

 

① 분할 (Divide) 입력 배열을 같은 크기의 2개 부분 배열로 분할 (원소 1개가 될 때까지)

→

② 정복 (Conquer) 각 부분 배열을 정렬 (충분히 작지 않으면 재귀 호출)

→

③ 결합 (Combine) 정렬된 부분 배열들을 하나의 배열에 통합

 

 

 

▶ C언어 구현 예시

 

merge_sort.c — 병합 정렬

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int L[n1], R[n2], i, j, k;
    for (i = 0; i < n1; i++) L[i] = arr[l + i];
    for (j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    i = 0; j = 0; k = l;
    while (i < n1 && j < n2) {  // 두 배열 병합
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);   // 왼쪽 분할 후 정렬
        mergeSort(arr, m+1, r); // 오른쪽 분할 후 정렬
        merge(arr, l, m, r);    // 병합
    }
}

 

⚠️ VLA(가변 길이 배열) 사용 주의
위 코드의 int L[n1], R[n2]; 는 C99 표준의 가변 길이 배열(VLA) 문법입니다. 문법상 오류는 아니지만 두 가지 실질적 위험이 있습니다.

· 컴파일러 호환성 : 구버전 MSVC(Visual Studio) 컴파일러에서는 컴파일 에러가 발생합니다.
· 스택 오버플로우 : 정렬할 데이터 수(n)가 커질수록 스택 메모리가 고갈되어 프로그램이 크래시될 수 있습니다.

🔑 실무 권장 방식 : 힙(Heap) 영역에 동적 할당(malloc)을 사용하거나, mergeSort 최초 호출 시 크기 n의 전역 임시 버퍼를 생성해 매개변수로 넘겨주는 방식이 더 안전합니다.

 

✅ 병합 정렬 특징
· 시간 복잡도 항상 O(n log n) — 최선·평균·최악 모두 동일
· 안정 정렬(Stable Sort) — 동일 키 값 순서 유지
· 추가 메모리(임시 배열)가 필요 — 공간 복잡도 O(n)
· 퀵 정렬보다 안정적이나 메모리 오버헤드 있음

 

 

 

07 정렬 알고리즘 한눈에 비교

 

정렬	평균 시간복잡도	최악 시간복잡도	공간복잡도	안정성	특징 요약
버블 정렬	O(n²)	O(n²)	O(1) 제자리 정렬	✅ 안정	구현 간단, 느림
삽입 정렬	O(n²)	O(n²)	O(1) 제자리 정렬	✅ 안정	거의 정렬된 경우 빠름
퀵 정렬	O(n log n)	O(n²)	O(log n) 재귀 스택 공간	❌ 불안정	실제로 가장 빠름, 제자리 정렬
병합 정렬	O(n log n)	O(n log n)	O(n) 임시 배열 필수	✅ 안정	안정적이나 추가 메모리 필요

 

 

 

📌 핵심 정리

· 정렬(Sorting) : 키(key) 기준으로 레코드를 오름차순·내림차순으로 재배열
· 내부 정렬 : 전체 데이터가 메모리에 올라와 있는 상태의 정렬
· 외부 정렬 : 외부 저장 장치를 활용해 대용량 데이터 정렬
· 버블 정렬 : 인접 원소 비교·교환, O(n²), 안정 정렬
· 삽입 정렬 : 정렬된 영역에 하나씩 삽입, O(n²), 안정 정렬, 거의 정렬된 경우 유리
· 퀵 정렬 : 피벗 기준 분할 정복, 평균 O(n log n), 불안정 정렬, 실용적으로 가장 빠름
· 병합 정렬 : 균등 분할 후 병합, 항상 O(n log n), 안정 정렬, 추가 메모리 필요

 

 

태그 : 정렬 알고리즘이란버블 정렬 개념삽입 정렬 원리퀵 정렬 피벗병합 정렬 분할 정복내부 정렬 외부 정렬 차이정렬 안정성이란C언어 정렬 구현자료구조 정렬 종류퀵정렬 병합정렬 비교