병합 정렬 알고리즘 이해: 정렬 알고리즘 마스터를 위한 초보자 가이드-JS 튜토리얼-php.cn

이전 기사에서는 버블 정렬, 선택 정렬, 삽입 정렬 등 다양한 정렬 알고리즘에 대해 배웠습니다. 우리는 이러한 정렬 알고리즘이 구현하기가 매우 쉽지만 대규모 데이터 세트에는 효율적이지 않다는 것을 배웠습니다. 즉, 대규모 데이터 세트 정렬을 처리하려면 더 효율적인 알고리즘이 필요하므로 병합 정렬이 필요합니다. 이번 시리즈에서는 병합 정렬의 작동 방식과 이를 JavaScript로 구현하는 방법을 살펴보겠습니다. 준비됐나요?

Understanding merge sort algorithm: Beginner

병합 정렬 알고리즘이란 무엇입니까?

병합 정렬 알고리즘은 분할 정복 원칙을 따르는 뛰어난 정렬 알고리즘입니다. 인접한 요소를 비교하여 배열을 여러 번 통과하는 선택 정렬 및 버블 정렬과 같은 간단한 알고리즘과 달리 병합 정렬은 보다 전략적인 접근 방식을 취합니다.

분할: 먼저 병합 정렬로 배열을 두 부분으로 나눕니다
정복: 둘째, 각 절반을 재귀적으로 정렬
결합: 마지막으로 정렬된 절반을 다시 병합합니다

이 접근 방식은 대규모 데이터세트를 처리할 때 선택 정렬 및 버블 정렬과 같은 단순한 O(n²) 알고리즘보다 지속적으로 성능이 뛰어납니다.

병합 정렬 알고리즘의 작동 방식

우리는 널리 사용되는 분할 정복 접근 방식을 사용하여 병합 정렬이 작동하는 것을 확인했습니다. 아래는 작동 방식을 시각적으로 나타낸 것입니다.

Understanding merge sort algorithm: Beginner

이제 마법을 보았으므로 위에서 언급한 접근 방식을 사용하여 [38, 27, 43, 3, 9, 82, 10] 배열을 수동으로 정렬하여 병합 정렬 알고리즘이 작동하는 방식을 살펴보겠습니다.

1단계: 나누기

병합 정렬의 첫 번째 단계는 배열을 하위 배열로 나눈 다음 모든 하위 배열에 항목이 하나만 남을 때까지 각 하위 배열을 하위 배열로, 하위 배열을 하위 배열로 나누는 것입니다.

Understanding merge sort algorithm: Beginner

2단계: 다시 병합(정복)

두 번째 단계는 해당 하위 배열을 처음부터 정렬하는 것입니다.

Understanding merge sort algorithm: Beginner

시간 복잡도

병합 정렬은 모든 경우(최적, 평균, 최악)에서 O(n log n) 시간 복잡도를 달성하므로 더 큰 데이터 세트의 경우 O(n²) 알고리즘보다 더 효율적입니다.

이유는 다음과 같습니다.

나누기: 배열을 log n 번 나눕니다(각 나눗셈은 크기를 절반으로 줄입니다)
병합: 각 병합 수준에는 n개의 작업이 필요합니다
합계: n개 작업 × log n 수준 = O(n log n)

비교:

버블 정렬: O(n²)
선택 정렬: O(n²)
병합 정렬: O(n log n)

1,000개 요소 배열의 경우:

O(n²) ≒ 1,000,000회 작업
O(n log n) ≒ 10,000 연산

공간 복잡도

병합 정렬에는 병합 중에 임시 배열을 저장하기 위해 O(n)개의 추가 공간이 필요합니다. 이는 버블 정렬 또는 선택 정렬에 필요한 O(1) 공간보다 크지만 시간 효율성으로 인해 일반적으로 실제로 이러한 절충안을 가치 있게 만듭니다.

JavaScript로 구현

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

로그인 후 복사

병합 기능 분석:

기능 설정:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

로그인 후 복사

병합된 결과를 저장할 빈 배열을 만듭니다
두 입력 배열 모두에 대한 포인터를 초기화합니다
이러한 포인터는 각 배열의 위치를 추적하는 손가락과 같다고 생각하세요

주요 병합 논리:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

로그인 후 복사

두 배열의 요소를 비교합니다
더 작은 요소를 가져와서 결과에 추가합니다
우리가 가져온 배열에서 포인터를 앞으로 이동합니다
덱을 정렬할 때 두 장의 카드 중 작은 것을 선택하는 것처럼

정리 단계:

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

로그인 후 복사

나머지 요소 추가
한 배열이 다른 배열보다 길 수 있으므로 필요합니다
비교해서 남은 카드 모으듯

주요 병합 정렬 기능

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

로그인 후 복사

병합 정렬 분석:

기본 사례:

   if (arr.length <= 1) {
     return arr;
   }

로그인 후 복사

길이가 0 또는 1인 배열을 처리합니다
정의에 따라 이미 정렬되어 있습니다
재귀 중지 지점 역할을 합니다

분할 단계:

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

로그인 후 복사

배열을 두 부분으로 분할
Slice()는 원본을 수정하지 않고 새 배열을 생성합니다
카드 한 벌을 반으로 자르는 것과 같습니다

재귀 정렬 및 병합:

   return merge(mergeSort(left), mergeSort(right));

로그인 후 복사

각 절반을 재귀적으로 정렬
병합 기능을 사용하여 정렬된 절반을 결합
작은 카드 더미를 결합하기 전에 정렬하는 것과 같습니다

예제 연습

[38, 27, 43, 3]이 어떻게 정렬되는지 살펴보겠습니다.

첫 번째 분할:

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

로그인 후 복사

두 번째 분할:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

로그인 후 복사

뒤로 병합:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

로그인 후 복사