줄을 서시오! 가장 기본적이면서도 강력한 정렬 알고리즘 5가지 완벽 정복

컴퓨터 과학의 세계에서 ‘정렬(Sorting)’은 데이터를 특정 순서(오름차순 또는 내림차순)에 따라 나열하는 가장 기본적이면서도 중요한 작업 중 하나입니다. 우리가 인터넷에서 상품을 ‘낮은 가격순’으로 검색하거나, 주소록에서 친구를 ‘가나다순’으로 찾을 때, 그 이면에는 모두 정렬 알고리즘이 tirelessly 일하고 있습니다. 수많은 정렬 알고리즘이 존재하지만, 그중에서도 거품(Bubble), 삽입(Insertion), 선택(Selection), 퀵(Quick), 병합(Merge) 정렬은 모든 개발자가 반드시 이해해야 할 ‘클래식’과도 같습니다.

이 알고리즘들은 단순히 데이터를 정렬하는 방법을 넘어, 각기 다른 문제 해결 철학과 효율성의 트레이드오프(trade-off)를 담고 있습니다. 어떤 알고리즘은 이해하기는 쉽지만 데이터가 많아지면 극도로 느려지고, 어떤 알고리즘은 조금 복잡하지만 압도적인 속도를 자랑합니다. 이들의 작동 원리를 이해하는 것은 코딩 테스트의 단골 문제를 해결하는 열쇠일 뿐만 아니라, 대용량 데이터를 효율적으로 처리해야 하는 실제 개발 현장에서 최적의 솔루션을 선택할 수 있는 안목을 길러줍니다.

본 글에서는 이 5가지 핵심 정렬 알고리즘이 각각 어떤 원리로 동작하는지, 그 장단점과 성능(시간 복잡도)은 어떻게 다른지 명확하게 비교 분석해 보겠습니다. 이 글을 통해 여러분은 어떠한 데이터가 주어지더라도 자신감 있게 최적의 정렬 방법을 선택하고 구현할 수 있는 개발자로 거듭날 것입니다.

---

O(n²)의 느리지만 착한 삼총사: 거품, 삽입, 선택 정렬

데이터의 크기가 작을 때는 충분히 유용하지만, 커질수록 성능이 급격히 저하되는 O(n²) 시간 복잡도를 가진 기본적인 정렬 알고리즘들입니다. 구현이 간단하고 직관적이어서 정렬 알고리즘의 원리를 처음 배울 때 가장 먼저 접하게 됩니다.

거품 정렬 (Bubble Sort)

핵심 아이디어: 옆 사람과 계속 비교하며 끝으로 밀어낸다

거품 정렬은 서로 인접한 두 원소를 비교하여, 정렬 순서에 맞지 않으면 그 위치를 교환하는(swap) 방식을 사용하는 가장 단순한 정렬 알고리즘입니다. 이 과정을 리스트의 처음부터 끝까지 반복하면, 가장 큰 원소가 마치 물속의 거품처럼 가장 마지막 위치로 올라가게 됩니다. 이런 과정을 전체 데이터 개수만큼 반복하면 모든 데이터가 정렬됩니다.

정렬 과정 (오름차순): [5, 1, 4, 2]

1. 1회전 (Round 1):
   • [5, 1] 비교 → [1, 5] 교환
   • [5, 4] 비교 → [4, 5] 교환
   • [5, 2] 비교 → [2, 5] 교환
   • 결과: [1, 4, 2, 5] (가장 큰 5가 맨 뒤로 이동 완료)
2. 2회전 (Round 2): (마지막 5는 제외하고 진행)
   • [1, 4] 비교 → 교환 안 함
   • [4, 2] 비교 → [2, 4] 교환
   • 결과: [1, 2, 4, 5] (두 번째로 큰 4가 자기 자리로 이동 완료)
3. 3회전 (Round 3): (마지막 4, 5는 제외하고 진행)
   • [1, 2] 비교 → 교환 안 함
   • 결과: [1, 2, 4, 5] (정렬 완료)

성능 및 특징:

• 시간 복잡도: 최선, 평균, 최악 모두 O(n²) 입니다. (이미 정렬된 경우에도 불필요한 비교를 계속합니다. 단, 특정 회전에서 교환이 한 번도 일어나지 않으면 정렬이 완료된 것으로 보고 조기 종료하는 최적화가 가능합니다.)
• 공간 복잡도:O(1). 주어진 배열 내에서 교환만으로 정렬하므로 추가적인 메모리가 거의 필요 없습니다.
• 안정 정렬 (Stable Sort): Yes. 값이 같은 원소의 상대적인 순서가 정렬 후에도 유지됩니다.
• 장점: 구현이 매우 간단하고 직관적입니다.
• 단점: 성능이 매우 비효율적이어서 실제 현업에서는 거의 사용되지 않습니다.

삽입 정렬 (Insertion Sort)

핵심 아이디어: 내 자리를 찾아 차례대로 끼워 넣는다

삽입 정렬은 이미 정렬된 부분 배열에 새로운 원소를 ‘삽입’해 나가면서 정렬을 완성하는 알고리즘입니다. 두 번째 원소부터 시작하여, 각 원소를 앞쪽의 정렬된 부분과 비교하면서 자신이 들어갈 올바른 위치를 찾아 그 자리에 삽입합니다. 이는 마치 우리가 손에 쥔 카드를 정렬할 때, 새로운 카드를 뽑아 이미 정렬된 카드들 사이의 적절한 위치에 끼워 넣는 방식과 매우 유사합니다.

정렬 과정 (오름차순): [5, 1, 4, 2]

1. 1단계:[5]는 이미 정렬된 부분.
2. 2단계:1을 꺼냅니다. 5와 비교하니 1이 더 작으므로, 5를 뒤로 밀고 그 앞에 1을 삽입합니다.
   • 결과: [1, 5, 4, 2]
3. 3단계:4를 꺼냅니다. 5와 비교하니 4가 더 작습니다. 5를 뒤로 밉니다. 1과 비교하니 4가 더 큽니다. 1과 5 사이에 4를 삽입합니다.
   • 결과: [1, 4, 5, 2]
4. 4단계:2를 꺼냅니다. 5, 4와 비교하니 2가 더 작습니다. 둘 다 뒤로 밉니다. 1과 비교하니 2가 더 큽니다. 1과 4 사이에 2를 삽입합니다.
   • 결과: [1, 2, 4, 5] (정렬 완료)

성능 및 특징:

• 시간 복잡도: 평균과 최악의 경우 O(n²) 입니다. 하지만 최선의 경우, 즉 이미 데이터가 거의 정렬되어 있는 상태에서는 O(n) 에 가까운 매우 빠른 성능을 보입니다.
• 공간 복잡도:O(1). 인플레이스(in-place) 정렬입니다.
• 안정 정렬 (Stable Sort): Yes.
• 장점: 구현이 간단하고, 특히 데이터가 거의 정렬된 상태에서는 어떤 복잡한 알고리즘보다도 빠를 수 있습니다. 데이터 크기가 작을 때 효율적입니다.
• 단점: 데이터가 많고 역순에 가까울수록 성능이 급격히 저하됩니다.

선택 정렬 (Selection Sort)

핵심 아이디어: 최소값을 찾아 맨 앞으로 보낸다

선택 정렬은 전체 데이터 중에서 가장 작은 값(최소값)을 찾아 첫 번째 위치의 원소와 교환하는 방식으로 동작합니다. 그 다음, 첫 번째 원소를 제외한 나머지 데이터 중에서 다시 최소값을 찾아 두 번째 위치와 교환합니다. 이 과정을 끝까지 반복하면 전체 데이터가 정렬됩니다.

정렬 과정 (오름차순): [5, 1, 4, 2]

1. 1회전: 전체 [5, 1, 4, 2]에서 최소값은 1입니다. 현재 첫 번째 위치의 5와 1을 교환합니다.
   • 결과: [1, 5, 4, 2]
2. 2회전:1을 제외한 [5, 4, 2]에서 최소값은 2입니다. 현재 두 번째 위치의 5와 2를 교환합니다.
   • 결과: [1, 2, 4, 5]
3. 3회전:1, 2를 제외한 [4, 5]에서 최소값은 4입니다. 현재 세 번째 위치의 4와 교환합니다. (변화 없음)
   • 결과: [1, 2, 4, 5] (정렬 완료)

성능 및 특징:

• 시간 복잡도: 최선, 평균, 최악 모두 O(n²) 입니다. 데이터가 이미 정렬되어 있어도 최소값을 찾기 위해 끝까지 비교해야 하므로 성능 개선이 없습니다.
• 공간 복잡도:O(1). 인플레이스(in-place) 정렬입니다.
• 안정 정렬 (Stable Sort): No. 값이 같은 원소가 있을 경우, 최소값을 찾아 교환하는 과정에서 그 상대적 순서가 바뀔 수 있습니다.
• 장점: 구현이 간단합니다. 데이터의 실제 교환(swap) 횟수가 다른 O(n²) 알고리즘에 비해 적다는 특징이 있습니다.
• 단점: 데이터 상태와 무관하게 항상 O(n²)의 성능을 보여 비효율적입니다.

---

O(n log n)의 빠르고 강력한 듀오: 퀵, 병합 정렬

데이터의 크기가 커져도 효율적인 성능을 보장하는, ‘분할과 정복(Divide and Conquer)’ 기법에 기반한 고급 정렬 알고리즘입니다. 실제 현업에서 가장 널리 사용되는 방식들입니다.

퀵 정렬 (Quick Sort)

핵심 아이디어: 기준(피벗)을 정하고, 좌우로 나눈다

퀵 정렬은 현대적인 프로그래밍 언어의 내장 정렬 함수에서 가장 흔하게 채택되는, 이름처럼 매우 빠른 정렬 알고리즘입니다. ‘분할과 정복’ 전략을 사용하며, 그 핵심은 ‘피벗(pivot)’이라는 기준 값에 있습니다.

1. 배열에서 임의의 원소 하나를 ‘피벗’으로 선택합니다.
2. 피벗보다 작은 원소들은 모두 피벗의 왼쪽으로, 큰 원소들은 모두 오른쪽으로 이동시킵니다. (이 과정을 ‘분할(Partition)’이라고 합니다.)
3. 이제 피벗을 기준으로 배열은 두 개의 부분 배열로 나뉘게 됩니다.
4. 이 두 개의 부분 배열에 대해 위 과정을 재귀적으로 반복합니다.
5. 부분 배열의 크기가 0이나 1이 되면 더 이상 나눌 필요가 없으므로 정렬이 완료됩니다.

정렬 과정 (피벗을 맨 오른쪽 원소로 선택): [5, 1, 8, 2, 6, 3]

1. 1단계: 피벗은 3. 3보다 작은 [1, 2]는 왼쪽, 큰 [5, 8, 6]은 오른쪽으로 보낸다.
   • 결과: [1, 2] | 3 | [5, 8, 6] (3의 위치는 확정)
2. 2단계 (왼쪽 부분 배열):[1, 2]를 정렬. 피벗은 2. 2보다 작은 1은 왼쪽.
   • 결과: [1] | 2
3. 2단계 (오른쪽 부분 배열):[5, 8, 6]을 정렬. 피벗은 6. 6보다 작은 5는 왼쪽, 큰 8은 오른쪽.
   • 결과: 5 | 6 | 8
4. 최종 결합:[1, 2], 3, [5, 6, 8]을 합쳐 [1, 2, 3, 5, 6, 8] (정렬 완료)

성능 및 특징:

• 시간 복잡도: 평균적으로 O(n log n) 의 매우 빠른 성능을 보입니다. 하지만 최악의 경우, 즉 피벗을 선택할 때마다 계속해서 최소값이나 최대값이 선택되면(예: 이미 정렬된 배열에서 항상 첫 번째 원소를 피벗으로 선택), 분할이 한쪽으로 치우쳐 O(n²) 까지 성능이 저하될 수 있습니다.
• 공간 복잡도:O(log n). 재귀 호출의 깊이만큼 스택 메모리가 필요합니다.
• 안정 정렬 (Stable Sort): No. 분할 과정에서 같은 값의 원소들의 순서가 바뀔 수 있습니다.
• 장점: 평균적으로 매우 빠르며, 추가적인 메모리 공간을 거의 사용하지 않는 인플레이스 정렬입니다.
• 단점: 최악의 경우 성능 저하가 심하며, 이를 피하기 위해 좋은 피벗을 선택하는 것이 중요합니다.

병합 정렬 (Merge Sort)

핵심 아이디어: 일단 쪼개고, 나중에 합치면서 정렬한다

병합 정렬 역시 ‘분할과 정복’에 기반한 알고리즘입니다. 퀵 정렬과 달리, 먼저 배열을 끝까지 쪼갠 후에 ‘병합(Merge)’하는 과정에서 실질적인 정렬이 이루어집니다.

1. 배열의 길이가 1이 될 때까지 계속해서 절반으로 ‘분할’합니다.
2. 길이가 1인 배열은 이미 정렬된 상태로 봅니다.
3. 이제 인접한 두 개의 작은 배열들을 하나로 ‘병합’합니다. 이때 두 배열의 첫 원소부터 비교하여 더 작은 값을 새로운 배열에 순서대로 담습니다. 이 과정을 통해 병합된 배열은 항상 정렬된 상태를 유지합니다.
4. 모든 부분 배열이 하나의 전체 배열로 병합될 때까지 이 과정을 반복합니다.

정렬 과정: [5, 1, 8, 2]

1. 분할:
   • [5, 1] | [8, 2]
   • [5] | [1] | [8] | [2]
2. 병합:
   • [5], [1] → [1, 5]
   • [8], [2] → [2, 8]
   • [1, 5], [2, 8] → [1, 2, 5, 8] (정렬 완료)

성능 및 특징:

• 시간 복잡도: 최선, 평균, 최악 모두 O(n log n) 으로 매우 안정적인 성능을 보장합니다.
• 공간 복잡도:O(n). 병합 과정에서 정렬된 원소를 담을 추가적인 배열이 필요합니다.
• 안정 정렬 (Stable Sort): Yes. 병합 과정에서 같은 값의 원소들의 순서를 유지하도록 구현할 수 있습니다.
• 장점: 데이터의 분포에 상관없이 항상 O(n log n)의 안정적인 성능을 보장합니다.
• 단점: 정렬을 위해 데이터 크기만큼의 추가 메모리(O(n))가 필요하여, 메모리 사용량이 많은 편입니다.

---

마무리: 어떤 정렬을 언제 사용해야 할까?

알고리즘	평균 시간 복잡도	최악 시간 복잡도	공간 복잡도	안정성	특징 및 사용처
거품 정렬	O(n²)	O(n²)	O(1)	Stable	교육용 외에는 거의 사용 안 함
삽입 정렬	O(n²)	O(n²)	O(1)	Stable	데이터가 거의 정렬된 경우 매우 빠름
선택 정렬	O(n²)	O(n²)	O(1)	Unstable	구현이 간단, 교환(swap) 횟수가 적음
퀵 정렬	O(n log n)	O(n²)	O(log n)	Unstable	일반적으로 가장 빠름, 인플레이스 정렬
병합 정렬	O(n log n)	O(n log n)	O(n)	Stable	성능이 매우 안정적, 외부 정렬에 유리

결론적으로, 대부분의 상황에서는 퀵 정렬이 평균적으로 가장 빠른 성능을 보여주므로 최선의 선택이 될 수 있습니다. 하지만 최악의 경우를 반드시 피해야 하는 미션 크리티컬한 시스템이나, 정렬의 안정성이 중요한 경우에는 병합 정렬이 더 나은 대안입니다. 데이터의 크기가 매우 작거나(예: 10개 미만), 이미 거의 정렬된 상태임이 확실하다면 삽입 정렬이 오히려 더 빠르고 효율적일 수 있습니다.

정렬 알고리즘의 세계는 이 5가지 외에도 힙, 셸, 기수 정렬 등 훨씬 더 다양하고 깊이가 있습니다. 하지만 오늘 살펴본 5가지 핵심 알고리즘의 원리와 장단점을 명확히 이해하는 것만으로도, 여러분은 데이터의 특성과 요구사항에 맞춰 가장 적절한 도구를 선택할 수 있는 훌륭한 개발자의 기본기를 갖추게 된 것입니다.