정렬 2편 (분할 정복: 병합 정렬, 퀵 정렬)

🚀 이 주제를 선택한 이유 & 학습 목표

선택 배경:
이전 글에서 O(n²) 정렬 알고리즘들을 학습하며, 이들의 명확한 한계를 인지했습니다. 데이터의 양이 증가함에 따라 성능이 기하급수적으로 저하되는 문제를 해결하기 위해, 보다 효율적인 접근 방식인 '분할 정복(Divide and Conquer)' 패러다임을 학습할 필요성을 느꼈습니다.

학습 목표:

1. '분할 정복' 패러다임의 세 가지 단계를 이해하고 설명할 수 있습니다.
2. 분할 정복의 대표적인 예시인 병합 정렬과 퀵 정렬의 동작 원리를 코드 수준에서 이해합니다.
3. 두 알고리즘의 시간/공간 복잡도, 안정성, 캐시 효율성 등의 특징을 비교하고, 어떤 상황에 어떤 정렬이 유리한지 판단할 수 있는 근거를 마련합니다.

📚 핵심 개념 및 원리

1. 분할 정복 (Divide and Conquer) 이란?

분할 정복은 해결하기 어려운 큰 문제를 해결 가능한 작은 문제로 나눈 뒤, 작은 문제들을 해결하고 그 결과를 다시 합쳐 원래의 큰 문제를 해결하는 알고리즘 설계 기법입니다. 주로 다음 세 단계를 따릅니다.

• 분할 (Divide): 원래 문제를 여러 개의 작은 하위 문제로 나눕니다.
• 정복 (Conquer): 하위 문제가 더 이상 나눌 수 없을 정도로 작아지면 해결하고, 그렇지 않다면 재귀적으로 분할 정복을 다시 적용합니다.
• 결합 (Combine): 해결된 하위 문제들의 답을 합쳐 원래 문제의 답을 구합니다.

2. 병합 정렬 (Merge Sort)

• 원리: '선 분할, 후 결합(정렬)' 방식입니다. 배열을 요소가 하나만 남을 때까지 계속해서 절반으로 나누고(분할), 다시 합쳐나가는 과정(결합)에서 정렬을 수행합니다.

• 고려사항:

  • 안정적인 성능: 최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 보장합니다.
  • 추가 메모리 필요: 두 개의 정렬된 하위 배열을 합치기 위한 임시 배열(temp)이 필요하므로 O(n)의 추가 공간을 사용합니다. 이는 메모리 사용에 민감한 환경에서는 큰 단점이 될 수 있습니다.
  • 안정 정렬 (Stable Sort): 중복된 값들의 상대적 순서가 유지됩니다.

• • Java 코드 예시:

    void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        // 분할 (Divide) & 정복 (Conquer)
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 결합 (Combine)
        merge(arr, left, mid, right);
    }
    }
    void merge(int arr[], int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    
    for (int l = 0; l < temp.length; l++) {
        arr[left + l] = temp[l];
    }
    }

3. 퀵 정렬 (Quick Sort)

• 원리: '선 정렬(분할), 후 분할' 방식입니다. 배열 내에서 하나의 기준점인 '피벗(pivot)'을 선택하고, 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 나누는 '분할(Partition)' 과정을 통해 정렬합니다. 이후 나뉜 두 개의 하위 배열에 대해 이 과정을 재귀적으로 반복합니다.

• 고려사항:

  • 평균적으로 가장 빠름: 이름처럼 평균 시간 복잡도가 O(n log n)으로 매우 빠릅니다. 인접한 메모리를 참조하는 경우가 많아 캐시 효율성이 좋기 때문입니다.
  • 제자리 정렬 (In-place Sort): 병합 정렬과 달리 추가적인 배열이 거의 필요 없어(O(log n)의 스택 공간) 메모리 사용에 매우 효율적입니다.
  • 최악의 경우 존재: 피벗이 계속해서 가장 크거나 작은 값으로 선택될 경우(예: 이미 정렬된 배열), O(n²)의 시간 복잡도를 가질 수 있습니다.
  • 불안정 정렬 (Unstable Sort): 분할 과정에서 값의 위치가 크게 바뀌므로 안정성을 보장하지 않습니다.

• Java 코드 예시:

  void quickSort(int arr[], int low, int high) {
      if (low < high) {
          // 분할(Partition)을 통해 피벗의 위치를 확정하고,
          // 그 위치를 기준으로 다시 재귀 호출
          int pi = partition(arr, low, high);
          quickSort(arr, low, pi - 1);
          quickSort(arr, pi + 1, high);
      }
  }
  
  int partition(int arr[], int low, int high) {
      int pivot = arr[high];
      int i = (low - 1);
      for (int j = low; j < high; j++) {
          if (arr[j] <= pivot) {
              i++;
              int temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
      int temp = arr[i + 1];
      arr[i + 1] = arr[high];
      arr[high] = temp;
      return i + 1;
  }

💡 장점, 단점 및 비교

특징	병합 정렬 (Merge Sort)	퀵 정렬 (Quick Sort)
시간 복잡도 (평균)	O(n log n)	O(n log n)
시간 복잡도 (최악)	O(n log n)	O(n²)
공간 복잡도	O(n)	O(log n)
안정성 (Stability)	Stable	Unstable
핵심 전략	선 분할, 후 정렬(결합)	선 정렬(분할), 후 분할

🤔 나의 이해와 생각 정리 (회고)

핵심 요약:
병합 정렬과 퀵 정렬은 분할 정복 패러다임을 사용하지만, '언제' 정렬이 일어나는지에 대한 철학이 다릅니다. 병합 정렬은 재귀가 끝까지 호출된 후 돌아오면서 정렬하고, 퀵 정렬은 재귀로 들어가기 전에 partition을 통해 부분적인 정렬을 수행합니다.

새롭게 깨달은 점:

• 병합 정렬의 merge 함수와 재귀: 재귀의 동작 방식이 처음에는 추상적이었습니다. 하지만 merge 함수가 이미 정렬된 두 하위 배열을 입력받는 것이 보장된다는 사실을 깨닫자 모든 것이 명확해졌습니다. 재귀가 가장 깊은 곳까지 내려가 요소 하나짜리 배열들을 만들고, 그것들이 병합되면서 올라올 때마다 정렬 상태가 유지/확장되는 구조였습니다. mid와 right 인덱스는 단순히 숫자가 아니라, 각 재귀 호출이 책임져야 할 '문제의 범위'를 정의하는 좌표 정보였습니다.
• 퀵 정렬의 partition 함수와 i, j의 움직임: partition 함수의 역할이 '완벽한 정렬'이 아닌 '피벗을 제자리에 놓기 위한 그룹화' 라는 것을 이해하는 것이 핵심이었습니다. i와 j의 움직임이 가장 혼란스러웠는데, '탐색자' j와 '작은 값 그룹의 경계 관리자' i라는 역할로 나누어 생각하니 명쾌해졌습니다. j는 모든 요소를 순회하고, i는 오직 j가 피벗보다 작은 값을 발견했을 때만 움직이며 자신의 구역을 확장하고 새로운 멤버를 받아들입니다. 이 과정의 결과로 피벗이 들어갈 완벽한 자리가 자연스럽게 만들어졌습니다.

더 궁금해진 점 / 의문점:
병합 정렬은 메모리를 많이 쓰지만 성능이 보장되고, 퀵 정렬은 메모리 효율적이지만 최악의 경우가 존재합니다. 그렇다면 "메모리도 적게 쓰면서, 최악의 경우에도 O(n log n)을 보장하는 정렬은 없을까?" 라는 의문이 생깁니다.

✨ 마무리하며

분할 정복 기반의 O(n log n) 정렬 알고리즘은 O(n²) 알고리즘에 비해 훨씬 효율적이며, 대용량 데이터 정렬의 기반이 됩니다. 두 알고리즘의 장단점과 내부 동작 원리를 깊이 이해함으로써, 상황에 맞는 기술을 선택할 수 있는 시야를 넓힐 수 있었습니다.