왜 정렬을 이렇게 자세히 다루는가

정렬(sorting)은 자료를 일정한 순서(오름차순 또는 내림차순)로 재배열하는 작업이다. 정렬 자체는 단순해 보이지만, 독학사 4단계 알고리즘 시험에서 정렬은 출제 빈도가 가장 높은 주제 중 하나다. 이유는 정렬 알고리즘이 “복잡도 분석”, “안정성 판별”, “제자리 정렬 여부”, “최선·평균·최악 케이스 구분” 같은 알고리즘 분석의 핵심 개념을 모두 담고 있는 좋은 실습 대상이기 때문이다.

이 편에서는 가장 기본적인 세 가지 비교 기반 정렬(comparison-based sort, 두 원소를 직접 비교해서 순서를 정하는 방식) 알고리즘인 선택 정렬, 삽입 정렬, 버블 정렬을 다룬다. “비교 기반”이라는 말이 중요한 이유는, 09편에서 배울 기수·계수 정렬처럼 값 자체를 비교하지 않고 분류하는 정렬과 대비되기 때문이다.

비교 기반 정렬 알고리즘을 보는 두 가지 잣대: 안정성과 제자리

본격적으로 세 알고리즘을 보기 전에, 이후 계속 등장할 두 가지 평가 기준을 먼저 정리한다.

쉽게 말하면: 안정성은 “같은 값끼리 순서가 안 바뀌는가”, 제자리는 “추가 배열 없이 원래 배열 안에서 정렬이 끝나는가”를 뜻한다.

• 안정 정렬(stable sort): 정렬 전에 값이 같았던 두 원소의 상대적 순서가 정렬 후에도 그대로 유지되는 정렬. 예를 들어 학생 명단을 이름순으로 이미 정렬해 둔 상태에서 다시 성적순으로 정렬할 때, 안정 정렬이면 같은 성적을 가진 학생들끼리는 원래의 이름순이 그대로 유지된다. 반대로 이 순서가 뒤섞일 수 있으면 불안정 정렬(unstable sort)이라 한다.
• 제자리 정렬(in-place sort): 정렬 대상 배열 외에 추가로 필요한 메모리가 상수 개(원소 개수와 무관한 $O(1)$) 뿐인 정렬. 배열 크기에 비례하는 추가 공간이 필요하면 제자리 정렬이 아니다.

선택 정렬: 매번 가장 작은 값을 골라 앞에 놓는다

쉽게 말하면: 남은 부분에서 가장 작은 값을 찾아 맨 앞자리와 자리를 바꾸는 과정을 반복한다.

선택 정렬(selection sort)은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 매 단계마다 정렬되지 않은 부분에서 최솟값을 찾아 정렬된 부분의 바로 뒤(즉 정렬 안 된 부분의 맨 앞)와 교환하는 방식이다.

선택 정렬 의사코드

SelectionSort(A, n)
  for i = 0 to n-2
    minIndex = i
    for j = i+1 to n-1
      if A[j] < A[minIndex]
        minIndex = j
    A[i]와 A[minIndex]를 교환

배열 [64, 25, 12, 22, 11]로 추적하기

결과 해석: 매 단계 정렬된 부분(왼쪽)이 한 칸씩 늘어난다. $i=3$에서는 이미 최솟값이 제자리에 있어 교환이 일어나지 않았지만, 그래도 비교 자체는 수행한다.

선택 정렬의 복잡도 유도

바깥 반복문은 $i=0$부터 $n-2$까지 총 $n-1$번 돌고, 안쪽 반복문은 $i$가 커질수록 비교 횟수가 줄어든다. $i=0$일 때 비교는 $n-1$번, $i=1$일 때는 $n-2$번, …, 마지막에는 1번이다. 이를 모두 더하면 다음과 같다.

지배항만 남기면 $\frac{n(n-1)}{2} = \frac{n^2-n}{2}$이므로 최고차항은 $n^2$이고, 상수·하위항을 제거하면 $O(n^2)$이다(03편에서 배운 점근적 표기 규칙 그대로 적용한 것이다). 이 비교 횟수는 배열이 이미 정렬되어 있어도, 완전히 역순이어도 항상 똑같다. 왜냐하면 선택 정렬은 “최솟값을 찾기 위한 비교”를 매번 남은 구간 전체에서 무조건 수행하기 때문이다. 그래서 선택 정렬은 최선·평균·최악이 모두 $O(n^2)$으로 동일한, 입력에 둔감한 알고리즘이다.

• 시간 복잡도: 최선·평균·최악 모두 $O(n^2)$
• 공간 복잡도: 교환에 쓰는 임시 변수 하나뿐이므로 $O(1)$ → 제자리 정렬
• 안정성: 최솟값을 찾아 먼 위치와 교환하는 과정에서 같은 값의 상대 순서가 바뀔 수 있다 → 불안정 정렬

배열 [5a, 2, 5b, 1](“5a”, “5b”는 값은 같은 5지만 원래 순서를 구분하기 위한 표기)을 선택 정렬하면, $i=0$에서 최솟값 1을 찾아 인덱스 0의 5a와 교환하는 과정에서 5a가 5b보다 뒤로 밀려나 원래 순서가 깨질 수 있다. 이 때문에 선택 정렬은 불안정하다고 분류한다.

삽입 정렬: 카드를 손에 쥐고 정렬하듯

쉽게 말하면: 카드놀이에서 새로 뽑은 카드를 이미 정렬된 카드 사이 알맞은 자리에 끼워 넣듯이, 현재 원소를 이미 정렬된 앞부분의 알맞은 위치에 삽입한다.

삽입 정렬(insertion sort)은 배열의 앞부분이 이미 정렬되어 있다고 가정하고, 그다음 원소를 그 정렬된 부분의 알맞은 위치에 밀어 넣는 방식이다.

삽입 정렬 의사코드

InsertionSort(A, n)
  for i = 1 to n-1
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key
      A[j+1] = A[j]
      j = j - 1
    A[j+1] = key

배열 [5, 2, 4, 6, 1, 3]으로 추적하기

결과 해석: $i=3$처럼 새 원소가 이미 자기 자리에 있으면(왼쪽 값보다 크면) 이동이 전혀 없다. 반대로 $i=4$처럼 새 원소가 가장 작으면 왼쪽 전체를 다 밀어야 한다. 이 차이가 삽입 정렬의 최선·최악 복잡도를 가른다.

삽입 정렬의 복잡도 유도

• 최악의 경우(입력이 완전 역순): 매 $i$번째 원소가 왼쪽에 있는 모든 원소보다 작아서 끝까지 밀어야 한다. 비교·이동 횟수는 선택 정렬과 똑같이 $1+2+\cdots+(n-1) = \frac{n(n-1)}{2}$이므로 $O(n^2)$이다.
• 최선의 경우(입력이 이미 정렬됨): while 조건의 A[j] > key가 매번 바로 거짓이 되어 각 $i$마다 비교를 딱 1번만 하고 멈춘다. 전체 비교 횟수는 $n-1$번이므로 $O(n)$이다.
• 평균의 경우: 임의의 순서로 놓인 입력이라면 각 원소는 평균적으로 자기 앞쪽 절반 정도를 이동한다고 볼 수 있어, 여전히 $O(n^2)$ 계열에 속한다.

이 최선 케이스 $O(n)$은 선택 정렬에는 없는 삽입 정렬만의 중요한 특징이다. 거의 정렬된 자료(정렬이 살짝 흐트러진 자료)에서는 삽입 정렬이 실제로 매우 빠르게 동작하며, 이 성질 때문에 07편에서 배울 퀵 정렬 등의 구현에서도 작은 부분 배열은 삽입 정렬로 마무리하는 최적화가 흔히 쓰인다.

• 시간 복잡도: 최선 $O(n)$, 평균·최악 $O(n^2)$
• 공간 복잡도: key, j 같은 변수 몇 개뿐이므로 $O(1)$ → 제자리 정렬
• 안정성: A[j] > key처럼 엄격한 부등호를 쓰면 같은 값은 밀어내지 않고 그 뒤에 삽입되므로 원래 순서가 유지된다 → 안정 정렬

버블 정렬: 인접한 두 값을 계속 맞바꾼다

쉽게 말하면: 이웃한 두 원소를 비교해서 순서가 잘못됐으면 맞바꾸는 일을 배열 끝까지, 그리고 여러 번 반복한다. 크기가 큰 원소가 거품처럼 뒤로 떠오른다.

버블 정렬(bubble sort)은 배열을 처음부터 끝까지 훑으면서 인접한 두 원소를 비교해, 순서가 틀렸으면(앞이 뒤보다 크면) 교환하는 과정을 배열 전체가 정렬될 때까지 반복한다. 한 번 훑을 때마다 그 구간에서 가장 큰 값이 마치 거품처럼 맨 뒤로 이동하기 때문에 이런 이름이 붙었다.

버블 정렬 의사코드 (조기 종료 포함)

BubbleSort(A, n)
  for i = 0 to n-2
    swapped = false
    for j = 0 to n-2-i
      if A[j] > A[j+1]
        A[j]와 A[j+1]를 교환
        swapped = true
    if swapped == false
      break

swapped(교환이 있었는가) 플래그는 한 번의 순회에서 교환이 한 건도 없었다면 이미 배열이 정렬된 것이므로 즉시 반복을 멈추는 조기 종료 장치다. 이 장치가 없으면 이미 정렬된 배열에도 항상 $n-1$번 순회를 다 도는 비효율이 생긴다.

배열 [5, 1, 4, 2, 8]로 추적하기 (1회차 순회)

결과 해석: 1회차 순회가 끝나자 가장 큰 값 8이 이미 맨 뒤에 도달했고, 원래 맨 앞의 5는 두 칸 오른쪽으로 이동했다. 다음 회차부터는 맨 뒤가 이미 정렬되었다고 보고 비교 범위를 하나씩 줄여나간다($n-2-i$).

버블 정렬의 복잡도 유도

바깥 순회는 최악의 경우 $n-1$번 필요하고, $i$번째 순회에서 비교는 $n-1-i$번 일어난다. 이를 모두 더하면 선택·삽입 정렬과 마찬가지로 $\frac{n(n-1)}{2}$번이 되어 $O(n^2)$이다. 다만 조기 종료 덕분에, 이미 정렬된 배열이 입력되면 1회차 순회에서 교환이 전혀 일어나지 않아 즉시 종료되므로 최선의 경우는 비교 $n-1$번만으로 끝나는 $O(n)$이다.

• 시간 복잡도: 최선(조기 종료 시) $O(n)$, 평균·최악 $O(n^2)$
• 공간 복잡도: 교환용 임시 변수뿐이므로 $O(1)$ → 제자리 정렬
• 안정성: A[j] > A[j+1]처럼 엄격한 부등호로 교환하므로, 같은 값끼리는 교환이 일어나지 않아 순서가 유지된다 → 안정 정렬

세 알고리즘 종합 비교

이 표에서 시험이 특히 좋아하는 함정은 두 가지다. 첫째, “세 알고리즘 모두 평균·최악이 $O(n^2)$이니 성능이 같다”고 오해하는 것 — 최선의 경우와 실전 특성(거의 정렬된 자료 등)까지 봐야 한다. 둘째, “안정성은 알고리즘의 본질적 속성이라 바꿀 수 없다”고 오해하는 것 — 실제로는 비교 조건을 >에서 >=로 바꾸는 등 구현 방식에 따라 안정성이 달라질 수 있으며, 시험에서는 표준적으로 제시된(위 의사코드 같은) 구현 기준으로 판단한다.

자주 틀리는 점

• 선택 정렬의 시간 복잡도가 입력에 따라 달라진다고 착각한다. 선택 정렬은 최솟값 탐색을 위해 항상 전체 구간을 비교하므로 최선·평균·최악이 모두 $O(n^2)$으로 동일하다. 이 점에서 삽입·버블 정렬(최선 $O(n)$)과 다르다.
• 삽입 정렬이 항상 $O(n^2)$이라고 단정한다. 이미 정렬되었거나 거의 정렬된 입력에서는 $O(n)$에 가깝게 동작한다.
• 버블 정렬에 조기 종료 장치가 없다고 가정하고 복잡도를 계산한다. 조기 종료(swapped 플래그) 여부에 따라 최선 케이스 복잡도가 $O(n^2)$과 $O(n)$으로 갈리므로, 문제에 제시된 의사코드에 그 장치가 있는지 반드시 확인한다.
• 안정성과 제자리 정렬을 같은 개념으로 혼동한다. 안정성은 “같은 값의 순서 유지”, 제자리는 “추가 메모리 사용량”으로 서로 다른 기준이다. 이 편의 세 알고리즘은 모두 제자리 정렬이지만 안정성은 선택 정렬만 다르다.
• 교환 횟수와 비교 횟수를 같은 것으로 계산한다. 선택 정렬은 비교는 $O(n^2)$번 하지만 교환은 최대 $n-1$번뿐이다. 교환(또는 원소 이동)의 비용이 클 때는 이 차이가 실제 성능에 영향을 준다.

핵심 정리

• 선택 정렬은 매 단계 최솟값을 찾아 앞자리와 교환하며, 최선·평균·최악 모두 $O(n^2)$이고 불안정, 제자리 정렬이다.
• 삽입 정렬은 정렬된 부분에 값을 끼워 넣으며, 최선 $O(n)$·평균과 최악 $O(n^2)$이고 안정, 제자리 정렬이다. 거의 정렬된 자료에 특히 강하다.
• 버블 정렬은 인접 원소를 맞바꾸며 전파하고, 조기 종료를 포함하면 최선 $O(n)$·평균과 최악 $O(n^2)$이며 안정, 제자리 정렬이다.
• 세 알고리즘 모두 시간 복잡도 차수는 $O(n^2)$ 계열이지만, 최선 케이스와 안정성에서 차이가 갈린다.
• 다음 07편에서는 이 $O(n^2)$의 한계를 분할정복으로 극복하는 퀵·병합 정렬을 다룬다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 4단계 알고리즘 과목 출제범위 중 기본 정렬 알고리즘 항목 확인
• GeeksforGeeks: Sorting Algorithms  — 선택·삽입·버블 정렬의 의사코드·복잡도·안정성 비교 정리