Computer Science/알고리즘

[알고리즘] 병합 정렬 (Merge Sort)

2023. 6. 17. 00:37
목차
  1. 병합 정렬 (Merge Sort) = 합병 정렬
  2. 병합 정렬 기본 프로세스
  3. 장점
  4. 단점
  5. 퀵 정렬과의 차이점
  6. 병합 정렬 구현

병합 정렬 (Merge Sort) = 합병 정렬

  • 분할 정복(Divide and Conquer) 방식을 사용하여 정렬을 수행하는 알고리
  • 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 크기를 비교하여 정렬하면서 합병하는 방식
  • 시간복잡도 : O(nlogn)
  • 공간복잡도 : O(n)

병합 정렬 기본 프로세스

  1. 분할(Divide) : 정렬할 배열을 반으로 나눈다. 이를 위해 배열의 중간 지점을 찾고, 중간을 기준으로 왼쪽과 오른쪽 부분 배열로 나눈다. O(logn)
  2. 정복(Conquer) : 나누어진 부분 배열에 대해 재귀적으로 정렬을 수행한다. 이 단계에서는 분할된 부분 배열이 단일 원소로 이루어질 때까지 계속해서 재귀 호출을 수행한다.
  3. 병합(Merge) : 정렬된 부분 배열을 병합하여 전체 배열을 생성한다. 병합할 때는 두 부분 배열을 비교하면서 작은 순서대로 원소를 선택하여 새로운 배열에 넣는다. O(n)

장점

  • 안정적인 정렬이다
    • 동일한 값에 대해 상대적인 순서가 보장된다.

  • 성능이 예측 가능하다.
    • 최악의 경우에도 시간 복잡도 O(nlogn)을 보장한다. 따라서 입력 데이터의 분포나 순서에 크게 영향을 받지 않고 일관된 성능을 보인다.

  • 배열 뿐만 아니라 연결 리스트에도 적용할 수 있다.
    • 연결 리스트의 경우 원소를 분할하고 병합하는 과정이 배열에 비해 간다하며, 메모리 관리에 유리한 경우가 있다.

단점

  • 추가적인 메모리 공간이 필요하다.
    • 재귀 호출 및 병합할 때 임시 배열을 사용하기 때문에 정렬할 배열과 같은 크기의 추가적인 메모리 공간이 필요하다. 

퀵 정렬과의 차이점

  • 분할 방식 : 병합 정렬은 분할 과정에서 배열을 반으로 나누고 재귀적으로 부분 배열을 정렬한 후, 정렬된 부분 배열을 병합하여 전체 배열을 생성한다. 퀵 정렬은 분할 과정에서 피벗을 선택하고, 피벗을 기준으로 작은 값은 왼쪽에 위치시키고 큰 값을 오른쪽에 위치시킨다. 이후 재귀적으로 각 부분 배열을 정렬한다.
  • 최적화 가능성 : 일반적인 병합 정렬 구현 방식에서는 병합 과정이 추가 작업 없이 수행되기 때문에 최적화를 할 수 있는 여지가 적다. 퀵 정렬은 피벗 선택 방식을 변경하여 최적화할 수 있는 경우가 있다.

병합 정렬 구현

    // 합병 정렬을 수행하는 메서드
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            // 배열이 null이거나 크기가 1 이하이면 정렬할 필요가 없으므로 리턴
            return;
        }

        // 임시 배열 생성
        int[] temp = new int[arr.length];

        // 합병 정렬 수행
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    // 배열을 분할하고 병합하는 재귀적인 메서드
    private static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            // 배열을 반으로 분할하여 재귀 호출로 정렬
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);

            // 분할된 배열을 병합
            merge(arr, temp, left, mid, right);
        }
    }

    // 두 개의 정렬된 부분 배열을 병합하는 메서드
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // 임시 배열에 정렬된 값들을 복사
        for (int i = left; i <= right; i++) {
            temp[i] = arr[i];
        }

        int i = left;   // 왼쪽 부분 배열의 인덱스
        int j = mid + 1;    // 오른쪽 부분 배열의 인덱스
        int k = left;   // 정렬된 배열에 값을 삽입할 인덱스

        // 왼쪽 부분 배열과 오른쪽 부분 배열을 비교하며 작은 값을 차례로 삽입
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
            k++;
        }

        // 남은 값들을 삽입
        while (i <= mid) {
            arr[k] = temp[i];
            i++;
            k++;
        }

        while (j <= right) {
            arr[k] = temp[j];
            j++;
            k++;
        }
    }
저작자표시

'Computer Science > 알고리즘' 카테고리의 다른 글

[알고리즘] 기수 정렬 (Radix Sort) & 계수 정렬 (Counting Sort)  (0) 2023.06.23
[알고리즘] 힙 정렬 (Heap Sort)  (0) 2023.06.17
[알고리즘] 퀵 정렬 (Quick Sort)  (0) 2023.06.17
[알고리즘] 삽입 정렬 (Insertion Sort)  (0) 2023.06.10
[알고리즘] 선택 정렬 (Selection Sort)  (0) 2023.06.10
  1. 병합 정렬 (Merge Sort) = 합병 정렬
  2. 병합 정렬 기본 프로세스
  3. 장점
  4. 단점
  5. 퀵 정렬과의 차이점
  6. 병합 정렬 구현
'Computer Science/알고리즘' 카테고리의 다른 글
  • [알고리즘] 기수 정렬 (Radix Sort) & 계수 정렬 (Counting Sort)
  • [알고리즘] 힙 정렬 (Heap Sort)
  • [알고리즘] 퀵 정렬 (Quick Sort)
  • [알고리즘] 삽입 정렬 (Insertion Sort)
dbssk
dbssk
dbssk
K.Back-end
dbssk
  • 분류 전체보기 (220)
    • 끄적 (0)
    • TIL (8)
      • Trouble Shooting (1)
    • Programmers (94)
      • Lv.0 (29)
      • Lv.1 (40)
      • Lv.2 (25)
    • 백준 (15)
    • 구름 (0)
    • Computer Science (79)
      • 컴퓨터 구조 (3)
      • Operating System (18)
      • 알고리즘 (9)
      • 자료구조 (11)
      • Database (10)
      • Network (8)
      • Web (12)
      • Design Pattern (8)
    • Spring (2)
    • Languages (13)
      • Java (13)
    • 북 스터디 (9)
      • 스프링 부트 핵심 가이드 (9)
      • 자바 코딩 인터뷰 완벽 가이드 (0)
    • 프론트엔드 (0)

인기 글

최근 글

태그

  • stack
  • 코딩테스트
  • 백엔드공부
  • 스택
  • 프로그래머스
  • LV.2
  • 해시
  • 백준
  • 개발자취준
  • 배열
  • 개발자포트폴리오
  • java
  • 개발자이력서
  • hash
  • spring
  • 백엔드스쿨
  • 자료구조
  • Lv.0
  • LV.1
  • 개발자취업
hELLO · Designed By 정상우.
dbssk
[알고리즘] 병합 정렬 (Merge Sort)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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