[알고리즘][병합정렬][MergeSort][정렬][파이썬][Python]-정리 및 코드

Merge Sort(병합 정렬)

병합 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나입니다.

 

 

아이디어

병합 정렬은 분할 정복 알고리즘을 사용한다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복은 일반적으로 재귀 호출을 사용하여 구현한다. 병합 정렬은 다음의 과정을 갖는다. 1. 분할: 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다. 2. 정복: 부분 리스트를 정렬한다. 여기서 부분 리스트가 충분히 작지 않다면 재귀 호출을 통해 다시 분할 정복을 한다. 3. 결합: 정렬된 부분 리스트를 하나의 리스트로 병합한다. 

 

병합 정렬 과정

- 추가적인 리스트가 필요하다.

- 각 부분 리스트를 정렬할 때도 병합 정렬을 재귀적으로 호출한다.- 병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합하는 단계이다.

 

 

알고리즘

병합 정렬의 알고리즘은 다음과 같습니다. 정렬 되지 않은 무작위의 숫자가 리스트에 저장되어 있고 오름차순으로 정렬을 한다고 가정합니다.

 

예:  [3, 2, 4, 5, 1, 3] (정렬되지 않은 리스트)

 

2개의 정렬된 리스트를 병합(merge)하는 과정은 다음과 같습니다. 2개의 리스트들의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮깁니다. 둘 중에서 하나가 끝날 때까지 이 과정을 반복합니다. 만약 둘 중 하나의 리스트가 먼저 끝나게 된다면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사합니다. 새로운 리스트를 원래의 리스트로 옮깁니다.

 

결과 1.     [3, 2, 4, ,5, 1, 3]

 

결과 1.1.     [3, 2, 4]     |   [5, 1, 3]

 

결과 1.2.    [3, 2]  | [4]  | [5, 1]   |   [3]

 

결과 1.3.    [3], [2], [4], [5], [1], [3]

 

결과 2.1    [2, 3], [4], [1, 5], [3]

 

결과 2.2    [2, 3, 4], [1, 3, 5]

 

결과 2.3    [1, 2, 3, 3, 4, 5]

 

 

 

특징

장점: 안정적인 정렬 방법( 데이터 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 O(nlogn)으로 동일하다.

 

단점: 만약 레코드를 리스트로 구성하면, 임시 리스트가 필요하다.

       제자리 정렬이 아니다.
       레코드들의 크기가 큰 경우에는 이동 횟수가 많아서 시간 낭비가 발생한다.

 

시간 복잡도 Big(O)

병합 정렬은 시간 복잡도 O(nlogn)으로 항상 균등한 시간을 갖는다. 병합 정렬 알고리즘이 실제 정렬이 이루어지는 순간은 병합(merge)할 때이다. 분할된 리스트들이 이미 정렬되어 있다는 전제 하에 두 개의 리스트를 비교하여 새로운 리스트를 형성하므로 n의 시간 복잡도가 필요하다. 실제 합치는 단계는 O(logn)의 시간을 유지하므로 총 시간 복잡도는 O(nlogn)이 된다.

 

소스코드

unsorted_list=[ 10-i for i in range(10)]
 
def MergeSort(unsorted_list):
    if len(unsorted_list)<=1:
        return unsorted_list
    
    mid=len(unsorted_list)//2
    left=MergeSort(unsorted_list[:mid])
    right=MergeSort(unsorted_list[mid:])
 
    return Merge(left, right)
 
def Merge(left, right):
 
    sorted_list=[]
    i=0
    j=0
 
    while( i<len(left)) and (j<len(right)):
        if left[i]<right[j]:
            sorted_list.append(left[i])
            i+=1
        else:
            sorted_list.append(right[j])
            j+=1
 
    if i<len(left):
        sorted_list+=left[i:]
    if j<len(right):
        sorted_list+=right[j:]
    return sorted_list
 
print(unsorted_list)
print(MergeSort(unsorted_list))