Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 연결 리스트(Linked List) 병합 정렬 구현하기

문제 개요

연결 리스트(Linked List)가 주어졌을 때, 병합 정렬(Merge Sort) 알고리즘을 사용하여 이를 오름차순으로 정렬하는 것이 목표입니다.

예를 들어 다음과 같은 연결 리스트가 있다고 가정해 보겠습니다.

정렬 전 리스트: 10->20->8->17->5->13->4
정렬 후 리스트: 4->5->8->10->13->17->20

알고리즘 접근 방식

연결 리스트에 병합 정렬을 적용하는 과정은 다음과 같습니다.

  1. 헤드(head)가 NULL이거나 리스트에 노드가 하나뿐이라면 이미 정렬된 상태이므로 그대로 반환합니다.
  2. 원본 리스트를 느린 포인터/빠른 포인터(slow/fast pointer) 기법을 활용해 두 부분으로 분할합니다.
  3. 분할된 앞부분과 뒷부분을 각각 재귀적으로 정렬합니다.
  4. 정렬된 두 리스트를 하나의 정렬된 리스트로 병합(merge)합니다.

C++ 구현 코드

#include <iostream>
#include <new>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct node {
   int data;
   struct node *next;
};
node *createList(int *arr, int n){
   node *head, *p;
   p = head = new node;
   head->data = arr[0];
   head->next = NULL;
   for (int i = 1; i < n; ++i) {
      p->next = new node;
      p = p->next;
      p->data = arr[i];
      p->next = NULL;
   }
   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) {
      result = head1;
      result->next = mergeSortedLists(head1->next,head2);
   } else {
      result = head2;
      result->next = mergeSortedLists(head1, head2->next);
   }
   return result;
}
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 << "Unsorted list: " << endl;
   displayList(head);
   mergeSort(&head);
   cout << "Final sorted list: " << endl;
   displayList(head);
   return 0;
}

코드 핵심 로직 설명

  • createList: 배열 데이터를 받아 연결 리스트를 생성합니다.
  • displayList: 헤드부터 끝까지 순회하며 노드의 값을 출력합니다.
  • mergeSortedLists: 두 개의 정렬된 리스트를 재귀적으로 비교하며 하나의 정렬된 리스트로 합칩니다. 한쪽 리스트가 NULL이 되면 나머지 리스트를 그대로 반환합니다.
  • splitList: 빠른 포인터(fast)는 두 칸씩, 느린 포인터(slow)는 한 칸씩 이동시켜 리스트의 중간 지점을 찾아냅니다. 이후 slow의 next를 NULL로 설정해 리스트를 둘로 분리합니다.
  • mergeSort: 분할(splitList) → 재귀 정렬 → 병합(mergeSortedLists)의 흐름으로 전체 정렬을 수행합니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다.

Unsorted list:
10 20 8 17 5 13 4
Final sorted list:
4 5 8 10 13 17 20

시간 및 공간 복잡도

  • 시간 복잡도: O(n log n) — 리스트를 반으로 나누는 작업이 log n번 발생하고, 각 단계에서 n개의 노드를 병합하기 때문입니다.
  • 공간 복잡도: O(log n) — 재귀 호출 스택이 차지하는 공간입니다. 배열 기반 정렬과 달리 연결 리스트는 추가 버퍼 없이 제자리 병합이 가능해 메모리 측면에서 유리합니다.

병합 정렬은 퀵 정렬과 달리 최악의 경우에도 O(n log n)의 성능을 보장하며, 특히 임의 접근(random access)이 어려운 연결 리스트 정렬에 가장 적합한 알고리즘으로 널리 알려져 있습니다.