정렬 알고리즘 비교 — 버블·선택·삽입·퀵·병합

정렬 알고리즘은 자료 집합을 특정 기준(오름차순·내림차순)에 따라 재배열하는 알고리즘이다. 정보처리기사 시험에서는 개별 알고리즘의 구현 코드보다 시간복잡도와 안정성(stability) 같은 특성을 비교하는 문제가 반복 출제된다.

비교 기반 정렬의 두 축: 시간복잡도와 안정성

비교 기반 정렬은 원소끼리 크기를 비교해 순서를 정한다. 이때 두 가지 잣대로 알고리즘을 구분한다.

시간복잡도는 입력 크기 n에 따라 비교·교환 연산이 얼마나 늘어나는지를 나타낸다. 최선·평균·최악의 경우가 다른 알고리즘이 많아, 어떤 입력 상태에서 어떤 복잡도가 나오는지가 시험 포인트다.

안정성은 같은 값을 가진 두 원소의 상대적 순서가 정렬 후에도 유지되는지를 뜻한다. 예를 들어 학생을 점수로 정렬할 때 동점자의 원래 등록 순서를 지켜야 하는 경우 안정 정렬이 필요하다.

다섯 가지 대표 알고리즘

버블 정렬은 인접한 두 원소를 비교해 순서가 틀리면 교환하는 과정을 반복한다. 한 번 순회할 때마다 가장 큰(또는 작은) 값이 끝으로 이동한다. 구현이 단순하지만 평균·최악 모두 O(n²)이라 실무에서는 거의 쓰이지 않는다.

선택 정렬은 매 회전마다 정렬되지 않은 구간에서 최솟값을 찾아 맨 앞과 교환한다. 비교 횟수는 버블 정렬과 같은 O(n²)이지만 교환 횟수가 최대 n-1번으로 적다는 차이가 있다. 안정 정렬이 아니다 — 최솟값을 찾아 위치를 바꾸는 과정에서 같은 값의 순서가 뒤바뀔 수 있다.

삽입 정렬은 정렬된 구간을 하나씩 늘려가며, 새 원소를 알맞은 위치에 끼워 넣는다. 평균·최악은 O(n²)이지만 입력이 이미 거의 정렬돼 있으면 O(n)에 가깝게 동작한다. 이 특성 때문에 데이터가 작거나 부분적으로 정렬된 상황에서 실제로 쓰인다.

퀵 정렬은 기준값(피벗)을 하나 골라 그보다 작은 값과 큰 값으로 나눈 뒤, 각 구간을 재귀적으로 정렬하는 분할 정복 방식이다. 평균은 O(n log n)으로 빠르지만, 피벗을 매번 최솟값이나 최댓값으로 고르면 구간이 거의 나뉘지 않아 최악의 경우 O(n²)까지 떨어진다. 이미 정렬된 배열에서 첫 원소를 피벗으로 고르는 구현이 대표적인 최악 사례다.

병합 정렬은 배열을 절반씩 나눠 각각 정렬한 뒤 두 정렬된 구간을 합치는 방식이다. 분할과 병합이 항상 절반씩 이뤄지므로 최선·평균·최악 모두 O(n log n)으로 일정하다. 병합 과정에서 같은 값의 상대 순서가 유지되어 안정 정렬이다. 다만 병합할 때 별도의 배열 공간이 필요해 공간복잡도는 O(n)이다.

시험에 자주 나오는 포인트

시간복잡도를 외울 때는 평균과 최악을 구분해서 기억해야 한다. 버블·선택·삽입 정렬은 평균·최악이 모두 O(n²)로 같지만, 퀵 정렬은 평균 O(n log n)과 최악 O(n²)이 갈린다는 점이 자주 함정으로 나온다.

안정 정렬 여부를 묻는 문제도 반복된다. 삽입 정렬과 병합 정렬은 안정 정렬이고, 선택 정렬과 퀵 정렬은 안정 정렬이 아니다. 버블 정렬은 일반적인 구현 기준으로 안정 정렬로 분류한다.

또 하나는 병합 정렬과 퀵 정렬을 “둘 다 분할 정복”이라고 뭉뚱그리는 함정이다. 병합 정렬은 분할은 단순히 반으로 나누고 실제 비교·정렬 작업은 합치는 단계에서 일어나는 반면, 퀵 정렬은 피벗 기준으로 재배치하는 분할 단계에서 비교가 끝나고 별도의 병합 단계가 없다. 이 차이를 짚어 두면 두 알고리즘을 헷갈리지 않는다.