예제로 풀어보는 퀵소트, 리커시브는 덤으로

지난번 퀵소트 속도와 원리 설명에 이어 오늘은 직접 코딩의 세계로 들어가 보려 합니다. 사실 30년 전 제가 처음 코딩을 배울 때는 메모리 하나하나를 아끼느라 재귀 함수를 쓰는 것이 사치처럼 느껴질 때도 있었어요. 스택 오버플로라도 나면 그날은 퇴근을 포기해야 했으니까요. 하지만 지금은 다릅니다. 하드웨어 성능은 비약적으로 발전했고, 이제는 코드의 가독성과 논리적 명확성이 훨씬 중요해졌지요. 그 정점에 있는 것이 바로 재귀입니다. 오늘 이 퀵소트 예제를 통해 여러분의 뇌 구조를 리커시브하게 한 단계 업그레이드해 보시길 바랍니다.

본문1 : 재귀(Recursive), 거울 속의 거울을 들여다보는 용기

재귀 함수라고 하면 일단 겁부터 먹는 후배님들이 많습니다. 함수가 자기 자신을 다시 부른다니, 왠지 끝없는 미로에 빠질 것만 같은 기분이 들죠? 하지만 원리는 아주 단순합니다. 커다란 문제를 도저히 한 번에 해결할 수 없을 때, 그 문제를 동일한 형태의 아주 작은 문제로 쪼개는 거예요. 마치 러시아 인형인 마트료시카를 하나씩 열어가는 과정과 같습니다.

여기서 잠깐 역사 공부를 좀 해볼까요? 이 천재적인 퀵소트 알고리즘을세상에 내놓은 주인공은 영국의 컴퓨터 과학자 토니 호어(Tony Hoare) 경입니다. 1959년 소련 유학 시절, 사전의 단어들을 정렬하기 위해 고안해냈다고 하는데, 그가 만든 이 방식은 수십 년이 지난 지금도 가장 효율적인 정렬 알고리즘 중 하나로 칭송받고 있지요. 단순한 아이디어 하나가 세상을 어떻게 바꾸는지 보여주는 산증인이라 할 수 있습니다.

 

퀵소트에서 재귀가 빛을 발하는 지점이 바로 여기입니다. 전체 배열을 정렬하는 대신, 피벗(Pivot)이라는 기준점을 하나 잡고 그보다 작은 놈들과 큰 놈들로 나눈 뒤, 그 나뉜 덩어리들에게 다시 똑같은 정렬 명령을 내리는 것이죠. 30년 동안 수많은 알고리즘을 봤지만, 이렇게 간결하면서도 강력하게 문제를 해결하는 방식은 드뭅니다. 함수 리턴값으로 혹은 일부로 자기 자신을 콜하는 재귀를 이해한다는 것은 단순히 코딩 기술을 배우는 것을 넘어, 세상을 구조적으로 바라보는 눈을 갖게 되는 것과 같습니다.

본문2: 파이썬으로 짜는 퀵소트, 예술이 되는 코드 한 줄

자, 이제 본격적으로 파이썬 코드를 살펴볼까요? 파이썬은 리스트 컴프리헨션(List Comprehension)이라는 강력한 무기가 있어서 퀵소트를 단 몇 줄 만에 구현할 수 있습니다. 30년 전 C 언어로 포인터를 돌려가며 수십 줄을 짜던 시절에 비하면 이건 정말 축복입니다.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr)//2]
   
    left   = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right  = [x for x in arr if x > pivot]
    
    return quicksort(left) + middle + quicksort(right)


# 메인 테스트
if __name__ == "__main__":
    arr = [5, 3, 8, 4, 2, 7, 1, 6]
    
    result = quicksort(arr)
    print(result)

 

코드의 맨 위에서 함수 정의를 하고 나먼 먼저 기저 조건(Base Case)을 정해야 합니다. 재귀에서 가장 중요한 건 언제 멈출지를 정하는 거예요. 리스트의 길이가 1보다 작거나 같으면 이미 정렬된 것이니 그대로 돌려주면 됩니다.

그리고 기준점인 피벗을 선택합니다. 사실 퀵소트의 성패는 코딩 실력보다도 피벗(Pivot)을 얼마나 영리하게 잡느냐에 달려 있다고 해도 과언이 아닙니다. 만약 정렬이 거의 다 된 데이터에서 하필이면 가장 작거나 가장 큰 값을 피벗으로 계속 잡게 되면, 퀵소트는 이름과 달리 거북이처럼 느려지는 최악의 시나리오를 마주하게 되거든요. 30년 현장에서 배운 팁을 드리자면, 데이터의 첫 번째와 마지막 그리고 중간 값 중에서 중간에 해당하는 값을 피벗으로 정하는 이른바 미디언 오브 쓰리(Median-of-Three) 방식을 추천합니다. 이렇게 하면 데이터가 편향되어 있을 때 발생할 수 있는 비효율을 획기적으로 줄일 수 있고, 시스템의 안정성도 훨씬 높아집니다. 피벗 하나에 따라 알고리즘이 예술이 될 수도, 재앙이 될 수도 있다는 사실을 꼭 기억하며 신중하게 선택하시길 바랍니다.

퀵소트 피보팅을 할 때 보통 맨 앞이나 중간값을 잡는다고 다들 이야기하는데 생각해보면 문제가 생기는 구간은 항상 관습처럼 "보통 그렇게 하면 돼.. 여태까지 그렇게 해왔어." 이런 것들에 대해서 깊이 생각하지 않고 따라서 하게 되면 그 부분이 언젠가는 문제로 돌아왔던 경험이 참 많습니다. 여기 예제에서는 데이터가 홀수일 경우에는 가운데 수, 짝수일 경우에는 가운데보다 하나 뒤에 수를 선정하는 알고리즘으로 택했지만 실제에서는 입력되는 데이터를 잘 검토한 후에 결정하는 것이 좋습니다. 정말 강조하소 싶은 것은 입력되는 데이터가 어떤 특성을 갖는 데이터인지 항상 먼저 검토하는 습관을 가져야 합니다

그다음이 마법의 구간입니다. 리스트 컴프리헨션을 써서 피벗보다 작은 값들을 모은 리스트, 피벗과 같은 값들의 리스트, 그리고 큰 값들의 리스트로 나눕니다. 그리고 작은 리스트와 큰 리스트에 다시 퀵소트 함수를 적용한 뒤 이들을 합치기만 하면 끝입니다. 정말 명쾌하지 않나요? 이 짧은 코드 안에 분할, 정복, 결합이라는 알고리즘의 3요소가 완벽하게 녹아들어 있습니다.

배열을 가지고 피벗을 잡고 파티션하는 과정을 끝까지 따라가보는 건 정말 효과적입니다. 처음에는 피벗을 마지막 원소로 잡고 분할하다 보면, 각 재귀 단계에서 left, middle, right가 어떻게 만들어지는지 눈에 들어옵니다.

특히 middle 리스트는 피벗과 같은 값을 모으는 역할을 하는데, 중복 데이터가 많을수록 그 존재감이 커집니다. 파이썬을 접하면서 저도 리스트 컴프리헨션을 처음 봤을 때 헷갈렸어요. left = [x for x in arr if x < pivot] 이 한 줄이 사실은 새로운 리스트를 만들면서 append처럼 오른쪽으로 값을 쌓는다는 걸 외우고 이해하니까 명확해졌습니다. 기존 리스트를 건드리지 않고 새로 만드는 점이 중요하죠. 이런 작은 부분을 하나씩 확인하다 보면 알고리즘이 손에 익습니다. 각 Array를 손으로 그리면서 꼭 한번 따라가 보시기 바랍니다.

본문3: 현장의 짬바, 재귀를 쓸 때 반드시 기억할 한 가지

30년 차 개발자로서 뼈 아픈 조언을 하나 하자면, 재귀는 반드시 탈출구가 명확해야 합니다. 현업에서 가끔 재귀 호출의 깊이가 너무 깊어져서 시스템이 멈추는 대형 사고를 목격하곤 합니다. 파이썬은 기본적으로 재귀 호출의 횟수를 제한하고 있기도 하죠.

실제 대규모 데이터를 다룰 때는 이 퀵소트가 최악의 경우(이미 정렬된 데이터에 피벗을 잘못 잡을 때 등)에 성능이 급격히 떨어질 수 있다는 점을 인지해야 합니다. 그래서 베테랑들은 피벗을 랜덤하게 잡거나, 데이터가 일정 수준 이하로 작아지면 삽입 정렬 같은 다른 방식으로 전환하는 하이브리드 전략을 쓰기도 합니다. 이론은 완벽할지라도 현실의 데이터는 지저분할 수 있다는 점, 그 지저분함을 고려하는 것이 바로 연륜에서 나오는 실력입니다. 여러분도 코드가 예쁘다고 취해 있지 말고, 항상 예외적인 상황을 시뮬레이션하는 습관을 들이세요.

마무리

오늘은 퀵소트와 재귀의 세계를 파이썬이라는 도구로 설명해 보았습니다. 복잡해 보이던 정렬도 잘게 쪼개어 보니 별것 아니라는 생각이 드시나요? 인생도 마찬가지입니다. 눈앞에 놓인 거대한 프로젝트나 커리어의 고민도, 오늘 하루 우리가 해야 할 작은 일들로 재귀적으로 나누어 해결하다 보면 어느새 멋진 결과에 도달해 있을 겁니다.

무엇보다 중요한 건 멈추지 않는 것입니다. 에러 메시지가 여러분을 괴롭혀도, 그 속에 답이 있다는 믿음을 가지세요. 저도 30년째 에러와 싸우고 있지만, 그 싸움이 즐겁기에 이 자리를 지키고 있으니까요. 다들 즐거운 코딩 하세요!