정렬(Sort)은 데이터를 정해진 기준에 따라 오름차순이나 내림차순으로 재배치하는 과정입니다. 정렬된 데이터는 검색·병합·통계 처리와 같은 후속 작업을 더 효율적으로 수행할 수 있게 해 줍니다.
이 장에서는 정렬 알고리즘을 선택할 때 고려할 요소와 내부 정렬의 대표 방식인 삽입·버블·선택·병합·퀵·힙 정렬을 정리합니다. 각 알고리즘의 처리 원리, 시간 복잡도, 안정성, 추가 메모리 사용 여부와 시험에서 자주 묻는 회전별 배열 변화를 함께 살펴봅니다.
이 장의 핵심 내용
- 정렬 알고리즘은 데이터의 양·초기 배열 상태·키 분포·메모리 환경을 고려해 선택합니다.
- 삽입 정렬은 앞쪽의 정렬된 영역에 새 값을 알맞은 위치로 삽입합니다.
- 버블 정렬은 인접한 두 값을 비교·교환하며 큰 값을 배열 뒤쪽으로 이동시킵니다.
- 선택 정렬은 남은 영역에서 최솟값을 찾아 현재 위치와 교환합니다.
- 병합 정렬은 데이터를 나눈 뒤 정렬된 부분 배열을 차례로 합칩니다.
- 퀵 정렬은 피벗을 기준으로 작은 값과 큰 값을 분할해 정렬합니다.
- 힙 정렬은 완전 이진 트리 형태의 힙을 이용해 최댓값 또는 최솟값을 반복적으로 꺼냅니다.
- 병합·힙 정렬은 최악의 경우에도 O(n log n), 퀵 정렬은 평균 O(n log n)이지만 최악은 O(n²)입니다.
정렬이란 무엇인가?
정렬은 데이터 레코드를 특정 키(Key)의 값을 기준으로 일정한 순서에 맞게 재배치하는 작업입니다. 숫자의 크기, 문자 순서, 날짜, 우선순위 등 다양한 값을 정렬 기준으로 사용할 수 있습니다.
| 구분 | 의미 | 예시 |
|---|---|---|
| 오름차순 | 작은 값에서 큰 값 순서로 배치 | 2, 5, 6, 7, 8, 9 |
| 내림차순 | 큰 값에서 작은 값 순서로 배치 | 9, 8, 7, 6, 5, 2 |
| 정렬 키 | 데이터의 순서를 결정하는 기준값 | 학번, 이름, 점수, 날짜 |
정렬 알고리즘은 무엇을 기준으로 선택할까?
모든 상황에서 가장 우수한 정렬 알고리즘이 하나로 정해지는 것은 아닙니다. 데이터와 시스템의 특성에 따라 비교 횟수, 이동 횟수, 메모리 사용량과 최악의 수행 시간을 함께 고려해야 합니다.
| 고려 요소 | 확인할 내용 |
|---|---|
| 데이터의 양 | 정렬할 레코드 수가 적은지, 매우 많은지 확인 |
| 초기 배열 상태 | 이미 상당 부분 정렬되어 있는지, 역순에 가까운지 확인 |
| 키의 분포 | 중복 키가 많은지, 값의 범위가 좁거나 넓은지 확인 |
| 비교와 이동 비용 | 키 비교와 레코드 이동 중 어느 작업의 비용이 큰지 확인 |
| 메모리 환경 | 추가 배열이나 보조 저장공간을 사용할 수 있는지 확인 |
| 안정성 필요 여부 | 같은 키를 가진 레코드의 기존 순서를 유지해야 하는지 확인 |
내부 정렬과 외부 정렬은 어떻게 다를까?
| 구분 | 의미 | 대표 상황 |
|---|---|---|
| 내부 정렬 | 정렬할 데이터를 주기억장치에 모두 올려 처리 | 메모리에 들어가는 배열이나 리스트 |
| 외부 정렬 | 데이터가 너무 커서 보조기억장치와 주기억장치를 함께 사용 | 대용량 파일과 데이터베이스 정렬 |
삽입 정렬은 어떻게 동작할까?
삽입 정렬(Insertion Sort)은 배열의 앞쪽을 정렬된 영역으로 보고, 뒤쪽에서 새로운 값을 하나씩 꺼내 정렬된 영역의 알맞은 위치에 삽입하는 방식입니다.
현재 삽입할 값을 키(Key)로 정한 뒤, 키보다 큰 앞쪽 원소를 한 칸씩 뒤로 이동시키고 비어 있는 위치에 키를 삽입합니다. 이미 상당 부분 정렬된 데이터에서는 이동 횟수가 적어 효율적입니다.
| 항목 | 내용 |
|---|---|
| 핵심 원리 | 정렬된 앞쪽 영역에 새 값을 삽입 |
| 최선 시간 복잡도 | O(n) |
| 평균·최악 시간 복잡도 | O(n²) |
| 안정 정렬 | 예 |
| 제자리 정렬 | 예 |
삽입 정렬의 회전별 변화
초기 배열이 6, 5, 7, 2, 8, 9일 때 오름차순 삽입 정렬을 적용합니다.
| 회전 | 키 | 배열 상태 |
|---|---|---|
| 초기 상태 | — | 6, 5, 7, 2, 8, 9 |
| 1회전 | 5 | 5, 6, 7, 2, 8, 9 |
| 2회전 | 7 | 5, 6, 7, 2, 8, 9 |
| 3회전 | 2 | 2, 5, 6, 7, 8, 9 |
| 4회전 | 8 | 2, 5, 6, 7, 8, 9 |
| 5회전 | 9 | 2, 5, 6, 7, 8, 9 |
시험 예시: 초기 자료 8, 3, 4, 9, 7에서 삽입 정렬 1회전 후 배열은 3, 8, 4, 9, 7입니다.
버블 정렬은 어떻게 동작할까?
버블 정렬(Bubble Sort)은 서로 인접한 두 원소를 비교하여 순서가 잘못되어 있으면 교환하는 과정을 반복합니다. 오름차순 정렬에서는 한 회전이 끝날 때마다 아직 정렬되지 않은 영역의 가장 큰 값이 뒤쪽으로 이동합니다.
| 항목 | 내용 |
|---|---|
| 핵심 원리 | 인접 원소를 비교·교환 |
| 최선 시간 복잡도 | 기본 구현 O(n²), 교환 여부를 검사하는 최적화 구현 O(n) |
| 평균·최악 시간 복잡도 | O(n²) |
| 안정 정렬 | 예 |
| 제자리 정렬 | 예 |
복잡도 주의: 교환이 한 번도 발생하지 않으면 즉시 종료하는 최적화가 있어야 최선 시간이 O(n)이 됩니다. 고정된 횟수만큼 끝까지 비교하는 기본 구현의 최선 시간은 O(n²)입니다.
버블 정렬 1회전의 의미
초기 배열 6, 5, 7, 2, 8, 9를 오름차순으로 정렬하면 첫 회전에서 인접한 값을 왼쪽부터 비교합니다.
| 비교 | 처리 결과 |
|---|---|
| 6과 5 | 교환 → 5, 6, 7, 2, 8, 9 |
| 6과 7 | 유지 → 5, 6, 7, 2, 8, 9 |
| 7과 2 | 교환 → 5, 6, 2, 7, 8, 9 |
| 7과 8 | 유지 → 5, 6, 2, 7, 8, 9 |
| 8과 9 | 유지 → 5, 6, 2, 7, 8, 9 |
선택 정렬은 어떻게 동작할까?
선택 정렬(Selection Sort)은 아직 정렬되지 않은 영역에서 최솟값을 찾고, 그 값을 현재 영역의 첫 번째 원소와 교환하는 과정을 반복합니다. 오름차순 정렬에서는 매 회전마다 가장 작은 값의 위치가 앞에서부터 하나씩 확정됩니다.
| 항목 | 내용 |
|---|---|
| 핵심 원리 | 남은 영역의 최솟값을 선택하여 앞으로 이동 |
| 최선·평균·최악 시간 복잡도 | O(n²) |
| 안정 정렬 | 일반적으로 아니오 |
| 제자리 정렬 | 예 |
| 특징 | 비교 횟수는 많지만 교환 횟수는 비교적 적음 |
선택 정렬의 회전별 변화
초기 배열이 6, 5, 7, 2, 8, 9일 때 오름차순 선택 정렬을 적용합니다.
| 회전 | 선택한 값 | 배열 상태 |
|---|---|---|
| 초기 상태 | — | 6, 5, 7, 2, 8, 9 |
| 1회전 | 2 | 2, 5, 7, 6, 8, 9 |
| 2회전 | 5 | 2, 5, 7, 6, 8, 9 |
| 3회전 | 6 | 2, 5, 6, 7, 8, 9 |
시험 예시: 초기 자료 37, 14, 17, 40, 35에서 선택 정렬 3회전 후 배열은 14, 17, 35, 40, 37입니다.
병합 정렬은 어떻게 동작할까?
병합 정렬(Merge Sort)은 데이터를 작은 부분 배열로 반복해서 나눈 뒤, 정렬된 부분 배열을 순서에 맞게 합치는 분할 정복 방식입니다. 2-Way 병합 정렬은 두 개의 정렬된 부분 배열을 하나의 정렬된 배열로 합치는 과정을 반복합니다.
| 항목 | 내용 |
|---|---|
| 핵심 원리 | 분할한 뒤 정렬된 부분 배열을 병합 |
| 최선·평균·최악 시간 복잡도 | O(n log n) |
| 안정 정렬 | 예 |
| 추가 공간 | 배열 구현에서는 일반적으로 O(n) |
| 대표 활용 | 대용량 파일과 외부 정렬 |
퀵 정렬은 어떻게 동작할까?
퀵 정렬(Quick Sort)은 하나의 값을 피벗(Pivot)으로 정하고, 피벗보다 작은 값과 큰 값을 서로 다른 영역으로 분할한 뒤 각 영역에 같은 과정을 반복하는 분할 정복 정렬입니다.
피벗이 배열을 비교적 균등하게 나누면 효율적이지만, 매번 최솟값이나 최댓값이 피벗이 되어 한쪽 영역만 커지면 수행 시간이 크게 증가할 수 있습니다.
| 항목 | 내용 |
|---|---|
| 핵심 원리 | 피벗을 기준으로 작은 값과 큰 값을 분할 |
| 최선·평균 시간 복잡도 | O(n log n) |
| 최악 시간 복잡도 | O(n²) |
| 안정 정렬 | 일반적으로 아니오 |
| 특징 | 평균적으로 빠르고 캐시 효율이 좋음 |
퀵 정렬의 최악 비교 횟수
피벗이 매번 가장 작은 값이나 가장 큰 값으로 선택되어 한쪽에만 원소가 남으면 비교 횟수는 다음과 같이 증가합니다.
힙 정렬은 어떻게 동작할까?
힙 정렬(Heap Sort)은 완전 이진 트리 형태의 힙을 이용하는 정렬 방식입니다. 오름차순 정렬에서는 일반적으로 최대 힙을 구성한 뒤 루트의 최댓값을 배열 뒤쪽으로 이동하고, 남은 영역에서 힙을 다시 구성하는 과정을 반복합니다.
| 항목 | 내용 |
|---|---|
| 핵심 원리 | 힙의 루트 값을 반복해서 꺼내 정렬 위치에 배치 |
| 최선·평균·최악 시간 복잡도 | O(n log n) |
| 안정 정렬 | 아니오 |
| 제자리 정렬 | 예 |
| 특징 | 최악의 경우에도 O(n log n)을 보장 |
정렬 알고리즘을 한눈에 비교하면?
| 알고리즘 | 최선 | 평균 | 최악 | 안정성 | 핵심 특징 |
|---|---|---|---|---|---|
| 삽입 정렬 | O(n) | O(n²) | O(n²) | 안정 | 정렬된 데이터에 유리 |
| 버블 정렬 | O(n) 또는 O(n²) | O(n²) | O(n²) | 안정 | 인접 원소 교환 |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | 불안정 | 교환 횟수가 적음 |
| 병합 정렬 | O(n log n) | O(n log n) | O(n log n) | 안정 | 추가 배열 필요 |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) | 불안정 | 피벗 선택의 영향이 큼 |
| 힙 정렬 | O(n log n) | O(n log n) | O(n log n) | 불안정 | 최악 시간 보장 |
시험에서 자주 혼동되는 개념
삽입 정렬과 선택 정렬
삽입 정렬은 현재 값을 정렬된 앞쪽 영역에 끼워 넣고, 선택 정렬은 남은 영역의 최솟값을 찾아 현재 위치와 교환합니다.
버블 정렬과 선택 정렬
버블 정렬은 인접 원소를 계속 교환하고, 선택 정렬은 한 회전에서 최솟값을 한 번 선택해 앞쪽에 배치합니다.
병합 정렬과 퀵 정렬
둘 다 분할 정복 방식이지만 병합 정렬은 나눈 뒤 합치는 과정이 핵심이고, 퀵 정렬은 피벗을 기준으로 제자리에서 분할하는 과정이 핵심입니다.
퀵 정렬과 힙 정렬
퀵 정렬은 평균적으로 빠르지만 최악 O(n²)이 발생할 수 있고, 힙 정렬은 모든 경우에 O(n log n)을 보장합니다.
이번 장 핵심 요약
- 정렬은 키를 기준으로 데이터를 일정한 순서로 재배치하는 작업입니다.
- 내부 정렬은 데이터를 메모리 안에서 처리하고, 외부 정렬은 보조기억장치를 함께 사용합니다.
- 삽입 정렬은 앞쪽 정렬 영역에 새 값을 삽입합니다.
- 버블 정렬은 인접 원소를 비교해 큰 값을 뒤로 이동시킵니다.
- 선택 정렬은 남은 영역의 최솟값을 선택해 앞쪽에 배치합니다.
- 삽입·버블·선택 정렬의 평균·최악 시간은 O(n²)입니다.
- 병합 정렬은 분할 후 병합하며 모든 경우 O(n log n)입니다.
- 퀵 정렬은 평균 O(n log n)이지만 피벗 선택이 나쁘면 O(n²)이 됩니다.
- 힙 정렬은 완전 이진 트리 형태의 힙을 이용하며 모든 경우 O(n log n)입니다.
- 안정 정렬은 같은 키를 가진 레코드의 기존 상대 순서를 유지합니다.
복습 문제
삽입 정렬은 어떤 방식으로 정렬할까?
앞쪽의 정렬된 영역에 새로운 값을 알맞은 위치로 삽입합니다.
초기 자료 8, 3, 4, 9, 7의 삽입 정렬 1회전 결과는?
3, 8, 4, 9, 7입니다.
버블 정렬 한 회전이 끝나면 어떤 값의 위치가 확정될까?
오름차순에서는 아직 정렬되지 않은 영역의 가장 큰 값이 뒤쪽에 확정됩니다.
선택 정렬에서 한 회전마다 선택하는 값은?
오름차순에서는 아직 정렬되지 않은 영역의 최솟값을 선택합니다.
초기 자료 37, 14, 17, 40, 35의 선택 정렬 3회전 결과는?
14, 17, 35, 40, 37입니다.
두 개의 정렬된 부분 배열을 합치며 O(n log n)에 정렬하는 방식은?
병합 정렬입니다.
피벗을 기준으로 데이터를 분할하는 정렬은?
퀵 정렬입니다.
퀵 정렬의 평균과 최악 시간 복잡도는?
평균은 O(n log n), 최악은 O(n²)입니다.
완전 이진 트리 형태의 자료 구조를 이용하는 정렬은?
힙 정렬입니다.
최악의 경우에도 O(n log n)을 보장하는 정렬은?
병합 정렬과 힙 정렬입니다.
참고자료
- 학습 범위 — 사무자동화산업기사 제1과목 사무자동화 시스템, 정렬 알고리즘
- Q-Net — 사무자동화산업기사 종목별 상세정보 및 출제기준
- NIST Dictionary of Algorithms and Data Structures — Sort
- NIST Dictionary of Algorithms and Data Structures — Sorting Terms
이 글은 사무자동화산업기사 시험 범위에 포함된 정렬 알고리즘을 이해하고 복습할 수 있도록 재구성한 정리입니다. 시간 복잡도는 구현 방식과 입력 상태에 따라 달라질 수 있으며, 특히 버블 정렬의 최선 O(n)은 교환 여부를 검사하는 조기 종료 최적화를 적용한 경우입니다. 실제 시험에서는 문제에서 제시한 알고리즘의 처리 방향과 회전 기준을 먼저 확인해야 합니다.