함께 배우는 수업 · 컴퓨터/정보

핵심 정렬 알고리즘 비교

기초 정렬(버블, 선택, 삽입: O(N²))과 분할 정복 기반 고급 정렬(병합, 퀵, 힙: O(N log N))의 동작 메커니즘, 공간 복잡도, 안정 정렬(Stable Sort) 여부를 비교합니다.

이 수업에서 해 볼 일

정렬 알고리즘의 작동 방식과 안정성을 구분한다

먼저 알면 좋은 것: 배열(Array)의 원소 교환(Swap)과 인덱스 조작 · Big-O 시간 복잡도 ($O(N^2)$ vs $O(N \log N)$) · 재귀 함수와 분할 정복(Divide and Conquer) 개념

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

정렬 과정을 읽을 때는 한 단계에서 확정되는 부분을 표시하자. 삽입 정렬은 앞의 정렬된 부분에 다음 원소를 끼우고, 선택 정렬은 남은 부분의 최솟값을 찾아 앞자리를 확정한다.[7,3,6]의 삽입 정렬에서 3까지 처리하면 [3,7,6]이다. 아직 보지 않은 6까지 모두 정렬된 것으로 쓰면 단계 추적을 건너뛴 것이다.안정성은 같은 키의 상대적 순서를 보존하는 성질이다. 보조 공간 사용 여부나 평균 시간 복잡도와 독립적으로 따져야 하며, 퀵 정렬은 피벗의 분할 균형이 성능에 중요하다.

1. 기초 $O(N^2)$ 정렬 알고리즘: 버블, 선택, 삽입 정렬

1. 버블 정렬 (Bubble Sort): - 인접한 두 원소(A[j], A[j+1])를 비교하여 앞의 값이 더 크면 자리를 교환(Swap)하는 과정을 반복합니다. 1회전이 끝날 때마다 가장 큰 원소가 거품처럼 맨 뒤로 확정됩니다. - 비교 횟수는 항상

\frac{N(N-1)}{2}

번으로 시간 복잡도는 최선·평균·최악 모두 $O(N^2)$ 이며, 자리 교환이 빈번해 실제로는 가장 느립니다. 2. 선택 정렬 (Selection Sort): - 아직 정렬되지 않은 구간에서 가장 작은 최솟값(Min)을 찾아 맨 앞자리의 원소와 단 한 번 교환합니다. - 교환(Swap) 횟수는 최대

N-1

번으로 적지만, 항상 최솟값을 찾기 위해 끝까지 비교해야 하므로 최선·평균·최악 모두 $O(N^2)$ 이며 불안정 정렬(Unstable)입니다. 3. 삽입 정렬 (Insertion Sort): - 손안의 카드를 정렬하듯, 두 번째 원소부터 시작해 앞쪽의 이미 정렬된 구간에서 자신이 들어갈 알맞은 위치를 찾아 끼워 넣습니다. - 평균·최악은

O(N^2)

이지만, 데이터가 이미 거의 정렬되어 있는 최선의 경우(Best Case) 앞 원소와 한 번씩만 비교하고 바로 넘어가므로 $O(N)$ 이라는 초고속 성능을 보입니다!기초 O(N²) 정렬 3총사 중 '삽입 정렬(Insertion Sort)'은 이미 정렬된 배열에서 O(N)에 동작하며 안정 정렬이기 때문에, 파이썬과 자바의 표준 정렬 알고리즘(TimSort) 내부에서도 소규모 구간(N ≤ 32) 정렬용으로 실제로 사용됩니다.

2. 고급 $O(N \log N)$ 정렬 알고리즘: 병합, 퀵, 힙 정렬

1. 병합 정렬 (Merge Sort): - 배열을 원소가 1개가 될 때까지 절반씩 분할(Divide)한 뒤, 두 부분 배열을 크기순으로 비교하며 합치는(Merge) 분할 정복 알고리즘입니다. - 데이터 상태와 무관하게 최선·평균·최악 항상 $O(N \log N)$ 을 보장하며 안정 정렬(Stable)이지만, 병합 과정에서 크기

N

만큼의 추가 임시 배열 메모리( $O(N)$ 공간 복잡도)가 필요합니다. 2. 퀵 정렬 (Quick Sort): - 기준값인 피벗(Pivot)을 하나 정해 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할(Partition)한 뒤 재귀적으로 정렬합니다. - 추가 배열을 쓰지 않는 제자리 정렬(In-place)이며 캐시 지역성이 뛰어나 평균 $O(N \log N)$ 중 실측 속도가 가장 빠릅니다. - 단, 이미 정렬된 배열에서 맨 앞이나 맨 끝을 피벗으로 잡으면 분할이

1 : N-1

로 쏠려 최악 시간 복잡도가 $O(N^2)$ 으로 떨어집니다 (실무에서는 중앙값 피벗이나 랜덤 피벗으로 방지). 3. 힙 정렬 (Heap Sort): - 최대 힙(Max Heap)을 구성한 뒤 루트(최댓값)를 꺼내 배열 뒤쪽부터 채우는 방식으로, 추가 메모리 없이(

O(1)

공간) 항상 $O(N \log N)$ 을 보장합니다.

예제로 살펴보기

초기 배열 [8, 3, 5, 2, 4]에 대해 (1) 선택 정렬의 1회전 완료 후 배열 상태와 (2) 첫 번째 원소 8을 피벗(Pivot)으로 삼아 퀵 정렬 분할(Partition)을 1회 수행했을 때 왼쪽 부분 배열과 오른쪽 부분 배열의 원소 구성을 구하시오.

1) 선택 정렬 1회전: - 전체 [8, 3, 5, 2, 4] 중 최솟값은 2(인덱스 3)입니다. - 맨 앞 원소인 8(인덱스 0)과 최솟값 2의 자리를 맞바꿉니다(Swap). - 1회전 완료 후 배열 상태: [2, 3, 5, 8, 4] 2) 퀵 정렬 1회 분할 (피벗 = 8): - 피벗 8보다 작은 원소는 3, 5, 2, 4이고, 피벗보다 큰 원소는 하나도 없습니다(0개). - 따라서 왼쪽 부분 배열에 [3, 5, 2, 4] 4개가 모두 몰리고 오른쪽 부분 배열은 [](빈 배열)가 되어 피벗 8은 맨 끝자리로 확정됩니다. - 이처럼 가장 큰 값이나 가장 작은 값을 피벗으로 선택하면 불균형 분할이 일어나 퀵 정렬이 O(N²)으로 느려집니다.

확인: 버블·선택·삽입 정렬은 평균 O(N²) 시간이 걸리지만, 삽입 정렬은 거의 정렬된 데이터에서 O(N)으로 매우 빠르다.

3. 안정 정렬(Stable Sort)의 중요성과 종합 비교표

- 안정 정렬 (Stable Sort) vs 불안정 정렬 (Unstable Sort): - 안정 정렬: 정렬 기준 키값이 같은 원소들이 있을 때, 정렬 전의 원래 상대적 순서가 정렬 후에도 그대로 유지되는 정렬입니다 (예: 엑셀에서 '이름순'으로 먼저 정렬한 뒤 '부서별'로 다시 정렬할 때, 같은 부서 안에서 이름순이 깨지지 않으려면 반드시 안정 정렬이어야 합니다!). - 안정 정렬 종류: 버블 정렬, 삽입 정렬, 병합 정렬, TimSort (Python sort(), Java Arrays.sort(Object[])). - 불안정 정렬 종류: 선택 정렬, 퀵 정렬, 힙 정렬 (멀리 떨어진 원소와 점프하며 Swap하기 때문에 기존 순서가 깨짐).

알고리즘	최선 (Best)	평균 (Average)	최악 (Worst)	공간 복잡도	안정성 (Stable)
버블 정렬	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	안정 (Stable)
선택 정렬	$O(N^2)$	$O(N^2)$	$O(N^2)$	$O(1)$	불안정
삽입 정렬	$O(N)$	$O(N^2)$	$O(N^2)$	$O(1)$	안정 (Stable)
병합 정렬	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(N)$	안정 (Stable)
퀵 정렬	$O(N \log N)$	$O(N \log N)$	$O(N^2)$	$O(\log N)$	불안정
힙 정렬	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(1)$	불안정

비교 기반 정렬의 이론적 하한선 O(N log N)을 깨는 특수 정렬: 데이터의 범위(K)가 작은 정수일 때는 원소끼리 비교하지 않고 개수를 세는 계수 정렬(Counting Sort, O(N+K))이나 자릿수별로 분류하는 기수 정렬(Radix Sort, O(dN))을 사용하여 선형 시간 O(N)에 정렬할 수 있습니다.

참고 근거와 확인 범위

Harvard CS50 · Lecture 3: Algorithms ↗
선택·버블·병합 정렬의 과정과 시간 복잡도

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →