13. 정렬 (2) - 선택 정렬, 셀 정렬, 기수 정렬, 힙 정렬, 탐색

 

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

· 선택 정렬 : 전체에서 최솟값을 반복적으로 선택해 앞으로 이동하는 방식, n-1번 반복
· 셸 정렬 : 간격(gap)을 두고 부분 리스트를 만들어 삽입 정렬로 처리, 간격을 줄여가며 반복
· 기수 정렬 : 비교 연산 없이 자릿수(일의 자리 → 십의 자리 → …) 기준으로 버킷에 분배해 정렬
· 힙 정렬 : 완전 이진 트리 기반 반정렬 구조(힙)를 이용해 최대·최솟값을 빠르게 추출
· 탐색 : 순차 탐색(처음부터 비교) vs 이진 탐색(정렬된 배열에서 범위를 절반씩 좁힘)

 

 

 

📌 정렬 알고리즘 전체 지도

 

버블 정렬	삽입 정렬	퀵 정렬	병합 정렬
선택 정렬 ★	셸 정렬 ★	기수 정렬 ★	힙 정렬 ★

★ 이번 포스팅에서 다루는 정렬

 

 

 

SECTION 01

선택 정렬 (Selection Sort)

 

💡 핵심 개념
정렬되지 않은 부분(오른쪽)에서 최솟값을 선택해 정렬된 부분(왼쪽) 끝으로 이동하는 방식.
전체 요소 개수가 n이면 n-1번 반복하면 정렬 완료.

 

▶ 동작 원리 단계별 예시

 

정렬된 부분 (왼쪽)	정렬 안 된 부분 (오른쪽)	설명
( )	(5, 3, 8, 1, 2, 7)	초기 상태
(1)	(5, 3, 8, 2, 7)	1 선택 → 5와 교환
(1, 2)	(5, 3, 8, 7)	2 선택
(1, 2, 3)	(5, 8, 7)	3 선택
(1, 2, 3, 5)	(8, 7)	5 선택
(1, 2, 3, 5, 7)	(8)	7 선택
(1, 2, 3, 5, 7, 8)	( )	✅ 정렬 완료

 

 

▶ C언어 구현

 

selection_sort.c — 선택 정렬

void selectionSort(int a[], int n) {
    int i, j, min, tmp;
    for (i = 0; i < n - 1; i++) {
        min = i;
        for (j = i + 1; j < n; j++)
            if (a[j] < a[min]) min = j; // 최솟값 인덱스 탐색
        tmp = a[i]; a[i] = a[min]; a[min] = tmp; // 교환
    }
}

 

 

 

SECTION 02

셸 정렬 (Shell Sort)

 

💡 핵심 개념
도널드 셸(Donald L. Shell)이 고안. 일정 간격(gap)으로 떨어진 원소들끼리 부분 리스트를 구성하고,
각 부분 리스트에 삽입 정렬 적용. 간격을 점점 줄여 마지막 간격 = 1이 되면 완료.

 

▶ 삽입 정렬과의 차이점

 

삽입 정렬	셸 정렬
인접한 원소끼리 비교 → 한 번에 한 칸씩만 이동	간격(gap)만큼 떨어진 원소끼리 비교 → 한 번에 큰 거리를 이동 가능
거의 정렬된 경우에는 빠름	마지막 단계가 거의 정렬 상태 → 삽입 정렬이 매우 빠르게 완료

 

 

▶ 셸 정렬 진행 흐름

 

① 큰 간격 gap = n/2 부분 리스트 수 多

→

② 간격 축소 gap = gap/2 부분 리스트 수 감소

→

③ 반복 간격이 줄어들며 부분 리스트 크기 증가

→

④ gap = 1 전체 리스트 삽입 정렬 → 완료

 

⚠️ 왜 효율적인가?
연속적이지 않은 부분 리스트에서 교환이 일어나면 원소가 최종 위치에 훨씬 가까이 이동하게 됩니다.
마지막 단계(gap=1)에서 삽입 정렬을 수행할 때는 이미 거의 정렬된 상태이므로 매우 빠르게 완료됩니다.

 

 

 

SECTION 03

기수 정렬 (Radix Sort)

 

💡 핵심 개념
다른 정렬과 달리 원소 간 비교 연산이 전혀 없는 색다른 정렬 기법.
숫자의 자릿수(기수, radix) 값에 따라 버킷(bucket)에 분배했다가 순서대로 꺼내는 과정을 반복.

 

▶ 기수 정렬 핵심 구조

 

용어	설명
기수 (Radix)	숫자의 자릿수. 10진수라면 기수 = 10 → 버킷을 0~9, 총 10개 사용
버킷 (Bucket)	자릿수 값에 해당하는 임시 저장 공간 → 원소를 분배했다가 순서대로 꺼냄
단계 수	데이터의 최대 자릿수 개수와 동일 예: 세 자리 수 → 3단계 (일 → 십 → 백)

 

▶ 정렬 진행 순서

 

1단계 일의 자리 기준 버킷 분배 → 수집

→

2단계 십의 자리 기준 버킷 분배 → 수집

→

3단계 (마지막) 백의 자리 기준 버킷 분배 → 수집 → 완료

 

 

✅ 기수 정렬의 장점
비교 연산이 없으므로 이론상 O(d·n) (d = 자릿수, n = 원소 수) 으로 매우 빠를 수 있습니다.
단, 버킷 메모리가 추가로 필요하며, 정수·문자열처럼 자릿수가 명확한 데이터에 적합합니다.

 

🚫 기수 정렬을 사용할 수 없는 경우 (시험 단골 함정!)
· 음수가 포함된 정수 배열 : 음수는 버킷 인덱스로 쓸 수 없어 일반적인 기수 정렬 직접 적용 불가
· 부동 소수점(실수, float/double) : 자릿수 경계가 불명확해 버킷 분배 기준을 정할 수 없음
※ 음수나 실수 데이터는 특수한 변환(오프셋 적용, 비트 표현 변환 등) 없이는 기수 정렬 적용이 불가합니다.

 

 

 

SECTION 04

힙 정렬 (Heap Sort)

 

💡 힙(Heap)이란?
완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조.
요소들이 완전히 정렬되지는 않지만 전혀 정렬되지 않은 것도 아닌 반(半)정렬 상태를 유지.
여러 값 중 가장 크거나 작은 값을 O(log n)에 빠르게 찾아낼 수 있는 것이 핵심.

 

▶ 최대 힙 vs 최소 힙

 

종류	조건	특징
최대 힙 (Max Heap)	key(부모) ≥ key(자식)	루트 = 전체 최댓값 오름차순 정렬에 활용
최소 힙 (Min Heap)	key(부모) ≤ key(자식)	루트 = 전체 최솟값 내림차순 정렬에 활용

 

⚠️ 힙은 완전 정렬이 아니다!
힙은 부모가 자식보다 크다(최대힙)는 느슨한 조건만 만족합니다.
같은 레벨의 형제 노드끼리는 크기 관계를 보장하지 않으며, 이것이 힙과 정렬된 배열의 차이입니다.
삭제 연산에서 최댓값/최솟값만 빠르게 꺼내면 되므로 전체 정렬이 불필요합니다.

 

▶ 힙 정렬의 2단계 작동 방식 (Heapify)

 

① Heapify (힙 생성) 정렬되지 않은 n개의 원소를 최대 힙 구조로 재구성

→

② 루트 추출 반복 루트(최댓값)를 맨 끝 원소와 교환 → 힙 크기를 1 줄이고 다시 Heapify → 반복하면 오름차순 정렬 완료

 

⏱ 시간 복잡도
힙 정렬은 최악·평균·최선 모든 경우에서 O(n log n) 을 보장합니다.
퀵 정렬이 최악의 경우 O(n²)로 떨어지는 것과 달리, 힙 정렬은 입력 데이터 순서에 관계없이 안정적인 성능을 냅니다.

 

 

 

SECTION 05

탐색 (Search) — 순차 탐색 vs 이진 탐색

 

💡 탐색이란?
주어진 테이블(레코드 집합)에서 원하는 탐색키(search key)를 가진 레코드를 찾는 작업.
컴퓨터에서 정렬과 함께 가장 중요한 응용 분야.

 

▶ 순차 탐색 vs 이진 탐색 비교

 

구분	순차 탐색 (Sequential Search)	이진 탐색 (Binary Search)
전제 조건	정렬 불필요	반드시 정렬된 배열
탐색 방식	처음부터 끝까지 하나씩 비교	중앙값과 비교 후 탐색 범위를 절반씩 축소
시간 복잡도	O(n)	O(log n)
장점	간단하고 직접적 어떤 배열에도 적용 가능	대용량 데이터에서 매우 빠름
단점	비효율적 (전체 탐색)	사전에 정렬이 필요

 

▶ 이진 탐색 동작 원리

 

① 정렬된 배열의 중앙 원소를 선택
② 찾는 값과 중앙값 비교
   · 찾는 값 = 중앙값 → 탐색 성공!
   · 찾는 값 < 중앙값 → 왼쪽 절반에서 재탐색
   · 찾는 값 > 중앙값 → 오른쪽 절반에서 재탐색
③ 탐색 범위가 0이 될 때까지 ①~② 반복

 

 

binary_search.c — 이진 탐색

int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2; // 중앙 인덱스
        if (key == a[mid]) return mid; // 탐색 성공
        else if (key < a[mid]) high = mid - 1; // 왼쪽 탐색
        else low = mid + 1; // 오른쪽 탐색
    }
    return -1; // 탐색 실패
}

 

 

 

📌 핵심 정리

· 선택 정렬 : 미정렬 부분에서 최솟값을 선택해 앞으로 이동. n-1번 반복으로 완료
· 셸 정렬 : 간격(gap)을 두고 부분 리스트를 삽입 정렬. gap을 줄여가며 반복 → 거의 정렬된 상태에서 최종 삽입 정렬
· 기수 정렬 : 비교 연산 없이 자릿수별 버킷 분배·수집 반복. 단계 수 = 자릿수 개수
· 힙 정렬 : 완전 이진 트리 기반 반정렬 구조. 최대힙은 부모 ≥ 자식, 최소힙은 부모 ≤ 자식. Heapify → 루트 추출 반복. 시간복잡도 O(n log n) (최악·평균·최선 모두)
· 순차 탐색 : 처음부터 끝까지 순서대로 비교. 정렬 불필요. O(n)
· 이진 탐색 : 정렬된 배열에서 중앙값 기준으로 범위 절반씩 축소. O(log n)

 

 

태그 : 선택정렬이란 셸정렬이란 기수정렬이란 힙정렬이란 자료구조 정렬 종류 순차탐색 이진탐색 차이 이진탐색 알고리즘 C언어 힙 최대힙 최소힙 차이 선택정렬 C언어 구현 자료구조 14강 정리