병합 정렬 알고리즘 - Java, C 및 Python 구현

병합 정렬은 가장 효율적인 정렬 알고리즘 중 하나입니다. 각 하위 목록이 단일 요소로 구성될 때까지 목록을 여러 하위 목록으로 나누고 이러한 하위 목록을 정렬된 목록이 되는 방식으로 병합한다는 아이디어를 기반으로 분할 및 정복(Divide and Conquer) 원칙에 따라 작동합니다.

정렬 작업 규칙 병합

Divide and Conquer의 개념에는 세 단계가 포함됩니다.

문제를 여러 하위 문제로 나눕니다.
하위 문제를 해결합니다. 아이디어는 문제를 실제로 해결되는 원자 하위 문제로 나누는 것입니다.
하위 문제의 솔루션을 결합하여 실제 문제의 솔루션을 찾습니다.

따라서 병합 정렬 작업 규칙에는 다음 단계가 포함됩니다.

정렬되지 않은 배열을 각각 단일 요소를 포함하는 하위 배열로 나눕니다.
두 개의 단일 요소 배열의 인접한 쌍을 가져와 병합하여 2개의 요소 배열을 형성합니다.
단일 정렬된 배열을 얻을 때까지 프로세스를 반복합니다.

크기가 'N'인 배열은 각각 크기가 'N/2'인 두 부분으로 나뉩니다. 그런 다음 해당 배열은 단일 요소에 도달할 때까지 더 나뉩니다. 여기서 기본 사례는 하나의 단일 요소에 도달합니다. 기본 케이스에 도달하면 왼쪽 부분과 오른쪽 부분을 병합하기 시작하고 마지막에 정렬된 배열을 얻습니다. 병합 정렬은 각 하위 배열이 단일 요소로 구성될 때까지 반복적으로 배열을 여러 하위 배열로 나누고 이러한 하위 배열을 정렬된 배열이 되는 방식으로 병합합니다.

병합 정렬 알고리즘 흐름

배열={70,50,30,10,20,40,60}

배열을 왼쪽 부분과 오른쪽 부분의 두 부분으로 반복해서 분해합니다. 분할은 중간 요소에서 발생합니다. 단일 요소에 도달할 때까지 나눈 다음 결합을 시작하여 정렬된 배열을 형성합니다.

병합 정렬 구현

Java, C 및 Python에서 병합 정렬 알고리즘을 구현합니다.

1. 자바 구현

package com.journaldev.ds;

public class MergeSort {

	public static void main(String[] args) {

		int[] arr = { 70, 50, 30, 10, 20, 40, 60 };

		int[] merged = mergeSort(arr, 0, arr.length - 1);

		for (int val : merged) {
			System.out.print(val + " ");
		}

	}

	public static int[] mergeTwoSortedArrays(int[] one, int[] two) {

		int[] sorted = new int[one.length + two.length];

		int i = 0;
		int j = 0;
		int k = 0;

		while (i < one.length && j < two.length) {

			if (one[i] < two[j]) {
				sorted[k] = one[i];
				k++;
				i++;
			} else {
				sorted[k] = two[j];
				k++;
				j++;
			}
		}

		if (i == one.length) {

			while (j < two.length) {
				sorted[k] = two[j];
				k++;
				j++;
			}
		}

		if (j == two.length) {

			while (i < one.length) {
				sorted[k] = one[i];
				k++;
				i++;
			}
		}

		return sorted;

	}

	public static int[] mergeSort(int[] arr, int lo, int hi) {

		if (lo == hi) {
			int[] br = new int[1];
			br[0] = arr[lo];

			return br;
		}

		int mid = (lo + hi) / 2;

		int[] fh = mergeSort(arr, lo, mid);
		int[] sh = mergeSort(arr, mid + 1, hi);

		int[] merged = mergeTwoSortedArrays(fh, sh);

		return merged;
	}

}

산출

2. C 구현

#include <stdio.h>

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 the 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); 
    } 
} 
  

void printArray(int A[], int size) 
{ 
    int i; 
    for (i=0; i < size; i++) 
        printf("%d ", A[i]); 
    printf("\n"); 
} 
  
/* Driver program to test above functions */
int main() 
{ 
    int arr[] = {70, 50, 30, 10, 20, 40,60}; 
    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; 
}

산출

3. 파이썬 구현

def merge_sort(unsorted_array):
    if len(unsorted_array) > 1:
        mid = len(unsorted_array) // 2  # Finding the mid of the array
        left = unsorted_array[:mid]  # Dividing the array elements
        right = unsorted_array[mid:]  # into 2 halves

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0

        #  data to temp arrays L[] and R[]
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                unsorted_array[k] = left[i]
                i += 1
            else:
                unsorted_array[k] = right[j]
                j += 1
            k += 1

        # Checking if any element was left
        while i < len(left):
            unsorted_array[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            unsorted_array[k] = right[j]
            j += 1
            k += 1


# Code to print the list
def print_list(array1):
    for i in range(len(array1)):
        print(array1[i], end=" ")
    print()


# driver code to test the above code
if __name__ == '__main__':
    array = [12, 11, 13, 5, 6, 7]
    print("Given array is", end="\n")
    print_list(array)
    merge_sort(array)
    print("Sorted array is: ", end="\n")
    print_list(array)

산출

병합 정렬 시간 및 공간 복잡성

1. 공간 복잡도

보조 공간: O(n) 제자리 정렬: 알고리즘 없음: 분할 정복

2. 시간 복잡도

Merge Sort는 재귀적 알고리즘으로 시간복잡도는 다음과 같은 재귀 관계식으로 표현할 수 있다. T(n) = 2T(n/2) + O(n) 위 재귀의 해는 O(nLogn)입니다. 크기 N의 목록은 최대 Logn 부분으로 나뉘며 모든 하위 목록을 단일 목록으로 병합하는 데 O(N) 시간이 걸립니다. 이 알고리즘의 최악의 경우 실행 시간은 O(nLogn)입니다. 최상의 경우 시간 복잡도: O(n*log n) 최악의 경우 시간 복잡도: O(n*log n) 평균 시간 복잡도: O(n*log n) MergeSort의 시간 복잡도는 3가지 경우 모두에서 O(n*Log n)입니다. , 평균 및 최고) mergesort는 항상 배열을 두 개의 절반으로 나누고 두 개의 절반을 병합하는 데 선형 시간이 걸립니다. 추가 자료:

Merge Sort Wikipedia 페이지
자바의 버블 정렬
자바의 삽입 정렬