정렬 알고리즘: 퀵·병합·기수 정렬부터 Timsort까지

한눈에 보기

정렬	최선	평균	최악	추가 메모리	안정 정렬
선택 정렬	O(N²)	O(N²)	O(N²)	O(1)	X
삽입 정렬	O(N)	O(N²)	O(N²)	O(1)	O
버블 정렬	O(N)	O(N²)	O(N²)	O(1)	O
병합 정렬	O(N log N)	O(N log N)	O(N log N)	O(N)	O
퀵 정렬	O(N log N)	O(N log N)	O(N²)	O(log N)	X
힙 정렬	O(N log N)	O(N log N)	O(N log N)	O(1)	X

기본 정렬

선택 정렬 (Selection Sort)

남은 원소 중 가장 작은 값을 찾아 0번 인덱스부터 차례대로 채워 넣는 방식이다. 입력 상태와 관계없이 항상 O(N²)이다.

삽입 정렬 (Insertion Sort)

원소를 하나씩 꺼내, 앞쪽의 이미 정렬된 부분에서 자기보다 작은 값이 나올 때까지 이동시켜 제자리에 끼워 넣는다.

• 최악은 O(N²)이지만 이미 정렬되어 있는 경우에는 O(N) 이다.

버블 정렬 (Bubble Sort)

인접한 두 원소를 비교해 기준에 맞지 않으면 자리를 바꾸며, 가장 큰 값을 뒤로 보내는 과정을 반복한다. 시간 복잡도는 O(N²)이다.

세 정렬 모두 배열 안에서 자리를 바꾸는 제자리 정렬이므로 추가 메모리는 O(1)이다.

병합 정렬 (Merge Sort)

분할 정복을 이용한 정렬이다.

1. 배열을 크기가 0 또는 1이 될 때까지 절반으로 계속 쪼갠다.
2. 쪼갠 배열을 다시 합치면서 정렬한다.

정렬된 두 배열 A, B를 결과 배열 C로 합칠 때는 각 배열의 맨 앞 원소 A[i]와 B[j]를 비교한다. A[i]가 B[j]보다 작거나 같으면 A[i]를 C에 넣고 i를 증가시키고, 아니면 B[j]를 넣고 j를 증가시킨다.

• 시간 복잡도: O(N log N)
• 공간 복잡도: O(N). 합칠 때 별도의 배열이 필요하다.

퀵 정렬 (Quick Sort)

역시 분할 정복을 이용한다. 기준값(pivot)을 하나 정해 pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤 양쪽을 재귀적으로 정렬한다.

1. 배열의 값 하나를 pivot으로 선택한다.
2. 가장 왼쪽 인덱스를 left, 가장 오른쪽 인덱스를 right에 저장한다.
3. right부터 비교한다. 값이 pivot보다 크면 right를 하나 감소시키며 반복하고, pivot보다 작은 값을 찾으면 멈춘다.
4. left를 비교한다. 값이 pivot보다 작으면 left를 하나 증가시키며 반복하고, pivot보다 큰 값을 찾으면 멈춘다.
5. 두 위치의 값을 교환한다. left와 right가 만날 때까지 3~5를 반복한다.
6. 만난 위치에 pivot을 두고, pivot의 왼쪽과 오른쪽 부분 배열에 같은 과정을 반복한다.

• 시간 복잡도: 평균 O(N log N), 최악 O(N²)

퀵 정렬 개선 방법

pivot으로 매번 최솟값이나 최댓값이 선택되면 배열이 한쪽으로만 나뉘어 O(N²)이 된다. 예를 들어 맨 앞이나 맨 뒤 원소를 pivot으로 쓰는데 배열이 이미 정렬되어 있는 경우이다.

따라서 pivot을 잘 선택해야 한다. median-of-three는 세 개의 원소를 뽑아 그 중앙값을 pivot으로 삼는 방법이다.

Quick Sort vs Merge Sort

	Quick Sort	Merge Sort
안정성	Unstable	Stable
메모리	적게 쓴다	많이 쓴다
최악의 경우	O(N²)	O(N log N)
특징	참조 지역성이 좋다	연결 리스트 정렬에 효율적이다

최악의 시간 복잡도는 병합 정렬이 더 낫지만, 일반적으로는 퀵 정렬이 더 빠르다. 퀵 정렬은 배열 안에서 인접한 데이터에 연속적으로 접근하므로 참조 지역성이 좋아 캐시를 잘 활용하기 때문이다.

안정 정렬 (Stable Sort)

정렬했을 때 값이 같은 원소들의 기존 순서가 변하지 않으면 안정 정렬이다.

• 안정 정렬: 삽입 정렬, 병합 정렬, 버블 정렬, 계수 정렬(Counting Sort)
• 불안정 정렬: 선택 정렬, 퀵 정렬, 힙 정렬

기수 정렬 (Radix Sort)

낮은 자릿수부터 자릿수별로 분류해 가며 정렬하는 방식이다. 원소끼리 비교 연산을 하지 않는다.

1. 1의 자리를 기준으로 새로운 테이블에 분류한다. 예를 들어 50은 테이블의 0번 칸에 들어간다.
2. 1의 자리 기준으로 정렬된 결과를 다시 10의 자리 기준으로 분류한다. 50은 5번 칸에 들어간다.
3. 가장 높은 자릿수까지 반복한다.

• 시간 복잡도: 자릿수를 d라고 하면 O(dN)이다. 자릿수가 작게 제한되어 있으면 사실상 O(N)이다.
• 정렬 속도가 빠르지만, 데이터 전체 크기에 더해 기수 테이블만큼의 메모리가 추가로 필요하다.

Internal Sort vs External Sort

• Internal Sort: 메인 메모리 안에서 일어나는 정렬
• External Sort: 데이터가 메모리에 다 올라가지 않아 보조 기억 장치(디스크)를 사용하는 정렬

주기억 장치와 보조 기억 장치의 접근 속도는 극단적으로 차이가 난다. 그래서 외부 정렬은 보조 기억 장치에 접근하는 횟수를 최소화하는 것이 최우선이다.

과정

1. 정렬할 파일을 여러 개의 run으로 분할한다. run은 메모리에 적재할 수 있는 크기의 단위이다.
2. 각 run을 메모리에서 내부 정렬한 뒤 파일에 저장한다.
3. 저장된 run들을 병합해 다시 파일에 저장한다.
4. run의 수가 1이 될 때까지 병합을 반복한다.

언어의 기본 정렬

Python: Timsort

삽입 정렬과 병합 정렬을 결합한 정렬 알고리즘이다. 삽입 정렬은 인접한 메모리끼리 비교를 반복하기 때문에 참조 지역성이 아주 좋고, 작은 배열에서는 빠르다는 점을 이용한다.

1. 배열을 2^x 크기의 작은 덩어리(run)로 나누고, 각 덩어리를 삽입 정렬로 정렬한다.
2. 이때 덩어리의 다음 원소도 계속 증가하거나 감소하는 흐름을 이어 간다면, 덩어리를 최대한 크게 만들기 위해 그 원소까지 덩어리에 포함한다. 이미 정렬된 구간을 그대로 활용하는 것이다.
3. 이런 식으로 배열 전체를 덩어리들로 만든다.
4. 덩어리들을 병합해야 하는데, 크기가 제각각이라 아무렇게나 병합하면 비효율적이다.
5. 그래서 덩어리를 스택에 push하면서, 스택 위쪽 덩어리들의 크기가 정해진 조건을 만족하지 않으면 인접한 두 덩어리를 병합한다. 비슷한 크기의 덩어리끼리 병합되도록 유지하기 위한 규칙이다.
6. 마지막에 남은 덩어리들을 모두 병합한다.

자세한 내용은 Naver D2의 Tim sort 글에 잘 정리되어 있다.

Java

• Primitive 타입 배열: 듀얼 피벗 퀵 정렬(Dual-Pivot Quicksort)
• 객체 배열과 컬렉션: Timsort

더 생각해 볼 질문

• Java에서 primitive 배열과 객체(컬렉션)의 정렬 방식이 다른 이유
• 듀얼 피벗 퀵 정렬의 동작 방식