정보처리기사 필기 단골 출제 유형인 선택 정렬(Selection Sort)을 [7,3,9,2,5] 예제로 전체 패스를 완전히 트레이스하며 정리합니다. O(n²)인 이유, 불안정 정렬 반례, 교환 횟수 공식까지 검산으로 확인, 무료 강의.
선택 정렬, "남은 것 중 가장 작은 값"을 매번 앞으로 보내는 방식
선택 정렬(Selection Sort)은 정렬 안 된 구간 전체를 훑어서 가장 작은 값을 찾은 다음, 그 값을 정렬 구간의 맨 앞과 통째로 맞바꾸는 방식입니다. 버블 정렬처럼 인접한 두 값을 계속 비교·교환하는 것도 아니고, 삽입 정렬처럼 값을 한 칸씩 밀어내며 끼워 넣는 것도 아닙니다. 한 회전(Pass)에 딱 한 번만 교환이 일어난다는 점이 선택 정렬만의 가장 뚜렷한 특징입니다.
정보처리기사 필기에서는 선택 정렬이 단독으로 "N회전 후 배열 상태" 또는 "전체 교환 횟수"를 묻는 형태로 자주 출제됩니다. 이 글은 선택 정렬 하나만 처음부터 끝까지 손으로 완전히 계산하며 파고드는 심화 자료입니다. 원리를 한 문장으로 미리 정리하면 이렇습니다. "매 회전마다 남은 구간에서 최솟값의 위치를 찾고, 그 위치와 회전 시작 위치를 교환한다." 이 문장을 표로 직접 검증해 보겠습니다.
예제 배열 [7, 3, 9, 2, 5]로 전체 패스 완전 추적
원소가 5개인 배열 [7, 3, 9, 2, 5]를 오름차순으로 정렬합니다. 원소가 n개이면 선택 정렬은 총 n-1번의 패스만 진행합니다. 마지막 원소 1개는 나머지가 모두 제자리를 찾으면 자동으로 정렬되기 때문에 별도의 패스가 필요 없습니다. n=5이므로 이번 예제는 4번의 패스로 끝납니다.
| 패스 | 탐색 범위(인덱스) | 탐색 대상 값 | 발견한 최솟값(위치) | 교환 여부 | 패스 종료 후 배열 |
|---|---|---|---|---|---|
| 시작 | - | - | - | - | [7, 3, 9, 2, 5] |
| 1회전 (i=0) | 0~4 | 7, 3, 9, 2, 5 | 2 (인덱스 3) | 교환 O — 인덱스 0(7)과 인덱스 3(2) 교환 | [2, 3, 9, 7, 5] |
| 2회전 (i=1) | 1~4 | 3, 9, 7, 5 | 3 (인덱스 1) | 교환 X — 최솟값이 이미 회전 시작 위치 | [2, 3, 9, 7, 5] (변화 없음) |
| 3회전 (i=2) | 2~4 | 9, 7, 5 | 5 (인덱스 4) | 교환 O — 인덱스 2(9)과 인덱스 4(5) 교환 | [2, 3, 5, 7, 9] |
| 4회전 (i=3) | 3~4 | 7, 9 | 7 (인덱스 3) | 교환 X — 최솟값이 이미 회전 시작 위치 | [2, 3, 5, 7, 9] (변화 없음) |
4번째 패스가 끝나면 인덱스 4에 남는 마지막 값 9는 이미 배열 전체에서 가장 크므로 검사 없이도 제자리입니다. 최종 결과는 [2, 3, 5, 7, 9]로 완전히 정렬되었습니다. 이 예제에서 실제로 값을 옮긴 교환은 1회전과 3회전, 단 2번뿐이었습니다. 나머지 두 번의 패스는 배열 전체를 훑어 최솟값을 찾긴 했지만, 그 값이 이미 제자리에 있었기 때문에 교환 없이 넘어갔습니다. "패스 수 = 교환 횟수"로 착각하면 안 되는 이유가 바로 여기에 있습니다.
검산. 각 패스에서 최솟값을 찾을 때 발생하는 비교 횟수는 탐색 범위의 원소 개수보다 1 적습니다. 1회전은 5개 중 최솟값을 찾으므로 4회, 2회전은 4개 중이므로 3회, 3회전은 3개 중이므로 2회, 4회전은 2개 중이므로 1회 비교합니다. 합산하면 4+3+2+1 = 10회입니다. 뒤에서 다룰 비교 횟수 공식 n(n-1)/2에 n=5를 대입하면 5×4/2 = 10으로 정확히 일치합니다. 표와 공식 두 가지 방법으로 같은 값이 나왔으므로 이 트레이스는 검산이 끝난 결과입니다.
시간복잡도: 왜 최선의 경우에도 O(n²)인가
선택 정렬의 시간복잡도는 최선·평균·최악 모두 O(n²)로 동일합니다. 이 부분이 버블 정렬·삽입 정렬과 가장 크게 갈리는 지점입니다. 이유는 단순합니다. 선택 정렬은 매 패스마다 "남은 구간에서 최솟값을 찾는" 작업을 반드시 끝까지 전부 비교해야만 완료할 수 있습니다. 배열이 이미 정렬되어 있어서 교환이 한 번도 필요 없는 경우라도, 최솟값이 맞는지 확인하려면 남은 원소를 전부 살펴봐야 하므로 비교 횟수는 조금도 줄어들지 않습니다. "조기 종료" 자체가 구조적으로 불가능한 알고리즘입니다.
비교 횟수 공식. 원소가 n개일 때 1회전은 n-1회, 2회전은 n-2회, ... 마지막 패스는 1회 비교합니다. 이를 모두 더하면 다음과 같습니다.
(n-1) + (n-2) + ... + 1 = n(n-1) / 2
이 공식은 입력 배열의 초기 상태와 전혀 무관하게 항상 성립합니다. 위 예제(n=5)에서 10회가 나온 것도, 배열이 이미 정렬되어 있는 극단적인 경우라도 마찬가지로 10회가 나옵니다. 반면 교환 횟수는 최대 n-1번이며, 실제 교환 횟수는 배열 상태에 따라 0번부터 n-1번 사이에서 달라집니다. 이번 예제에서는 4번 중 2번(1회전, 3회전)만 교환이 일어났습니다. "비교는 항상 고정, 교환은 최대 n-1번이지만 상황에 따라 더 적을 수 있다"는 문장이 선택 정렬의 시간복잡도를 요약하는 핵심입니다.
불안정 정렬(Unstable Sort)인 이유 — 반례로 확인하기
선택 정렬은 불안정 정렬입니다. 최솟값을 찾은 위치와 회전 시작 위치를 거리에 상관없이 그대로 맞바꾸기 때문에, 그 사이에 있던 같은 값의 원소를 건너뛰면서 원래의 상대적 순서가 바뀔 수 있습니다. 말로만 설명하면 추상적이니 값이 같은 원소가 포함된 배열로 직접 검증해 보겠습니다.
키(key)가 같은 두 원소를 구분하기 위해 알파벳 표기를 붙인 배열 [5(A), 5(B), 2(C)]를 오름차순으로 정렬합니다. 정렬 전 5(A)는 인덱스 0, 5(B)는 인덱스 1에 있어 5(A)가 5(B)보다 앞입니다.
| 패스 | 탐색 범위 | 최솟값(위치) | 교환 | 결과 |
|---|---|---|---|---|
| 1회전 (i=0) | 5(A), 5(B), 2(C) | 2(C), 인덱스 2 | 인덱스 0 ↔ 인덱스 2 | [2(C), 5(B), 5(A)] |
| 2회전 (i=1) | 5(B), 5(A) | 5(B), 인덱스 1 (동률은 먼저 있는 값 유지) | 없음 | [2(C), 5(B), 5(A)] |
정렬이 끝난 결과는 [2(C), 5(B), 5(A)]입니다. 정렬 전에는 5(A)가 5(B)보다 앞에 있었는데, 정렬 후에는 5(B)가 5(A)보다 앞으로 순서가 뒤바뀌었습니다. 원인은 1회전에서 인덱스 0과 멀리 떨어진 인덱스 2를 교환하는 과정에서, 그 사이에 있던 5(B)를 그대로 지나쳐 5(A)가 5(B) 뒤로 넘어갔기 때문입니다. 이것이 선택 정렬이 불안정 정렬로 분류되는 이유를 보여주는 가장 짧은 반례입니다.
버블 정렬·삽입 정렬과의 차이 — "교환 횟수가 적다"는 특징
| 정렬 알고리즘 | 최선 | 평균/최악 | 안정 정렬 | 교환·이동 특징 |
|---|---|---|---|---|
| 선택 정렬 | O(n²) | O(n²) | 불안정 | 패스당 교환 최대 1회 → 전체 교환 최대 n-1회로 가장 적음 |
| 버블 정렬 | O(n) (조기 종료 시) | O(n²) | 안정 | 어긋난 인접 쌍마다 교환 → 최악의 경우 n(n-1)/2회까지 급증 |
| 삽입 정렬 | O(n) | O(n²) | 안정 | 정렬 구간에 값을 밀어 넣는 이동(shift) → 최악 n(n-1)/2회 |
세 알고리즘 모두 평균·최악 시간복잡도는 O(n²)로 같지만, 선택 정렬만 실제로 값을 옮기는 횟수(교환)가 항상 n-1회 이하로 제한된다는 점이 뚜렷한 차별점입니다. 버블 정렬과 삽입 정렬은 배열이 뒤섞여 있을수록 교환·이동 횟수가 비교 횟수만큼 불어날 수 있지만, 선택 정렬은 아무리 배열이 심하게 뒤섞여 있어도 교환은 최대 n-1번을 넘지 않습니다. 이 특징 때문에 비교 비용보다 쓰기(교환) 비용이 훨씬 비싼 환경 — 예를 들어 쓰기 수명이 제한적인 플래시 메모리 — 에서는 선택 정렬의 "교환 최소화" 특성이 실무적으로 언급되기도 합니다. 다만 안정성이 필요한 상황이라면 선택 정렬은 적합하지 않다는 점도 함께 기억해야 합니다.
코드로 확인하기
파이썬과 자바로 각각 구현한 선택 정렬입니다. 안쪽 반복문에서 min_idx를 갱신만 하고, 바깥 반복문이 끝날 때 딱 한 번만 교환하는 구조를 코드에서도 확인할 수 있습니다.
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
print(selection_sort([7, 3, 9, 2, 5]))
# [2, 3, 5, 7, 9]
public static void selectionSort(int[] arr) {
int n = arr.length;
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;
}
}
if (minIdx != i) {
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}
}
코드에서 if min_idx != i 조건을 눈여겨봐야 합니다. 이 조건이 있기 때문에 최솟값이 이미 제자리에 있는 패스(위 트레이스의 2회전, 4회전)에서는 불필요한 교환이 생략됩니다. 이 조건을 빼고 무조건 교환하도록 구현하면 알고리즘의 결과는 같지만, 매 패스마다 자기 자신과 교환하는 의미 없는 연산이 추가되어 "전체 교환 횟수 = n-1"이라는 시험 공식과 실제 코드 동작이 어긋나 보일 수 있습니다.
시험에서 자주 틀리는 함정
- 교환 횟수를 패스 횟수와 동일시하는 착각 — 위 예제처럼 패스는 4번 진행돼도 실제 교환은 2번뿐일 수 있습니다. "N번째 패스까지 교환이 몇 번 일어났는가"를 물으면 반드시 각 패스에서 최솟값 위치와 회전 시작 위치가 같은지부터 확인해야 합니다.
- 최솟값 탐색 범위를 잘못 잡는 실수 — k회전의 탐색 범위는 인덱스 k-1부터 끝까지입니다(1-based 기준). 이미 정렬이 끝난 앞쪽 구간까지 포함해서 최솟값을 다시 찾으면 오답이 나옵니다.
- 최선의 경우를 O(n)으로 착각 — 삽입 정렬·버블 정렬은 이미 정렬된 배열에서 O(n)까지 빨라지지만, 선택 정렬은 배열이 아무리 정렬되어 있어도 매번 전체 구간을 끝까지 비교해야 하므로 최선의 경우도 O(n²)입니다.
- 안정 정렬로 착각 — "정렬 알고리즘의 안정성" 표 문제에서 선택 정렬만 유일하게 불안정 정렬입니다. 버블·삽입 정렬과 묶어서 안정 정렬이라고 답하면 틀립니다.
- 비교 횟수 공식 n(n-1)/2를 교환 횟수 공식으로 착각 — n(n-1)/2는 비교 횟수 공식입니다. 교환 횟수의 최댓값은 n-1이며, 두 공식을 바꿔 쓰면 안 됩니다.
자주 묻는 질문
선택 정렬은 몇 번의 패스(회전)를 진행하나요?
원소가 n개라면 총 n-1번의 패스를 진행합니다. 앞의 n-1개 원소가 각자 제자리를 찾으면 마지막 1개는 자동으로 정렬되기 때문에 별도의 패스가 필요 없습니다. 위 예제(n=5)에서도 4번의 패스로 정렬이 끝났습니다.
선택 정렬의 전체 교환 횟수는 항상 n-1번인가요?
아닙니다. n-1번은 최댓값일 뿐입니다. 각 패스에서 찾은 최솟값이 이미 회전 시작 위치에 있다면 교환은 일어나지 않습니다. 위 예제에서는 4번의 패스 중 2번만 실제로 교환이 일어났습니다. 다만 "비교 횟수"는 배열 상태와 무관하게 항상 n(n-1)/2로 고정된다는 점과 구분해서 기억해야 합니다.
선택 정렬과 삽입 정렬 중 어느 쪽이 시험에서 더 안전한 선택인가요?
"안정 정렬인가?"를 묻는 문제라면 삽입 정렬(안정)과 선택 정렬(불안정)의 답이 다르므로 반드시 구분해서 암기해야 합니다. "최선의 경우 시간복잡도"를 묻는 문제도 삽입 정렬은 O(n), 선택 정렬은 O(n²)로 다릅니다. 반면 "교환·이동 횟수가 가장 적은 알고리즘은?"이라는 질문에는 선택 정렬(최대 n-1회)이 정답에 가깝습니다. 문제가 묻는 기준이 무엇인지부터 정확히 파악하는 것이 중요합니다.
이런 분께 딱 맞는 강의입니다
- 정보처리기사 필기를 준비 중인 수험생
- 정렬 알고리즘 파트에서 패스별 결과·교환 횟수 문제를 틀려본 분
- 선택 정렬과 버블 정렬이 헷갈리는 분
- 비전공자라 알고리즘이 낯설지만 정처기에 도전하는 분
- 선택 정렬 하나만 완전히 손으로 검산하며 정리하고 싶은 분
수강 정보
| 항목 | 내용 |
|---|---|
| 수강료 | 무료 |
| 강의 수 | 1강 |
| 카테고리 | 자격증 |
| 강사 | 누구나패스 |
| 수강 방식 | 온라인(PC·모바일) |
회원가입 후 즉시 수강할 수 있으며, 언제든 다시 돌려볼 수 있습니다. 추가 비용 없이 무료로 제공됩니다.
함께 보면 좋은 글
선택 정렬을 확실히 정리했다면, 같은 방식으로 삽입 정렬을 단독으로 완전히 트레이스한 글과 세 정렬 알고리즘을 한 번에 비교한 글도 이어서 확인해 보세요.
삽입 정렬(Insertion Sort) 완벽 이해 — 정보처리기사 자료구조 핵심 정리 →
정처기 자료구조 핵심: 버블 정렬·선택·삽입 정렬 원리 한 번에 정리 →
지금 바로 무료로 확인하세요
정보처리기사 시험에서 정렬 알고리즘은 원리와 계산 과정만 손에 익히면 무조건 득점할 수 있는 영역입니다. 선택 정렬의 패스별 동작과 교환 횟수 계산을 이번 글의 표로 직접 다시 그려보면서 검산하는 연습을 추천합니다.
댓글
불러오는 중...
