정렬 (Sort) - 병합정렬

2024. 7. 16. 22:37·Algorithm
목차
  1. 병합정렬이란

병합정렬이란

병합정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 배열을 반으로 나누어 각각을 정렬한 후 합치는 과정을 반복하여 정렬을 완료하는 알고리즘.

  • 병합정렬은 안정 정렬로, 같은 값의 원소들 간의 순서가 바뀌지 않음.

병합정렬 요약

특징
  • 분할 정복 알고리즘
    병합정렬은 분할 정복(Divide and Conquer) 알고리즘의 일종
    문제를 더 작은 부분 문제로 나누고 각각을 해결한 후 합쳐서 최종 해결책을 만드는 방식.
  • 재귀적 접근
    병합정렬은 재귀적으로 배열을 반으로 나누어 더 이상 나눌 수 없을 때까지 나누고, 나눈 배열을 병합하여 정렬
  • 외부 정렬 가능
    병합정렬은 외부 정렬(external sorting)에 적합.
    대규모 데이터를 정렬할 때, 메모리에 모두 적재할 수 없는 경우에 사용될 수 있음.
  • 균등한 성능
    다른 정렬 알고리즘과 달리, 데이터의 초기 정렬 상태에 상관없이 항상 O(n log n)의 성능을 보장.
    이는 최악의 경우에도 일관된 성능을 제공한다는 의미.
장점 
  • 안정 정렬
    병합정렬은 안정 정렬(stable sort)로, 동일한 값의 원소들이 입력 순서대로 유지. 이는 데이터의 순서를 유지해야 하는 상황에서 중요한 특징.
  • O(n log n) 시간복잡도
    최선, 평균, 최악의 경우 모두 O(n log n)의 시간복잡도를 가짐. 이는 매우 효율적인 시간복잡도.
단점
  • 추가 메모리 공간 필요
    병합정렬은 배열을 나누고 병합하는 과정에서 추가 메모리 공간이 필요.
    이 추가 공간의 복잡도는 O(n).
시간복잡도
  • 최선, 평균, 최악 : O(n log n)
공간복잡도 
  • O(n)

 

자바스크립트 예시

// 병합 함수: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합칩니다.
function merge(left, right) {
    let resultArray = [], leftIndex = 0, rightIndex = 0;

    // 두 배열의 각 요소를 비교하여 작은 값을 결과 배열에 추가합니다.
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            resultArray.push(left[leftIndex]);
            leftIndex++;
        } else {
            resultArray.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // 왼쪽 배열에 남은 요소를 결과 배열에 추가합니다.
    while (leftIndex < left.length) {
        resultArray.push(left[leftIndex]);
        leftIndex++;
    }

    // 오른쪽 배열에 남은 요소를 결과 배열에 추가합니다.
    while (rightIndex < right.length) {
        resultArray.push(right[rightIndex]);
        rightIndex++;
    }

    return resultArray;
}

// 병합 정렬 함수: 배열을 반으로 나누어 재귀적으로 정렬합니다.
function mergeSort(array) {
    if (array.length <= 1) {
        return array;
    }

    const middleIndex = Math.floor(array.length / 2);
    const leftArray = array.slice(0, middleIndex);
    const rightArray = array.slice(middleIndex);

    return merge(mergeSort(leftArray), mergeSort(rightArray));
}

// 테스트
const array = [34, 7, 23, 32, 5, 62];
const sortedArray = mergeSort(array);
console.log(sortedArray);

'Algorithm' 카테고리의 다른 글

동적 프로그래밍 - 메모이제이션  (0) 2024.07.18
정렬 (Sort) - 퀵정렬  (0) 2024.07.16
정렬 (Sort) - 삽입정렬  (0) 2024.07.13
정렬 (Sort) - 선택정렬  (0) 2024.07.12
정렬 (Sort) - 버블정렬  (1) 2024.07.09
  1. 병합정렬이란
'Algorithm' 카테고리의 다른 글
  • 동적 프로그래밍 - 메모이제이션
  • 정렬 (Sort) - 퀵정렬
  • 정렬 (Sort) - 삽입정렬
  • 정렬 (Sort) - 선택정렬
예슬e
예슬e
예슬e
예슬e개발로그
예슬e
전체
오늘
어제
  • 분류 전체보기 (27)
    • 💙 At work in 2024 (0)
    • FrontEnd (7)
      • React (7)
      • Package Manager (0)
      • Build System (0)
      • Transpiler & Bundler (0)
      • Architecture (0)
      • Test (0)
    • BackEnd (2)
    • CS (8)
      • Data Structure (7)
      • Network (1)
    • Algorithm (10)
    • Project (0)
    • Blog (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

리액트 파이버
리액트파이버
타뷸레이션
자바스크립트
useCallback
리렌더링
자바스크립트배열
하노이의탑
useEffect
자료구조
jsx
프론트엔드
메모이제이션
리액트
useState
백엔드
api만들기
알고리즘
리액트딥다이브
재귀

최근 댓글

최근 글

hELLO· Designed By정상우.v4.5.3
예슬e
정렬 (Sort) - 병합정렬
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.