[CS50 4주차] Merge Sort

• 정렬된 여러 개의 데이터 열들을 정렬된 하나의 데이터 열로 만드는 알고리즘

• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식

• 재귀적으로 함수를 호출함.

• 일반적인 방법으로 구현할 경우 이 정렬은 안정 정렬에 속함.

  분할 정복 알고리즘

  분할 정복(divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 분할 정복 방법은 대개 순환 호출을 이용하여 구현

   

 

• 병합 정렬은 데이터 열의 병합(Merge)작업을 이용한 정렬 알고리즘
  • 분할(Divide) 데이터 열을 2개로 나누는 단계
  • 정복(Conquer) 부분 배열 정렬 , 부분배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법 적용
  • 결합(Combine) 데이터열을 병합하는 단계
  • 시간의 상한 $O(nlogn)$

🔽 Merge Sort 의사코드

on input of n elements 
if n < 2
	return
else 
      sort left half of elements
      sort right half of elements
      merge sorted galves

🔽 Merge Sort 구현 코드

//직접 구현해보기 참고 코드 
/* C program for Merge Sort */
#include <stdio.h>
#include <stdlib.h>
 
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
 
    /* create temp arrays */
    int L[n1], R[n2];
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
 
        merge(arr, l, m, r);
    }
}
 
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}
 
/* Driver code */
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    printf("Given array is \n");
    printArray(arr, arr_size);
 
    mergeSort(arr, 0, arr_size - 1);
 
    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

 

Divide 단계에서는 데이터를 반으로 나누고, 나눈 데이터를 다시 반으로 나누는 과정을 반복

더이상 반으로 나눌 수 없으면, 이웃한 데이터들을 나눈 순서의 역순으로 정렬하고 병합해서 하나의 데이터로 만듬

 

🔽 Merge Sort 단점

• 만약 레코드를 배열로 구성하게 되면 임시배열이 필요
• 레코드들의 크기가 큰 경우에는 이동 횟수가 많아지기 때문에 시간적 낭비가 많음

🔽 Merge Sort 장점

• 안정적인 정렬방법
  • 데이터 분포에 영향을 덜 받음 (입력데이터가 무엇이든 정렬되는 시간은 동일)
  • 레코드를 연결리스트(Linked List)로 구성할 경우 링크 인덱스만 변경되므로 데이터의 이동이 적어짐
  • Linked List를 사용한다면, MergeSort는 퀵 정렬을 포함한 다른 어떤 정렬보다 효율적.

🔽Merge Sort 시간복잡도

• 실행 시간의 상한 $O(n\ log \ n)$

  • Divide 단계에서 $O(log \ n)$
  • Combine 단계 $O(n)$

• 실행 시간의 하한 $\Omega(n\ log \ n)$

 

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

Merge Sort Algorithm

Merge Sort Algorithm