Quick sort, Quick? 정말 빠른 정렬 알고리즘은?

이 바닥에서 키보드 좀 두드려본 옆집 올디버거 입니다. 요즘 인공지능이 코드를 대신 짜주니 뭐니 해도 결국 우리가 마주하는 본질은 데이터의 나열입니다. 언제였던가 괜히 점심 메뉴 고르느라 한참을 고민했는데, 알고 보니 그것도 내 머릿속에서 선호도 순으로 정렬을 하고 있더라고요.

신입 시절에는 무조건 퀵 정렬(Quick Sort)이 제일 빠른 줄 알고 모든 코드에 억지로 집어넣다가 서버가 뻗었던 기억이 납니다. 오늘은 그 짬바에서 나오는 진짜 정렬 이야기를 해볼까 해요. 이론적인 이야기보다는 제가 겪은 현장의 냄새를 듬뿍 담아봤습니다.

첫 번째 이야기: 퀵 정렬은 정말 퀵할까? (피벗의 배신)

제가 90년대 중반에 서브 프로젝트로 한 수치 계산 프로그램 일을 맡았을 때 일입니다. 당시에는 지금처럼 라이브러리가 풍족하지 않아서 정렬 함수 하나도 손수 깎아 만들던 시절이었죠. 저는 자부심 넘치는 젊은 피였고, 당연히 성능이 가장 좋다는 퀵 정렬을 선택했습니다.

이론적으로 퀵 정렬은 평균 속도가 가장 빠릅니다. 하지만 함정이 하나 있죠. 바로 기준점인 피벗(Pivot)을 어떻게 잡느냐에 따라 운명이 결정된다는 겁니다. 제가 짠 코드에 하필이면 이미 거의 정렬된 데이터가 들어왔는데, 피벗 선택 로직이 엉망이었던 바람에 시간 복잡도가 제곱으로 치솟아 버렸습니다. 속도가 이상하게 너무 느려졌고 제 등에서는 식은땀이 비 오듯 흘렀죠. 그때 깨달았습니다.  아무리 빠른 퀵 소트라도 상황에 따라서는 가장 느린 거북이가 될 수 있다는 사실, 초보 개발자들이 가장 많이 하는 실수 중 하나입니다.

Quick sort illustration, 얼마나 빨리 정렬할 수 있나 이것이 항상 우리에게 중요합니다

포트란에서 공식적으로 재귀(Recursive) 호출을 지원하기 시작한 것은 포트란 90(Fortran 90)부터 입니다. 그전 표준인 포트란 77 시절에는 함수나 서브루틴이 자기 자신을 호출하는 것이 표준상 금지되어 있었거든요. 당시에는 변수들이 메모리에 고정된 위치를 차지하는 '스태틱(Static)' 방식이 기본이라, 재귀 호출을 하면 이전 호출의 데이터가 덮어씌워지는 대참사가 벌어지곤 했습니다.

하지만 1991년에 발표된 포트란 90에서 RECURSIVE라는 키워드가 도입되면서 상황이 완전히 달라졌죠. 이제는 함수 앞에 이 키워드를 붙여주기만 하면 컴퓨터가 알아서 스택 메모리를 사용해 이전 기록을 보관해주니, 팩토리얼이나 피보나치 수열 같은 복잡한 알고리즘도 아주 세련되게 짤 수 있게 되었습니다. 30년 전 선배들이 재귀를 구현하려고 함수 복사본을 수십 개씩 만들거나 스택을 직접 코딩하던 눈물겨운 삽질이 비로소 마침표를 찍은 순간이라고 할 수 있겠네요. 지금은 누구나 아무렇지도 않게 쓰는 재귀호출을 쓰지만 그때는 정말 조심하고 어렵게 구현해야 했었지요.

두 번째 이야기: 최악의 상황은 공평하지 못한 대장(피벗)의 탄생

퀵소트의 핵심은 대장(피벗)을 하나 뽑아서 그보다 작은 애들은 왼쪽, 큰 애들은 오른쪽으로 나누는 분할 정복에 있습니다. 가장 이상적인 건 대장이 딱 중간값을 뽑아서 동네를 반반으로 딱딱 나누는 거예요. 그래야 작업량이 매번 절반씩 뚝뚝 떨어지니까요.

그런데 이미 정렬이 된 데이터(예: 1, 2, 3, 4, 5)에서 맨 앞의 숫자 1을 피벗으로 잡으면 어떻게 될까요?

1. 1단계: 1이 대장이 됩니다. 1보다 작은 건 없으니 왼쪽은 비어있고, 나머지는 다 오른쪽으로 갑니다. (나머지: 2, 3, 4, 5)
2. 2단계: 남은 애들 중 2가 대장이 됩니다. 역시 왼쪽은 비고 나머지는 다 오른쪽. (나머지: 3, 4, 5)
3. 3단계: 3이 대장이 됩니다. (나머지: 4, 5)

느껴지시나요? 이건 반으로 나누는 게 아니라, 양파 껍질을 한 겹씩 까는 모양새가 되어버립니다. 원래 퀵소트는 이분 탐색처럼 뭉텅이로 일을 처리해야 하는데, 피벗을 잘못 잡으면 그냥 하나씩 하나씩 비교하는 노가다로 전락해 버리는 거죠.

세 번째 이야기: 왜 느려지는 걸까? (피라미드 vs 절벽)

 수학적으로 보면 더 명확합니다.

1.  좋을 때: $O(n \log n)$ – 데이터를 반씩 쪼개니까 층수가 낮습니다.
2. 운 나쁠 때: $O(n^2)$ – 데이터 개수만큼 층이 생깁니다. 10만 개 데이터를 정렬하는데 10만 층짜리 계단을 하나씩 내려간다고 생각해보세요. 서버가 비명을 지르는 게 당연하죠. 

실제로 정렬이 이미 되어 있거나 역순으로 정렬된 데이터에서 맨 앞이나 맨 뒤를 피벗으로 잡는 로직은 최악의 악수입니다. 현장에서는 이걸 방지하기 위해 세 가지 값 중 중간값을 피벗으로 잡거나(Median-of-Three), 아예 무작위로 피벗을 고르는 방식을 써서 이런 낭패를 피하곤 한답니다.

네 번째 이야기: 얼나마 느려질까?  빅 오

우리가 물건을 살 때 가성비를 따지듯, 컴퓨터 공학에서는 시간 복잡도라는 것으로 알고리즘의 가성비를 측정합니다. $O$ 라는 기호는 빅 오(Big-O)라고 부르는데, 데이터가 늘어날 때 계산 시간이 얼마나 늘어나는지를 나타내는 척도예요.

그중에서도 $O(n\log n)$  은 소위 말하는 준수한 모범생의 성적표라고 보시면 됩니다. 아주 단순한 방식보다는 훨씬 빠르고, 현실적으로 대용량 데이터를 처리할 수 있는 마지노선 같은 존재죠.

1. $n$  (선형 시간): 데이터 10만 개를 하나하나 다 훑는 노가다입니다. 1번부터 10만 번까지 묵묵히 걷는 거죠.
2. $\log n$  (로그 시간): 이건 아주 영리한 방식입니다. 10만 개의 데이터가 있어도 반씩 뚝뚝 자르면서 찾아가면 단 20번 만에 원하는 걸 찾을 수 있어요. 이분 탐색(Binary Search)이 바로 이 방식이죠.
3. $n^2$  이라면? 100,000의 제곱이니 무려 100억 번을 연산해야 합니다.
4. $n \log n$  이라면? 100,000 곱하기 약 17(로그값)을 해서 170만 번 정도면 끝납니다.

예를 들어 퀵 정렬이나 병합 정렬을 생각해보세요. 전체 데이터를 반으로 쪼개고( $\log n$), 그 과정을 전체 데이터 개수($>n$)에 맞춰서 조립해 나가는 식이죠. 노가다와 천재적인 발상이 곱해진 아주 효율적인 조합이라고 할 수 있습니다. 100억 번과 170만 번의 차이, 느껴지시나요? 전자는 점심 먹고 와도 안 끝나지만, 후자는 눈 깜빡할 사이에 끝납니다. 이래서 우리가 효율적인 알고리즘을 공부하는 거예요. $n\log n$ 은 우리가 대규모 서비스를 운영할 수 있게 해주는 마법의 숫자입니다.

오늘 정렬과 복잡도라는 거대한 산을 저와 함께 살짝 넘으셨는데 기분이 어떠신가요? 30년 동안 수많은 버그와 싸우며 제가 깨달은 건, 결국 좋은 개발자란 가장 어려운 알고리즘을 달달 외우는 사람이 아니라 상황에 맞는 가장 현명한 도구를 고를 줄 아는 사람이라는 점입니다. $O(n\log n)$ 이라는 숫자 뒤에 숨겨진 효율성의 미학을 이해하셨다면, 여러분은 이미 단순한 코더를 넘어 엔지니어의 길로 들어선 셈이에요. 기술은 매일같이 변하지만 이런 근본적인 원리는 세월이 흘러도 변하지 않는 든든한 무기가 되어줄 겁니다. 오늘 배운 내용을 밑거름 삼아 여러분의 코드가 세상이라는 넓은 데이터 바다에서 가장 빠르고 안정적으로 돌아가길 이 선배가 진심으로 응원하겠습니다. 다음에 더 진한 Qucik Sort 샘플 현장의 이야기로 또 만나요!

참고사항

1. 시간 복잡도 비교: $n=1,000,000$ 일 때, $n \log n \approx 2 \times 10^7$ 수준이며, $n^2 = 10^{12}$ 로 비교 불가능할 만큼의 차이가 발생함.
2. 비교 정렬의 하한: 비교 기반 정렬 알고리즘(Comparison-based sorting)의 이론적 하한선은 $\Omega(n \log n)$ 임이 수학적으로 증명됨.
3. 실질적 성능: 실제 실행 시에는 상수항(Constant factor)에 따라 $O(n \log n)$  알고리즘 간에도 성능 차이가 존재하며, Timsort 등이 이를 최적화함.