정보처리기사 필기 자료구조 핵심, 버블·선택·삽입 정렬 3가지를 같은 예제 배열로 한 번에 비교합니다. 1회차 동작 차이, 시간복잡도·안정성 비교표, 시험 대비 팁까지 정리했습니다.
정렬 알고리즘, 시험에서 자꾸 틀리는 이유
정보처리기사 필기 시험에서 자료구조 파트는 매 회차 빠지지 않고 출제됩니다. 그중에서도 버블 정렬(Bubble Sort)은 원리가 단순해 보이지만, 단계별 진행 과정을 손으로 추적하다 보면 헷갈리는 경우가 많습니다. 선택 정렬·삽입 정렬과 혼동해 시간 복잡도나 안정성을 잘못 기억하는 것도 흔한 실수입니다.
이 글은 버블 정렬 하나만 파고드는 대신, 시험에 가장 자주 함께 등장하는 버블·선택·삽입 정렬 세 가지를 같은 예제 배열로 나란히 비교해서 "무엇이 다른지"를 한 번에 정리하는 것을 목표로 합니다. 각 알고리즘을 처음부터 끝까지 스텝별로 완전히 풀어보는 심화 학습은 알고리즘별 단독 글에서 다루고, 이 글에서는 세 알고리즘의 핵심 차이에 집중합니다.
무엇을 배우나요?
단 1강 안에 정렬 알고리즘의 핵심 개념이 압축되어 있습니다.
| 주제 | 내용 |
|---|---|
| 버블 정렬 원리 | 인접한 두 값을 비교·교환하는 Pass별 과정 단계별 시각화 |
| 시간 복잡도 | 최선·평균·최악 O(n²) 이해 — 시험 출제 포인트 정리 |
| 선택 정렬 비교 | 매 Pass에서 최솟값을 찾는 방식과 버블 정렬의 차이점 |
| 삽입 정렬 비교 | 이미 정렬된 구간에 삽입하는 방식과 세 알고리즘 비교 총정리 |
버블·선택·삽입, 핵심 아이디어부터 다르게 시작합니다
버블 정렬은 배열의 맨 앞부터 끝까지 인접한 두 값을 계속 비교하면서, 순서가 틀리면 그 자리에서 바로 맞바꾸는 방식입니다. 한 번의 Pass가 끝날 때마다 그 구간에서 가장 큰 값이 물거품처럼 맨 뒤로 밀려 올라가기 때문에 "버블(bubble)"이라는 이름이 붙었습니다. 비교와 교환이 함께 자주 일어나는 것이 특징입니다.
선택 정렬은 접근 방식이 정반대입니다. 정렬 안 된 구간 전체를 먼저 훑어서 최솟값의 위치를 찾은 뒤, 그 값을 정렬 구간의 맨 앞과 딱 한 번만 교환합니다. 매 Pass마다 비교는 배열 전체를 훑을 만큼 많이 일어나지만, 실제로 값을 옮기는 교환은 최대 1번뿐입니다.
삽입 정렬은 트럼프 카드를 손에 쥐고 정렬하는 방식과 비슷합니다. 왼쪽에 이미 정렬된 작은 구간이 있다고 가정하고, 그 오른쪽의 값 하나를 꺼내 정렬된 구간의 알맞은 자리에 밀어 넣습니다(삽입). 정렬 구간이 아직 짧을 때는 비교·이동 범위가 매우 좁다는 것이 핵심입니다.
같은 배열, 다른 첫걸음 — 1회차(패스) 동작 비교
세 알고리즘의 차이를 가장 빠르게 체감하는 방법은 똑같은 배열을 주고 "1회차(첫 Pass)"만 진행했을 때 무엇이 달라지는지 나란히 보는 것입니다. 배열 [4, 2, 5, 1, 3]을 오름차순으로 정렬한다고 할 때, 각 알고리즘의 1회차 결과는 다음과 같습니다. (전체 완전 풀이는 아래 삽입 정렬 심화 글에서 5단계 전체 트레이스로 확인할 수 있습니다.)
| 정렬 | 1회차 종료 후 배열 | 비교 횟수 | 교환/이동 횟수 | 이번 회차에서 벌어진 일 |
|---|---|---|---|---|
| 버블 정렬 | [2, 4, 1, 3, 5] | 4회 | 교환 3회 | (4,2)→교환, (4,5)→유지, (5,1)→교환, (5,3)→교환. 배열 끝까지 인접 비교를 반복하며 최댓값 5가 맨 뒤로 확정 |
| 선택 정렬 | [1, 2, 5, 4, 3] | 4회 | 교환 1회 | 배열 전체(4,2,5,1,3)를 훑어 최솟값 1(인덱스 3)을 찾은 뒤, 인덱스 0과 딱 한 번 교환 |
| 삽입 정렬 | [2, 4, 5, 1, 3] | 1회 | 이동 1회 | 정렬 대상은 아직 앞 원소 1개(4)뿐. 두 번째 값 2를 4와 비교해 앞으로 밀어 넣음 — 뒤쪽 [5,1,3]은 손도 대지 않음 |
같은 1회차인데도 버블 정렬은 배열 전체를 훑으며 3번이나 값을 맞바꾸고, 선택 정렬은 똑같이 전체를 훑지만 교환은 1번뿐이며, 삽입 정렬은 아예 배열 뒤쪽을 건드리지도 않는다는 차이가 한눈에 드러납니다. 이 차이가 뒤에서 다룰 "교환 횟수", "안정성", "이미 정렬된 데이터에 강한 알고리즘" 같은 시험 포인트로 그대로 이어집니다.
왜 이런 차이가 나타날까 — 비교 횟수 vs 이동 횟수 공식
원소가 n개일 때, 버블 정렬과 선택 정렬의 비교 횟수는 둘 다 n(n-1)/2번으로 동일합니다. n=5인 이번 예제 기준으로는 총 10회입니다(1회차에서는 그중 4회만 진행된 것입니다). 두 알고리즘 모두 정렬 안 된 구간을 끝까지 훑기 때문에 비교 횟수 자체는 차이가 없습니다.
차이는 "값을 실제로 옮기는 횟수"에서 갈립니다. 선택 정렬은 Pass마다 교환이 최대 1번이므로 전체 교환 횟수가 정확히 n-1번(이번 예제는 4번)으로 고정됩니다. 반면 버블 정렬은 순서가 어긋난 인접 쌍을 만날 때마다 매번 교환하므로, 최악의 경우(완전 역순 배열) 비교 횟수와 똑같이 n(n-1)/2번까지 교환이 일어날 수 있습니다. 삽입 정렬의 이동 횟수도 최악의 경우 n(n-1)/2번까지 늘어나지만, 이번 예제의 1회차처럼 정렬 구간이 짧을 때는 이동이 거의 일어나지 않습니다. 이 "비교는 비슷해도 이동 비용이 다르다"는 점이 세 알고리즘을 구분하는 핵심 축입니다.
시간복잡도·공간복잡도·안정성, 헷갈리지 않게 표로 정리
| 알고리즘 | 최선 | 평균 | 최악 | 공간복잡도 | 안정 정렬(Stable) |
|---|---|---|---|---|---|
| 버블 정렬 | O(n) (조기 종료 적용 시) | O(n²) | O(n²) | O(1) | 안정 |
| 선택 정렬 | O(n²) | O(n²) | O(n²) | O(1) | 불안정 |
| 삽입 정렬 | O(n) | O(n²) | O(n²) | O(1) | 안정 |
세 알고리즘 모두 추가 배열 없이 제자리에서 정렬하므로 공간복잡도는 O(1)로 동일합니다. 다만 선택 정렬은 이미 정렬된 배열을 넣어도 최솟값을 찾기 위해 매번 전체를 끝까지 훑어야 하므로 최선의 경우조차 O(n²)입니다. 반면 버블 정렬(조기 종료 조건 포함)과 삽입 정렬은 이미 정렬된 배열이 들어오면 한 바퀴만 돌고 O(n)에 끝낼 수 있습니다.
안정성(Stable) 여부도 시험에서 자주 묻는 포인트입니다. 버블 정렬은 값이 클 때만 교환하므로 같은 값끼리는 순서가 바뀌지 않고, 삽입 정렬도 더 클 때만 뒤로 밀기 때문에 안정적입니다. 하지만 선택 정렬은 최솟값을 찾은 자리와 정렬 구간의 맨 앞을 멀리 떨어진 위치라도 그냥 맞바꿔버리기 때문에, 같은 값을 가진 다른 원소를 건너뛰어 순서가 뒤바뀌는 경우가 생깁니다. 그래서 세 정렬 중 선택 정렬만 유일하게 불안정 정렬로 분류됩니다.
시험 vs 실무 — 언제 어떤 정렬을 구분해서 기억하면 좋을까
시험 대비. "안정 정렬이 아닌 것은?"류 문제는 선택 정렬을 정답으로 고르면 됩니다. "한 회전(Pass)마다 교환이 최대 1번만 일어나는 정렬은?"이나 "전체 교환 횟수가 정확히 n-1번인 정렬은?" 같은 문제도 선택 정렬을 가리킵니다. 반대로 "이미 정렬된 배열에서 최선의 시간복잡도가 O(n)인 정렬 두 가지는?"이라고 물으면 버블 정렬(조기 종료 조건 포함)과 삽입 정렬이 정답입니다. 세 알고리즘의 이름과 "무엇이 최소로 유지되는가"(버블=비교, 선택=교환, 삽입=이동 범위)를 한 문장씩 짝지어 외워두면 헷갈릴 일이 크게 줄어듭니다.
실무 감각. 세 알고리즘 모두 대량의 실제 데이터에는 퀵정렬·병합정렬·Timsort 같은 O(n log n) 알고리즘에 자리를 내줍니다. 다만 삽입 정렬만은 예외적으로 지금도 살아남아 있는데, 데이터가 이미 거의 정렬돼 있거나 원소 개수가 아주 작은 구간을 처리할 때는 오버헤드가 적어 오히려 더 빠르기 때문입니다. 그래서 Python의 Timsort, Java의 Arrays.sort() 등 실제 표준 정렬 라이브러리 내부에서도 작은 구간을 나눠 처리할 때 삽입 정렬이 부분적으로 사용됩니다.
메모리 쓰기 비용이 비쌀 때. 비교 비용보다 값을 옮기는(쓰기) 비용이 훨씬 비싼 환경, 예를 들어 쓰기 수명이 제한적인 플래시 메모리나 EEPROM처럼 특수한 하드웨어 위에서 정렬해야 한다면, 교환 횟수가 항상 n-1번으로 가장 적은 선택 정렬이 오히려 유리할 수 있습니다. 이런 "교환/이동 횟수 최소화"라는 선택 정렬의 특성은 시험에서도, 실무 면접 질문에서도 자주 언급되는 포인트입니다.
더 깊이 알고 싶다면 — 삽입 정렬 심화 학습
이 글은 세 정렬을 나란히 놓고 차이를 비교하는 개괄 글입니다. 삽입 정렬 하나만 처음부터 끝까지 스텝별로 완전히 트레이스하며 이해하고 싶다면 아래 글을 확인해 보세요.
삽입 정렬(Insertion Sort) 완벽 이해 — 정보처리기사 자료구조 핵심 정리 →
이런 분께 추천합니다
- 정보처리기사 필기 시험을 처음 준비하는 분
- 자료구조 파트에서 정렬 알고리즘 문제를 자꾸 틀리는 분
- 버블·선택·삽입 정렬의 차이가 헷갈리는 분
- 시간 복잡도·안정성 개념을 빠르게 정리하고 싶은 분
- 비전공자이지만 정처기 자격증 취득을 목표로 하는 분
수강 정보
| 항목 | 내용 |
|---|---|
| 수강료 | 무료 |
| 강의 수 | 1강 |
| 카테고리 | 자격증 |
| 강사 | 누구나패스 |
| 수강 방식 | 온라인 (PC·모바일 모두 가능) |
자주 묻는 질문
버블 정렬의 시간 복잡도는 얼마인가요?
버블 정렬의 시간 복잡도는 최선·평균·최악 모두 O(n²)입니다. 단, 이미 정렬된 배열에 조기 종료 조건을 추가하면 최선 O(n)이 될 수 있습니다. 이 강의에서 시험 출제 기준에 맞춰 명확히 설명합니다.
버블 정렬과 선택 정렬 중 교환 횟수가 더 적은 것은?
선택 정렬입니다. 선택 정렬은 매 Pass마다 최솟값을 찾은 뒤 딱 한 번만 교환하므로 전체 교환 횟수가 최대 n-1번으로 제한됩니다. 반면 버블 정렬은 순서가 어긋난 인접 쌍을 만날 때마다 교환하므로, 최악의 경우(역순 배열) 교환 횟수가 훨씬 많아질 수 있습니다. 다만 두 알고리즘 모두 비교 횟수 자체는 O(n²) 수준으로 동일합니다.
세 알고리즘 중 안정 정렬(Stable Sort)은 몇 개인가요?
버블 정렬과 삽입 정렬은 안정 정렬이고, 선택 정렬만 불안정 정렬입니다. 선택 정렬은 최솟값을 찾은 위치와 정렬 구간의 맨 앞을 거리에 상관없이 그대로 맞바꾸기 때문에, 같은 값을 가진 다른 원소를 건너뛰면서 원래의 상대적 순서가 뒤바뀔 수 있습니다.
이미 정렬된 배열이라면 어떤 정렬이 가장 빠른가요?
조기 종료 조건을 넣은 버블 정렬과 삽입 정렬은 이미 정렬된 배열에서 O(n)에 끝낼 수 있습니다. 반면 선택 정렬은 정렬 여부와 무관하게 매번 남은 구간 전체를 끝까지 훑어 최솟값을 찾아야 하므로, 이미 정렬돼 있어도 항상 O(n²)입니다.
세 정렬 중 코드가 가장 짧고 구현이 쉬운 것은 무엇인가요?
보통 버블 정렬이 이중 반복문과 인접 비교·교환만으로 이루어져 세 알고리즘 중 코드가 가장 직관적이라고 평가받습니다. 선택 정렬은 최솟값의 인덱스를 별도로 추적해야 하고, 삽입 정렬은 값을 오른쪽으로 밀어내는 반복 이동 로직이 추가로 필요해 코드 줄 수가 조금 더 늘어나는 편입니다. 다만 세 알고리즘 모두 이중 반복문 구조라는 뼈대는 동일하기 때문에, 하나를 확실히 이해하면 나머지 두 개도 비교적 수월하게 익힐 수 있습니다.
비전공자도 이해할 수 있나요?
네. 프로그래밍 경험이 없어도 그림과 단계별 과정으로 설명하기 때문에 알고리즘을 처음 접하는 분도 무리 없이 따라올 수 있습니다.
정처기 필기 시험에서 정렬 알고리즘은 얼마나 자주 나오나요?
자료구조·알고리즘 과목에서 매 회차 1~3문제가 출제됩니다. 버블·선택·삽입 정렬은 출제 빈도가 높은 단골 주제로, 단계별 진행 결과값과 시간 복잡도·안정성을 반드시 암기해야 합니다.
댓글
불러오는 중...
