좋은 정렬, 나쁜 정렬, 이상한 정렬
서론
세상은 정말로 또 다른 '정렬 알고리즘 설명' 블로그 글을 필요로 할까요?
한편으로는 확실히 그렇습니다. 왜냐하면 정렬 알고리즘은 이미 너무 많이 설명되었기 때문에, 오히려 제대로 설명된 적이 거의 없기 때문입니다. 버블 정렬은 “느리고”, 퀵 정렬은 “빠르며”, 병합 정렬은 “안정적”이라는 문장은 수천 번 반복되었지만, 그 문장을 처음 들었을 때 독자의 머릿속에서 실제로 무슨 일이 일어나는지는 아무도 신경 쓰지 않았습니다. 마치 “비타민 C는 감기에 좋다”는 말을 들은 사람이 비타민이 무엇인지, 정확히 어떤 감기를 말하는지, ‘좋다’는 것이 통계적으로 어떤 의미인지는 모른 채 고개만 끄덕이는 것과 비슷합니다.
정렬 알고리즘을 이해한다는 것은 코드를 외우는 일이 아닙니다. 그것은 직관을 하나 얻는 일에 가깝습니다. 비교라는 행위의 비용이 어디서 발생하는지, 기억 공간을 조금 더 쓰는 대신 시간을 절약하는 선택이 언제 합리적인지, 그리고 “평균적으로 빠르다”는 말이 최악의 경우를 만났을 때 어떤 기분이 되는지를 상상해보는 연습입니다. 이는 이 모든 생각을 생략하고 그저 표준 라이브러리의 sort()를 사용할 때조차도 여전히 유용한 훈련입니다.
그래서 이 글은 또 하나의 정렬 알고리즘 설명이지만, 동시에 그 이상을 의도합니다. 여기서는 가능한 한 적은 수식으로, 가능한 한 많은 직관을 얻는 것을 목표로 합니다. 이미 알고 있다고 생각했던 알고리즘들이 사실은 전혀 다른 성격을 가지고 있다는 점, 그리고 그 차이가 현실 세계의 문제 선택에 어떻게 영향을 미치는지를 차분히 살펴볼 것입니다. 또한 표준 라이브러리의 sort()에 대해서도 알아볼 것입니다.
나쁜 정렬
버블 정렬:무엇이 문제인가
버블 정렬은 가장 널리 알려진 정렬 알고리즘 중 하나이지만, 동시에 가장 자주 오해되는 알고리즘이기도 합니다. 먼저 정의부터 정확히 짚고 가겠습니다.
버블 정렬은 배열을 앞에서부터 훑으면서 서로 이웃한 두 원소를 비교하고, 순서가 잘못되어 있으면 교환하는 일을 반복합니다. 한 번 배열을 끝까지 훑고 나면, 가장 큰 원소 하나가 마치 물속의 기포처럼 맨 뒤로 떠오릅니다. 이 과정을 다시 처음부터 반복하며, 더 이상 교환이 일어나지 않을 때 정렬이 끝났다고 판단합니다.
이 설명에서 중요한 점은 두 가지입니다.
첫째, 버블 정렬은 인접한 원소만 교환할 수 있습니다.
둘째, 한 번의 전체 순회(pass)로 확실히 제자리를 찾는 원소는 많아야 하나(보통은 최댓값 하나)입니다.
이 구조가 바로 버블 정렬의 본질적인 한계입니다.
인접 교환만 허용된다는 말은, 어떤 원소가 자기 자리에 가기 위해 멀리 이동해야 한다면 그만큼 여러 번의 비교와 교환을 거쳐야 한다는 뜻입니다. 예를 들어, 배열의 맨 앞에 있는 최댓값은 단 한 번의 실수로 끝까지 순간 이동하지 않습니다. 대신 옆 원소와 한 칸씩 싸우며, 묵묵히 뒤로 밀려나야 합니다. 이 “한 칸씩 이동”이라는 제약이 누적되면서 비용이 폭발합니다.
또한 버블 정렬은 구조적으로 전체 배열을 여러 번 반복해서 훑는 방식을 취합니다. 구현에 따라 다르지만, 보통은 길이가 n인 배열에 대해 최대 n−1번의 패스를 수행하며, 각 패스마다 최대 n번의 비교가 일어납니다. 이 때문에 평균적인 시간 복잡도는 O(n^2)입니다.
물론 예외는 있습니다. 배열이 이미 정렬되어 있다면, “이번 패스에서 아무 교환도 일어나지 않았다”는 사실을 감지하고 즉시 종료할 수 있습니다. 이 최선의 경우, 버블 정렬은 O(n)에 가깝게 동작합니다. 하지만 이 최선의 경우는 입력 데이터가 거의 완벽하게 정렬되어 있어야만 등장하며, 조금만 어긋나도 곧바로 n^2의 세계로 돌아옵니다.
정리하면, 버블 정렬의 문제는 단순히 “느리다”는 데 있지 않습니다. 더 정확히 말하면, 느릴 수밖에 없는 제약을 스스로에게 부과하고 있다는 점이 문제입니다.
- 원소는 인접한 위치로만 이동할 수 있고
- 한 번의 패스로 얻는 진전은 매우 제한적이며
- 이미 더 나은 정보(어느 값이 어디쯤 있어야 하는지)를 활용하지 않습니다.
이 모든 선택은 구현을 단순하게 만들어 주지만, 그 대가로 시간이라는 자원을 가차 없이 소비합니다.
그래서 버블 정렬은 실무에서 “나쁜 정렬”로 분류됩니다. 다만 그 “나쁨”은 무능에서 오는 것이 아니라, 의도적으로 모든 영리한 전략을 포기했을 때 어떤 일이 벌어지는지를 보여주는 데서 옵니다. 이 점에서 버블 정렬은 하나의 실패작이기보다는, 다음 질문을 던지기 위한 출발점에 가깝습니다.
“만약 원소를 한 칸씩 옮기는 대신, 더 멀리 보내줄 수 있다면?”
“한 번의 작업으로 둘 이상의 원소를 제자리로 보낼 수 있다면?”
이 질문들에 대한 답이 바로, 이후에 등장하는 더 나은 정렬 알고리즘들입니다.
좋은 정렬
퀵 정렬:별로 퀵한 정렬이 아니다
붙여진 이름이 적절한 경우가 있고, 이름만으로 판단해서는 안 되는 경우가 있습니다. 퀵 정렬은 그 중간쯤의 존재입니다.
왜냐하면 퀵 정렬이 대부분의 경우에는 정말로 빠르기 때문입니다. 다만 그 “대부분”이란 단어가 문제를 일으킵니다. 사람들은 대개 이름이 약속하는 바를 항상 해내는 물건을 원하고, 알고리즘 이름에 그런 기대를 걸어버리는 순간부터 슬금슬금 비극이 시작됩니다.
퀵 정렬은 기본적으로 “적당히 똑똑한 분할”의 알고리즘입니다. 배열에서 원소 하나를 골라(이를 피벗이라고 부릅니다.), 그 피벗보다 작은 값들을 왼쪽, 큰 값들을 오른쪽으로 밀어 넣습니다. 그러고 나면 피벗은 “자기가 있어야 할 위치” 근처에 놓이게 되고, 왼쪽 덩어리와 오른쪽 덩어리에 대해 같은 일을 반복합니다. 이런 방식은 정교한 전체 계획을 세우지 않으면서도, 결과적으로는 꽤 훌륭한 정렬을 만들어냅니다.
여기서 중요한 건 “피벗을 어떻게 고르느냐”입니다. 피벗이 운 좋게 중앙값 근처라면, 한 번 분할할 때마다 문제 크기가 반으로 줄어드는 느낌이 나고, 그래서 평균적으로는 O(n log n)이라는, 알고리즘 세계에서 사실상 “세련된 빠름”으로 취급받는 성능을 얻습니다. 하지만 피벗이 계속해서 최솟값이나 최댓값처럼 한쪽 끝에 걸리면, 분할이 아니라 거의 “한 칸씩 밀기”가 되어버리고, 그 순간 퀵 정렬은 O(n^2)라는 낯익은 지옥의 표정을 드러냅니다.
그럼에도 불구하고 퀵 정렬이 사랑받는 이유가 있습니다. 첫째, 구현이 단순하고, (잘 구현하면) 추가 메모리를 거의 쓰지 않는 제자리(in-place) 정렬이라는 점. 둘째, 실제 컴퓨터에서는 “빅-오 표기”가 말해주지 않는 것들이 많은데, 퀵 정렬은 메모리를 이리저리 뛰어다니지 않고 배열을 연속적으로 훑는 일이 많아서 캐시 친화적인 편입니다. 현실은 수학보다 덜 우아하지만 더 집요해서, 이 ‘캐시’라는 녀석이 체감 속도를 좌우하는 경우가 흔합니다. 이 때문에 퀵 정렬은 이론적으로는 다른 정렬과 동급이거나 열등해 보이는데도, 벤치마크에서는 종종 “아니 왜 이렇게 빠르지?” 같은 얼굴을 합니다.
하지만 여기까지가 “퀵 정렬이 퀵한 날” 이야기입니다. 문제는 퀵 정렬이 피봇을 올바르게 잡지 못하면 갑자기 느려질 수 있다는 점이고, 이게 사람들을 불안하게 만듭니다. 특히 정렬이 “언제나 빠를 것”이라고 가정해버린 코드가 세상에 충분히 많다는 점을 생각하면, 최악의 경우가 단지 교과서 속 각주가 아니라 실제 장애 보고서의 본문으로 올라오는 순간이 생깁니다.
여기서 우리는 이름의 문제로 돌아옵니다. 퀵 정렬은 빠른가? 네, 평균적으로는 빠릅니다. 그러나 “퀵”이라는 단어가 약속하는 것은 평균이 아니라 보통 사람의 마음속에 있는 상시성입니다. 그리고 퀵 정렬은 그 상시성을 제공하지 않습니다. 그 대신, 현실적인 성능(캐시, 상수항, 구현 난이도, 메모리 사용량)을 뭉뚱그린 “실전에서 자주 이긴다”라는 종류의 강함을 제공합니다.
이쯤에서, 초보자들이 흔히 던지는 질문이 있습니다. “그럼 퀵 정렬은 쓰지 말아야 하나요?” 이 질문은 대체로 “그럼 사람은 살지 말아야 하나요?” 같은 질문과 비슷합니다. ‘최악의 경우’라는 말을 듣는 순간, 우리는 그 최악이 내일 당장 나를 찾아올 것처럼 느끼지만, 실제로는 입력 데이터의 분포, 피벗 선택 전략, 구현의 세부 사항, 그리고 무엇보다 “정렬이 정말 병목인가?” 같은 질문들이 먼저입니다. 즉, 퀵 정렬을 판단하는 올바른 방법은 이름이 아니라 맥락입니다. (그리고 맥락은 늘 귀찮습니다. 그래서 사람들은 이름을 좋아하죠.)
팀 정렬:상아탑 바깥의 정렬
그런데 이론이 뭐 어쨌다는 겁니까? 우리는 우아한 이론보다 실제 속도에 신경써야 하지 않을까요?
팀 정렬(Timsort)은 이 질문에 대한, 드물게도 성실한 대답입니다. “이론적으로는 이렇고, 실제로는 저렇다”라는 말을 수십 년간 반복해 온 알고리즘 연구자들과 시스템 프로그래머들이, 마침내 “그럼 실제를 기준으로 알고리즘을 설계해 보자”라고 결심한 결과물에 가깝습니다.
팀 정렬의 출발점은 단순합니다. 현실의 데이터는 무작위가 아니라는 관찰입니다. 우리가 정렬하는 데이터는 대개 이미 어느 정도 정렬되어 있습니다. 로그 파일은 시간순에 가깝고, 사용자 목록은 이전 정렬 결과의 약간의 수정판이며, 화면에 표시되는 데이터는 “조금만 바뀐 상태”로 다시 정렬되는 경우가 많습니다. 그런데도 우리는 오랫동안 “최악의 경우”와 “무작위 입력”을 기준으로 알고리즘을 평가해 왔습니다. 팀 정렬은 이 관행을 정면으로 의심합니다.
팀 정렬은 병합 정렬(merge sort)을 기반으로 하지만, 그대로 쓰지 않습니다. 대신 배열을 처음부터 훑으면서 이미 정렬되어 있거나 거의 정렬된 구간을 찾아냅니다. 이 구간들을 런(run)이라고 부릅니다. 중요한 점은, 이 런들이 우연히 생긴 노이즈가 아니라 현실 데이터의 기본 상태라는 가정입니다. 팀 정렬은 “데이터가 이미 어느 정도 정렬되어 있다면, 그 사실을 적극적으로 이용하겠다”는 태도를 취합니다.
발견된 런이 너무 짧으면, 삽입 정렬로 적당한 길이까지 확장합니다. 삽입 정렬은 이론적으로는 느리지만, 짧고 거의 정렬된 배열에서는 매우 빠릅니다. 이후 팀 정렬은 이 런들을 특정 규칙에 따라 병합합니다. 이 규칙은 단순히 “왼쪽부터 합친다”가 아니라, 병합 비용이 폭증하지 않도록 런의 크기 관계를 관리하는 일종의 불변식(invariant)을 유지합니다. 이 부분은 설명만 들으면 과하게 복잡해 보이지만, 요지는 하나입니다. 병합 정렬의 최악 성능을 피하면서, 현실 데이터의 구조를 최대한 보존한다는 것입니다.
이 결과로 팀 정렬은 흥미로운 성질을 갖습니다.
- 최악의 경우 시간 복잡도는 O(n log n)으로 보장됩니다.
- 이미 정렬된 경우에는 O(n)에 가깝게 동작합니다.
- 안정 정렬이며, 실제 환경에서 매우 빠릅니다.
이쯤 되면 팀 정렬은 거의 “치트 코드”처럼 보입니다. 실제로도 그렇습니다. 파이썬, 자바(객체 배열), 스위프트 등 여러 언어의 표준 정렬은 팀 정렬 또는 그 변형을 사용합니다. 여기에는 어떤 미묘한 태도 변화가 담겨 있습니다. “프로그래머가 최악의 경우를 모두 통제할 수 있다”는 가정에서 벗어나, “현실에서 자주 일어나는 경우를 최대한 잘 처리하자”는 방향으로 이동한 것입니다.
물론 팀 정렬에도 대가가 있습니다. 구현은 복잡하고, 코드 길이는 퀵 정렬이나 병합 정렬보다 훨씬 깁니다. 머릿속에서 전체 동작을 한 번에 이해하기도 어렵습니다. 이는 팀 정렬이 알고리즘 수업에서 종종 뒷부분에 짧게 언급되거나, 아예 생략되는 이유이기도 합니다. 설명하기 어렵고, 칠판에 적기 불편하며, “깔끔한 수식 하나”로 요약되지 않기 때문입니다.
하지만 이 점이 바로 팀 정렬의 성격을 드러냅니다. 팀 정렬은 이론을 무시하지 않지만, 이론을 신성시하지도 않습니다. 최악의 경우 분석은 유지하되, 설계의 중심에는 실제 데이터와 실제 하드웨어가 놓여 있습니다. 이는 “아는 것”과 “실천하는 것”의 차이를 보여주는 전형적인 사례입니다. 우리는 오래전부터 “삽입 정렬은 거의 정렬된 데이터에서 빠르다”는 사실을 알고 있었고, “병합 정렬은 안정적이다”라는 것도 알고 있었습니다. 팀 정렬은 그 지식을 그냥 알고 있는 데서 멈추지 않고, 실제 코드로 밀어 넣었습니다.
그래서 팀 정렬은 어떤 면에서 알고리즘이라기보다 태도에 가깝습니다.
“현실은 생각보다 질서정연하다.”
“그 질서를 무시하지 말고 활용하라.”
그리고 아마도 가장 중요한 교훈은 이것입니다. 알고리즘의 품질은 수식의 아름다움보다, 우리가 실제로 무엇을 정렬하는가에 더 크게 좌우된다는 사실 말입니다.
이상한 정렬
기수 정렬:비교보다 빠르게
연구자들은 데이터끼리 비교하며 정렬할 경우 시간 복잡도가 O(n log n)보다 작을 수 없다는 것을 알아냈습니다. 그렇다면 비교를 안 하면 어떨까요?
이 질문은 알고리즘 이론에서 보기 드물게 생산적인 반항입니다. “한계를 증명했다”는 말은 보통 대화를 끝내는 문장인데, 여기서는 오히려 새로운 대화를 시작합니다. 비교 정렬에 한계가 있다면, 그 한계 바깥으로 나가면 됩니다. 기수 정렬(Radix sort)은 그렇게 태어났습니다.
기수 정렬의 핵심 발상은 간단합니다. 원소 전체를 서로 비교하지 말고, 자릿수(digit) 단위로 분해해서 처리하자는 것입니다. 숫자를 예로 들면, 329와 457 중 무엇이 큰지 묻지 않습니다. 대신 “일의 자리”, “십의 자리”, “백의 자리”를 차례로 보며 정렬합니다. 이 과정에서 필요한 것은 비교 연산이 아니라, “이 자릿값이 무엇인가?”라는 분류 작업입니다.
보통의 구현은 다음과 같습니다. 가장 낮은 자릿수부터 시작해, 각 자릿값에 대해 안정 정렬을 수행합니다. 일의 자리로 한 번, 십의 자리로 한 번, 이런 식으로 자릿수의 수만큼 반복합니다. 각 단계는 선형 시간에 가능하고, 전체 시간 복잡도는 대략 O(d·n)입니다. 여기서 d는 자릿수의 개수입니다. d가 작고 고정되어 있다면, 기수 정렬은 사실상 O(n)처럼 보입니다.
이 지점에서 기수 정렬은 매우 매력적인 제안을 합니다.
- 비교를 하지 않는다.
- 최악의 경우에도 성능이 안정적이다.
- 이론적으로 n log n의 장벽을 넘는다.
그래서 종종 “기수 정렬이 가장 빠른 정렬 아닌가?”라는 질문이 나옵니다. 이 질문이 흥미로운 이유는, 답이 항상 “아니오”이기 때문입니다. 그리고 그 이유는 기수 정렬이 공짜 점심을 제공하지 않기 때문입니다.
기수 정렬은 비교를 포기하는 대신, 강한 가정을 요구합니다. 데이터가 정수이거나, 고정 길이 문자열이거나, 최소한 “자릿수로 쪼갤 수 있는 구조”를 가져야 합니다. 또한 자릿수의 범위가 제한되어 있어야 합니다. 예를 들어 32비트 정수라면 자릿수는 32비트로 고정되어 있지만, 임의 정밀도 정수나 길이가 제각각인 문자열로 가면 이야기가 달라집니다. d는 더 이상 작은 상수가 아니고, 그 순간 O(d·n)는 O(n log n)보다 나아 보이지 않습니다.
또 하나의 비용은 메모리입니다. 기수 정렬은 보통 계수 정렬(counting sort) 같은 보조 정렬을 내부에서 사용하고, 이는 추가 메모리를 요구합니다. 비교 정렬에서 흔히 볼 수 있는 “제자리 정렬”의 장점을 포기하는 셈입니다. 이론적으로는 빠르지만, 실제 시스템에서는 캐시, 메모리 대역폭, 할당 비용 같은 현실적인 요소들이 속도를 갉아먹습니다.
이쯤에서 기수 정렬의 성격이 드러납니다. 기수 정렬은 범용 정렬이 아닙니다. 대신 문제가 잘 정의된 영역에서는 매우 강력한 특수 도구입니다. 네트워크 패킷의 키, 고정 길이 ID, 날짜와 시간, 비트열처럼 구조가 명확한 데이터에서는 기수 정렬이 비교 정렬을 압도하는 경우가 많습니다. 반대로 “아무 타입이나 받아서 정렬해야 한다”는 표준 라이브러리의 요구에는 잘 맞지 않습니다. 그래서 기수 정렬은 흥미롭게도 교과서에서는 “이론적 예외”처럼 소개되지만, 실제 산업 현장에서는 조용히, 그러나 꾸준히 사용됩니다.
보고 정렬:그리고 이를 위한 변호
보고 정렬은 정렬될 때까지 배열 안의 원소들을 무작위로 섞는 “정렬” 알고리즘입니다. 어리석다고요? 맞습니다. 하지만 재밌죠.
보고 정렬(Bogosort)은 보통 농담으로 소개됩니다. “알고리즘의 안티테제”, “컴퓨터 과학이 스스로를 패러디한 결과물”, 혹은 “무한한 원숭이 정렬 이론의 실습 버전”. 대부분의 설명은 여기서 멈춥니다. 웃고 넘어가기에 충분하기 때문입니다. 하지만 보고 정렬이 계속해서 교과서와 블로그에 등장한다는 사실은, 이 알고리즘이 단순한 농담 이상이라는 점을 암시합니다.
보고 정렬의 정의는 놀라울 정도로 정직합니다.
- 배열이 정렬되었는지 확인한다.
- 정렬되어 있지 않다면, 배열을 무작위로 섞는다.
- 다시 1번으로 돌아간다.
끝입니다. 분할도 없고, 병합도 없고, 피벗도 없습니다. 유일한 판단은 “이미 정렬되었는가?”라는 질문 하나뿐입니다. 그리고 그 질문에 “아니오”라는 답이 나오는 한, 보고 정렬은 계속해서 셔플 버튼을 누릅니다.
시간 복잡도를 묻는 순간, 대화는 불편해집니다. 평균 시간 복잡도는 O(n · n!) 정도로 이야기되며, 최악의 경우는 사실상 정의할 수 없습니다. “언젠가는 끝난다”는 말조차 확률적인 의미에서만 참입니다. 이쯤 되면 보고 정렬은 알고리즘이라기보다 실험입니다. 그리고 대부분의 실험이 그렇듯, 실용성은 거의 없습니다.
그런데도 보고 정렬은 묘하게 방어할 구석이 있습니다.
첫째, 개념적으로 가장 단순한 정렬입니다. 정렬의 정의를 “모든 가능한 순열 중에서 정렬된 상태를 찾는 것”이라고 한다면, 보고 정렬은 그 정의를 가장 직접적으로 구현합니다. 다른 정렬 알고리즘들이 온갖 휴리스틱과 구조적 가정을 덧붙이는 동안, 보고 정렬은 아무것도 가정하지 않습니다. 이 점에서 보고 정렬은 이상할 정도로 순수합니다.
둘째, 보고 정렬은 확률 알고리즘의 직관을 설명하는 데 유용합니다. “기대 시간”, “거의 확실히 종료됨(almost surely)”, “확률 0과 불가능의 차이” 같은 개념을 설명할 때, 보고 정렬만큼 직관적인 예시는 드뭅니다. 배열이 작다면, 실제로 실행해 보고 “언젠가는 된다”는 감각을 몸으로 이해할 수 있습니다. 물론 n이 조금만 커져도 이 감각은 곧 절망으로 바뀝니다.
여기서 보고 정렬의 진짜 역할이 드러납니다. 보고 정렬은 경고 표지판입니다. 알고리즘 설계에서 “아무 전략도 쓰지 않는 것”이 어떤 결과를 낳는지를 극단적으로 보여줍니다. 무작위는 마법이 아닙니다. 구조 없는 무작위는, 대개 구조 없는 시간 낭비로 이어집니다.
그럼에도 불구하고, 보고 정렬은 완전히 쓸모없지는 않습니다. 이론적으로는 “모든 순열이 동일한 확률로 생성된다”는 가정이 성립하는 한, 언젠가는 정렬됩니다. 그리고 이 “언젠가”라는 단어가 문제의 핵심입니다. 컴퓨터 과학에서 우리는 보통 “언젠가”를 신뢰하지 않습니다. 대신 “상한”, “기대값”, “보장”을 원합니다. 보고 정렬은 그 모든 요구를 정면으로 거부합니다.
그래서 보고 정렬은 변호가 필요합니다. 실용성의 법정에서는 유죄지만, 교육과 개념의 법정에서는 무죄에 가깝습니다. 그리고 어쩌면 이것이 보고 정렬이 존재하는 이유일지도 모릅니다. 우리는 이미 너무 많은 영리한 알고리즘을 알고 있고, 가끔은 그 영리함이 어디에서 왔는지를 잊습니다. 보고 정렬은 그 출발점을, 즉 아무 생각도 하지 않았을 때의 세계를 보여줍니다. 그 세계는 비효율적이고, 우스꽝스럽고, 그리고 놀라울 만큼 교육적입니다.
그리고 우주의 열 죽음이 오기 전에 16개의 숫자를 정렬하고 싶다면 합리성이 얼마나 소중한지도 함께 가르쳐 줍니다.
