문제 정의
이중 연결 리스트(doubly linked list)가 주어졌을 때, 병합 정렬(Merge Sort) 알고리즘을 사용하여 노드 값들을 오름차순으로 정렬하는 것이 이번 문제의 목표입니다.
입력 리스트 : 10 -> 20 -> 8 -> 17 -> 5 -> 13 -> 4 정렬 결과 : 4 -> 5 -> 8 -> 10 -> 13 -> 17 -> 20
알고리즘 접근 방식
병합 정렬은 대표적인 분할 정복(Divide and Conquer) 기법으로, 연결 리스트에 적용할 때 다음 순서로 동작합니다.
- 기저 조건 확인 — 헤드(head)가 NULL이거나 노드가 하나뿐이라면 이미 정렬된 상태이므로 그대로 반환합니다.
- 리스트 분할 — 빠른 포인터(fast)와 느린 포인터(slow)를 이용해 원본 리스트를 절반 크기의 두 리스트로 나눕니다.
- 재귀 정렬 — 앞쪽 절반과 뒤쪽 절반을 각각 병합 정렬로 재귀적으로 정렬합니다.
- 병합(Merge) — 정렬이 끝난 두 리스트를 하나의 정렬된 리스트로 합치며, 이때 prev 포인터도 함께 갱신해 이중 연결 구조를 유지합니다.
C++ 전체 구현 코드
#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
int data;
struct node *next;
struct node *prev;
};
node *createList(int *arr, int n){
node *head, *p, *q;
p = head = new node;
head->data = arr[0];
head->prev = NULL;
head->next = NULL;
for (int i = 1; i < n; ++i) {
q = new node;
q->data = arr[i];
q->prev = p;
q->next = NULL;
p->next = q;
p = q;
}
return head;
}
void displayList(node *head){
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
node *mergeSortedLists(node *head1, node *head2){
node *result = NULL;
if (head1 == NULL) {
return head2;
}
if (head2 == NULL) {
return head1;
}
if (head1->data < head2->data) {
head1->next = mergeSortedLists(head1->next, head2);
head1->next->prev = head1;
head1->prev = NULL;
return head1;
} else {
head2->next = mergeSortedLists(head1, head2->next);
head2->next->prev = head2;
head2->prev = NULL;
return head2;
}
}
void splitList(node *src, node **fRef, node **bRef){
node *fast;
node *slow;
slow = src;
fast = src->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*fRef = src;
*bRef = slow->next;
slow->next = NULL;
}
void mergeSort(node **head){
node *p = *head;
node *a = NULL;
node *b = NULL;
if (p == NULL || p->next == NULL) {
return;
}
splitList(p, &a, &b);
mergeSort(&a);
mergeSort(&b);
*head = mergeSortedLists(a, b);
}
int main(){
int arr[] = {10, 20, 8, 17, 5, 13, 4};
node *head;
head = createList(arr, SIZE(arr));
cout << "정렬되지 않은 리스트: " << endl;
displayList(head);
mergeSort(&head);
cout << "최종 정렬된 리스트: " << endl;
displayList(head);
return 0;
}
주요 함수 살펴보기
- createList() — 배열 값을 기반으로 이중 연결 리스트를 생성하고 헤드 노드를 반환합니다.
- splitList() — 토끼-거북이(tortoise and hare) 기법처럼 fast 포인터를 두 칸씩, slow 포인터를 한 칸씩 이동시켜 리스트 중앙을 찾은 뒤 둘로 자릅니다.
- mergeSortedLists() — 두 정렬 리스트를 재귀적으로 비교·연결하며, 병합 후 각 노드의 prev 포인터를 올바르게 재설정합니다.
- mergeSort() — 위 과정을 조합해 리스트 전체를 정렬하고 최종 헤드 포인터를 갱신합니다.
실행 결과
위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.
정렬되지 않은 리스트: 10 20 8 17 5 13 4 최종 정렬된 리스트: 4 5 8 10 13 17 20
복잡도 분석
- 시간 복잡도: O(n log n) — 매 단계마다 리스트를 절반으로 나누는 분할이 O(log n)번 발생하고, 각 단계의 병합에 O(n)의 시간이 소요됩니다.
- 공간 복잡도: O(log n) — 재귀 호출 스택 깊이만큼의 추가 공간이 사용됩니다.
- 참고: 연결 리스트는 임의 접근(random access)이 불가능해 퀵 정렬 적용이 까다롭지만, 병합 정렬은 순차 접근만으로 동작하므로 연결 리스트 정렬에 특히 적합한 알고리즘입니다.