왜 여러 정렬 알고리즘을 비교해서 배우는가

정렬(sorting)은 “값을 크기 순서대로 늘어놓는다”는 목표는 하나지만, 그 목표에 도달하는 방법은 여러 가지이고 방법마다 속도·메모리 사용량·구현 난이도가 다르다. 독학사 시험에서는 “이 알고리즘의 이름은?”을 묻기보다, 배열 상태가 한 단계씩 어떻게 바뀌는지를 손으로 추적하게 하거나, 여러 정렬을 안정성·복잡도 기준으로 비교하게 하는 문항이 반복적으로 나온다. 그래서 이 편은 하나의 예시 배열을 정해 놓고 일곱 가지 정렬 알고리즘 전부에 같은 배열을 적용해 보면서, “왜 이 정렬은 빠르고 저 정렬은 느린가”를 직접 눈으로 확인하는 방식으로 구성한다.

쉽게 말하면: 정렬 알고리즘마다 “무엇을 비교하고 무엇을 옮기는가”에 대한 전략이 다르고, 그 전략 차이가 속도·메모리·안정성의 차이로 이어진다.

이 편 전체에서 기준으로 쓸 예시 배열은 다음과 같다.

선택 정렬 — 매번 최솟값을 찾아 앞으로 보낸다

선택 정렬(selection sort)은 정렬되지 않은 구간에서 가장 작은 값을 찾아, 그 값을 정렬되지 않은 구간의 맨 앞과 자리를 바꾸는 과정을 반복한다.

원소가 $n$개면 패스는 $n-1$번 필요하고, 매 패스마다 남은 구간 전체를 훑어 최솟값을 찾으므로 비교 횟수는 $(n-1) + (n-2) + \cdots + 1$번이다. 이 합은 항상 $\frac{n(n-1)}{2}$이 되어, 배열이 이미 정렬되어 있어도 똑같이 다 비교해야 하므로 최선·평균·최악 모두 $O(n^2)$이다.

삽입 정렬 — 손안의 카드를 정렬하듯

삽입 정렬(insertion sort)은 카드를 손에 쥐고 한 장씩 뽑아 이미 정렬된 카드 뭉치의 알맞은 자리에 끼워 넣는 방식과 같다. 왼쪽부터 “이미 정렬된 부분”을 늘려가면서, 새로 뽑은 값을 그보다 큰 값들을 오른쪽으로 밀어내고 알맞은 자리에 넣는다.

삽입 정렬은 배열이 이미 정렬에 가까울수록 밀어야 할 값이 적어 빨라진다. 최선의 경우(이미 정렬된 배열)는 각 값을 한 번만 확인하고 이동 없이 넘어가므로 $O(n)$이고, 최악의 경우(완전히 역순으로 정렬된 배열)는 매번 왼쪽 전체를 다 밀어야 하므로 $O(n^2)$이다.

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

버블 정렬(bubble sort)은 배열을 왼쪽부터 오른쪽으로 훑으면서 인접한 두 값을 비교해, 왼쪽이 더 크면 서로 자리를 바꾸는 과정을 반복한다. 한 패스가 끝날 때마다 그 구간에서 가장 큰 값이 거품처럼 오른쪽 끝으로 떠오른다.

4번째 패스에서 교환이 한 번도 일어나지 않았다는 사실은 “이미 정렬이 끝났다”는 신호로 쓸 수 있다. 이 신호를 이용해 더 이상 패스를 반복하지 않고 즉시 종료하도록 구현하면(조기 종료, early termination), 이미 정렬된 배열에 대해서는 한 패스(비교 $n-1$번)만 돌고 끝나 $O(n)$이 된다. 이 최적화가 없으면 이미 정렬된 배열에도 $n-1$번의 패스를 전부 도는 $O(n^2)$ 구현이 된다. 최악의 경우(역순 배열)는 조기 종료 여부와 무관하게 $O(n^2)$이다.

세 정렬을 한눈에 — 최종 결과와 비교 방식

선택·삽입·버블 정렬 모두 예시 배열을 1, 2, 3, 5, 8, 9로 정렬한다는 결과는 같지만, “무엇을 기준으로 옮기는가”가 다르다.

퀵 정렬 — 기준값으로 좌우를 나눈 뒤 각자 정렬

퀵 정렬(quick sort)은 배열에서 피벗(pivot, 기준값)을 하나 고른 뒤, 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 모으는 분할(partition) 과정을 거치고, 나뉜 두 구간을 각각 재귀적으로 같은 방식으로 정렬한다. 이 편에서는 맨 오른쪽 값을 피벗으로 고르는 방식(로무토 분할, Lomuto partition)으로 첫 분할 과정을 추적한다.

예시 배열 5, 2, 8, 1, 9, 3(인덱스 0~5)에서 피벗은 맨 오른쪽 값 3(인덱스 5)이다. 로무토 분할은 “피벗보다 작은 값들의 경계”를 가리키는 변수 i를 배열 시작 바로 앞(가상의 인덱스 -1)에 두고, j를 0부터 피벗 바로 앞 인덱스(4)까지 옮기며 비교한다.

퀵 정렬의 성능은 피벗을 얼마나 균형 있게 고르느냐에 달려 있다. 매번 배열을 절반씩 나누는 데 가까운 피벗을 고르면 분할 깊이가 $\log n$ 수준이 되어 평균·최선 복잡도가 $O(n \log n)$이 되지만, 이미 정렬된 배열에서 매번 맨 끝(또는 맨 앞) 값을 피벗으로 고르면 한쪽 구간이 텅 비고 다른 쪽에 나머지 전부가 몰리는 극단적인 분할이 반복되어 최악의 경우 $O(n^2)$까지 나빠진다.

합병 정렬 — 반으로 쪼갠 뒤 정렬된 두 조각을 합친다

합병 정렬(merge sort)은 배열을 더 이상 쪼갤 수 없을 때까지(원소 1개) 절반씩 나눈 뒤, 정렬된 두 조각을 하나로 합치는 병합(merge) 과정을 거슬러 올라가며 반복하는 방식이다. 예시 배열을 절반으로 나누면 5, 2, 8과 1, 9, 3이 되고, 각각을 재귀적으로 정렬하면 2, 5, 8과 1, 3, 9가 된다. 이 두 정렬된 조각을 병합하는 과정을 추적한다.

병합 결과는 1, 2, 3, 5, 8, 9로 정렬이 완료된다. 병합 과정에서 두 조각을 비교하는 횟수는 항상 두 조각 길이의 합에 비례하고, 나누는 깊이는 항상 $\log n$이므로, 합병 정렬은 배열이 어떤 순서로 주어지든 **최선·평균·최악 모두 $O(n \log n)$**으로 일정하다. 다만 병합 과정에서 결과를 담을 별도의 배열이 필요하므로, 원본 배열 크기에 비례하는 $O(n)$의 추가 메모리를 쓴다.

히프 정렬 — 최대 힙을 만들고 하나씩 꺼낸다

히프 정렬(heap sort)은 11편에서 다룬 히프(heap, 완전이진트리 기반 우선순위 큐)의 성질을 이용한다. 배열 전체를 최대 힙(부모가 항상 자식보다 큰 히프)으로 재배열한 뒤, 힙의 루트(항상 최댓값)를 배열의 맨 끝과 교환하고 힙 크기를 하나 줄이는 과정을 반복하면, 매번 확정되는 값이 오른쪽부터 채워지며 정렬이 완성된다.

히프 정렬은 힙을 만드는 데 $O(n)$, 이후 $n$번 루트를 꺼내면서 매번 힙을 재정렬하는 데 각각 $O(\log n)$이 걸려, 전체 시간 복잡도는 **최선·평균·최악 모두 $O(n \log n)$**이다. 배열 안에서 교환만으로 동작하므로 추가 메모리가 거의 필요 없다.

기수 정렬 — 비교하지 않고 자릿수로 나눈다

기수 정렬(radix sort)은 지금까지의 정렬과 근본적으로 다르다. 두 값을 직접 비교하지 않고, 값을 이루는 자릿수(digit)마다 순서대로 안정적인 방식으로 재배치해서 정렬한다. 정수를 예로 들어 1의 자리부터 시작해 가장 큰 자릿수까지 차례로 처리하는 방식(최하위 자릿수부터, Least Significant Digit, LSD)을 추적한다. 자릿수가 다양한 값을 다루기 위해 새로운 예시 배열 170, 45, 75, 90, 802, 24, 2, 66을 쓴다.

세 번의 자릿수 패스(1의 자리, 10의 자리, 100의 자리)를 거치자 완전히 정렬되었다. 각 자릿수 패스는 그 자체로 안정적인 정렬(값이 같으면 원래 순서를 유지하는 정렬, 보통 계수 정렬 방식을 이용)이어야 한다. 그래야 예를 들어 1의 자리가 같은 170과 90이 그다음 자릿수(10의 자리) 패스에서도 서로 상대적인 순서가 잘못 뒤바뀌지 않는다.

기수 정렬의 시간 복잡도는 자릿수(또는 자리 수)를 $d$, 원소 개수를 $n$, 각 자릿수가 가질 수 있는 값의 범위(기수, 10진수라면 10)를 $k$라 할 때 $O(d \times (n + k))$다. $d$와 $k$가 고정된 상수로 볼 수 있는 상황(예: 자릿수 범위가 제한된 정수)이라면 사실상 $O(n)$에 가까운 성능을 낼 수 있어, 비교 기반 정렬의 이론적 하한인 $O(n \log n)$보다 빠를 수 있다. 다만 이는 “비교를 하지 않기 때문”이며, 문자열이나 부동소수점처럼 자릿수 개념이 명확하지 않은 데이터에는 그대로 적용하기 어렵다.

일곱 정렬의 안정성·제자리 여부·복잡도 종합 비교

안정 정렬(stable sort)이란 값이 같은 원소 두 개가 있을 때, 정렬 후에도 그 둘의 원래 상대적 순서가 바뀌지 않는 정렬을 말한다. 제자리 정렬(in-place sort)이란 입력 배열과 별개로 원소 개수에 비례하는 추가 배열을 만들지 않고, 원본 배열 안에서 교환만으로 정렬을 끝내는 방식을 말한다.

왜 선택 정렬은 안정적이지 않은가: 최솟값을 찾아 “멀리 떨어진 자리”와 통째로 교환하기 때문에, 그 교환 과정에서 같은 값을 가진 다른 원소를 건너뛰어 상대적 순서가 뒤바뀔 수 있다. 예를 들어 [5a, 5b, 2](첨자는 구분용, 두 5는 값이 같음)에서 최솟값 2를 찾아 맨 앞의 5a와 교환하면 [2, 5b, 5a]가 되어, 원래 5a가 5b보다 앞에 있었는데 순서가 뒤집힌다.

왜 삽입 정렬과 버블 정렬은 안정적인가: 두 정렬 모두 값이 진짜로 더 클 때만 교환하거나 이동시키고, 값이 같으면 교환하지 않고 그대로 둔다. 그래서 같은 값끼리는 원래 순서가 유지된다.

자주 틀리는 점: “모든 정렬이 안정적이지 않다”거나 “빠른 정렬(퀵·히프)일수록 안정적이다”처럼 안정성과 속도를 연결 지어 착각하면 안 된다. 안정성은 속도와 무관하게, “값이 같을 때 교환하지 않고 넘어가는가”라는 구현 방식에서 결정된다.

순차 탐색과 이진 탐색

정렬이 끝난 배열에서 특정 값을 찾는 방법은 06편에서 배열을 다룰 때 언급했던 두 갈래로 정리된다.

순차 탐색(sequential search, 선형 탐색이라고도 한다)은 배열의 맨 앞부터 하나씩 확인하는 가장 단순한 방법이다. 정렬 여부와 무관하게 항상 쓸 수 있지만, 최악의 경우(찾는 값이 맨 끝에 있거나 없을 때) $n$번을 다 확인해야 해 $O(n)$이다.

이진 탐색(binary search)은 배열이 정렬되어 있을 때만 쓸 수 있는 방법으로, 탐색 범위의 중간값과 비교해 목표값이 그보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 남기고 나머지를 통째로 버리는 과정을 반복한다. 정렬된 배열 2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91(인덱스 0~10)에서 45를 찾는 과정을 두 방법으로 비교한다.

같은 배열, 같은 목표값인데도 이진 탐색은 절반씩 버리는 전략 덕분에 훨씬 적은 비교로 값을 찾는다. 원소가 $n$개일 때 이진 탐색은 매 비교마다 범위를 절반으로 줄이므로 남은 범위가 1이 될 때까지 걸리는 비교 횟수는 $\log_2 n$번에 비례해 $O(\log n)$이다.

자주 틀리는 점: 이진 탐색은 배열이 정렬되어 있어야만 쓸 수 있다. 정렬되지 않은 배열에 이진 탐색을 적용하면 절반을 버리는 기준 자체가 성립하지 않아 잘못된 결과가 나올 수 있다. “정렬 안 된 배열에 이진 탐색이 더 빠르다”는 식의 보기는 항상 틀린 진술이다.

해싱과 충돌 처리

해싱(hashing)은 값을 배열의 인덱스로 직접 변환하는 해시 함수(hash function)를 이용해, 탐색·삽입·삭제를 평균적으로 $O(1)$에 처리하려는 방법이다. 해시 함수 $h(k)$는 키(key) $k$를 입력받아 테이블 크기 범위 안의 인덱스를 돌려준다. 가장 단순한 형태는 나머지 연산을 이용한 나눗셈 해싱이다.

• $k$: 저장하려는 키(값)
• $m$: 해시테이블의 크기(칸 수)
• $\bmod$: 나머지 연산(나눗셈의 나머지를 취한다는 뜻)

테이블 크기 $m = 7$일 때, 키 10, 22, 31, 4, 15, 28을 차례로 삽입하면 해시값은 각각 $10 \bmod 7 = 3$, $22 \bmod 7 = 1$, $31 \bmod 7 = 3$, $4 \bmod 7 = 4$, $15 \bmod 7 = 1$, $28 \bmod 7 = 0$이다. 여기서 31과 10이 똑같이 인덱스 3을 가리키고, 15와 22가 똑같이 인덱스 1을 가리키는 문제가 생긴다. 서로 다른 키가 같은 인덱스로 계산되는 이 현상을 충돌(collision)이라고 부르며, 해시테이블 자체를 아무리 잘 설계해도 키의 개수가 테이블 크기보다 많아지면 충돌은 피할 수 없다(비둘기집 원리). 그래서 실제로 쓸 수 있는 해싱은 충돌 처리 방법까지 함께 갖춰야 한다.

체이닝 — 같은 칸에 리스트로 매달기

체이닝(chaining, 분리 연결법이라고도 한다)은 각 인덱스 칸을 하나의 값이 아니라 연결리스트(07편)로 만들어, 같은 인덱스로 계산된 키들을 그 리스트에 계속 이어 붙이는 방법이다. 위 예시 키들을 체이닝으로 삽입한 결과는 다음과 같다.

탐색할 때는 먼저 해시값으로 인덱스를 계산한 뒤, 그 칸의 연결리스트를 처음부터 훑어 원하는 키를 찾는다. 한 칸에 몰리는 키가 적을수록(테이블 크기에 비해 키 개수가 적당할수록) 리스트 길이가 짧아 탐색이 빠르다.

개방 주소법 — 다른 빈칸을 찾아 나선다

개방 주소법(open addressing)은 별도의 연결리스트를 두지 않고, 충돌이 나면 정해진 규칙에 따라 같은 테이블 안의 다른 칸을 순서대로 확인해 빈칸을 찾아 넣는 방법이다. 어떤 순서로 다음 칸을 찾는지에 따라 세 가지로 나뉜다.

선형 조사법(linear probing)은 충돌이 나면 바로 다음 칸, 그다음 칸 순서로 한 칸씩 옮겨가며 빈칸을 찾는다. 탐사 규칙은 $h(k, i) = (h(k) + i) \bmod m$이며, $i$는 시도 횟수(0, 1, 2, …)다. 앞서 쓴 키들을 선형 조사법으로 순서대로 삽입하는 과정을 추적한다.

제곱 조사법(quadratic probing)은 다음 칸을 찾을 때 건너뛰는 간격을 $i$가 아니라 $i^2$(1, 4, 9, …)로 늘려 나간다. 탐사 규칙은 $h(k, i) = (h(k) + i^2) \bmod m$이다. 선형 조사법은 충돌이 난 자리 바로 옆에 계속 값을 채워 넣어 특정 구간에 값이 몰리는 1차 군집화(primary clustering) 현상이 잘 생기는데, 제곱 조사법은 건너뛰는 간격을 점점 넓혀서 이 군집화를 어느 정도 완화한다.

이중 해싱(double hashing)은 하나가 아니라 두 개의 해시 함수 $h_1(k)$, $h_2(k)$를 준비해, 탐사 규칙을 $h(k, i) = (h_1(k) + i \times h_2(k)) \bmod m$으로 정한다. 건너뛰는 간격 자체가 키마다 다르게(두 번째 해시 함수의 값만큼) 달라지므로, 같은 자리에서 충돌한 키들이라도 서로 다른 간격으로 흩어져 군집화가 가장 적게 일어나는 방법으로 꼽힌다.

자주 틀리는 점: 체이닝은 테이블 크기(칸 수)를 넘어서도 삽입할 수 있지만(리스트가 길어질 뿐), 개방 주소법은 테이블에 빈칸이 없으면 더 이상 삽입할 수 없다는 근본적인 차이가 있다. 또한 개방 주소법에서 키를 삭제할 때 그 칸을 단순히 “비어 있음”으로 표시하면, 그 자리를 거쳐 탐사했던 다른 키를 찾을 때 탐사가 중간에 끊겨 버리는 문제가 생길 수 있어 “삭제됨” 표시를 별도로 관리해야 한다.

자주 틀리는 점

• 선택 정렬과 삽입 정렬을 헷갈리는 실수: 선택 정렬은 “남은 구간에서 최솟값을 찾아 앞으로 보내는” 방식이고, 삽입 정렬은 “새 값을 이미 정렬된 구간의 알맞은 자리에 끼워 넣는” 방식이다. 확정되는 위치가 선택 정렬은 앞자리, 삽입 정렬은 정렬된 구간의 확장이라는 점이 다르다.
• 퀵 정렬의 평균과 최악 복잡도를 혼동하는 실수: 퀵 정렬은 평균 $O(n \log n)$이지만, 피벗이 계속 한쪽으로 치우치게 뽑히면 최악의 경우 $O(n^2)$까지 나빠질 수 있다.
• 합병 정렬을 제자리 정렬로 착각하는 실수: 합병 정렬은 병합 단계에서 원본과 별도인 임시 배열이 필요하므로 제자리 정렬이 아니다.
• 이진 탐색을 정렬되지 않은 배열에 적용하는 실수: 이진 탐색은 정렬된 배열에서만 성립한다.
• 개방 주소법에서 삭제를 단순히 빈칸 처리하는 실수: 삭제된 자리를 그냥 비워 버리면 그 자리를 거쳐 탐사해야 했던 다른 키의 탐색이 중간에 끊겨 찾지 못하게 될 수 있다.

핵심 정리

• 선택·삽입·버블 정렬은 모두 $O(n^2)$ 계열이지만 “무엇을 확정하고 무엇을 옮기는가”가 다르고, 삽입·버블은 안정적인 반면 선택은 안정적이지 않다.
• 퀵·합병·히프 정렬은 모두 평균 $O(n \log n)$이지만, 퀵 정렬만 최악의 경우 $O(n^2)$까지 나빠질 수 있고, 합병 정렬만 추가 메모리($O(n)$)가 필요해 제자리 정렬이 아니다.
• 기수 정렬은 값을 직접 비교하지 않고 자릿수별로 안정적인 정렬을 반복해 $O(d(n+k))$에 정렬하며, 자릿수와 기수가 고정되어 있으면 비교 기반 정렬의 이론적 하한($O(n \log n)$)보다 빠를 수 있다.
• 이진 탐색은 정렬된 배열에서 범위를 절반씩 줄여 $O(\log n)$에 값을 찾고, 순차 탐색은 정렬 여부와 무관하게 항상 쓸 수 있지만 $O(n)$이다.
• 해싱은 충돌을 피할 수 없으며, 체이닝(연결리스트로 매달기)과 개방 주소법(선형·제곱 조사법, 이중 해싱으로 다른 빈칸 찾기)이 대표적인 충돌 처리 방법이다.

마무리 복습

참고 자료

• MDN JavaScript reference  — 배열 정렬과 Map·Set 같은 해시 기반 구조를 이해하는 데 참고할 수 있는 자료.
• 국가평생교육진흥원 과목별 평가영역  — 정렬·탐색·해싱 관련 출제 범위 확인용 공식 안내.