Python 병합정렬 알고리즘

Python 병합정렬 알고리즘

테스트를 보는 곳이나 면접에서도 직접 구현해보라고 하는 구현방법들이다.

병합 정렬은 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘.

 

예를 들어서

A - 1, 2, 3, 5

B - 4, 6, 7, 8

이 두 집합을 합쳐가면서 정렬하는 방법

 

병합

# 병합

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        # index값이 커질 때 즉 한 바퀴 다 돌 때 탈출조건
        if array1[array1_index] < array2[array2_index]:
        # array1[0]과 array2[0]의 비교, 즉 1과 4의 비교
            result.append(array1[array1_index])
        # 만약 array1이 작다면 array1의 0번쨰 인덱스를 빈리스트 result에 붙인다.
            array1_index += 1
        # array1은 한번 갔으니, index를 +1해준다. 그럼 다음에 비교할떈 array1[1]이 되겠지.
        else:
            result.append(array2[array2_index])
            array2_index += 1
        # 아닐 경우는 그 반대로 해준다.

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1
      #만약에 array1_index값이 array1의 범위와 똑같아 진다면, 즉 한 바퀴 다 돌았는데
      # array2는 아직 전부 못돌았으면, 그냥 남은 모든 array2의 리스트를 result에 붙여넣어준다.
      # array2_index가 1씩 커지다 결국 while문 탈출

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1
    # 이건 그 반대의 경우다. 즉 array1이 범위를 다 못돌았을 때

    return result
   # 정렬한 result 값을 출력해준다.


print(merge(array_a, array_b))

[1 , 2, 3, 5]

[4, 6, 7, 8]

 

먼저 1과 4를 비교하고

 

1 < 4 이므로 1을 빈리스트 C에 넣는다.

 

그렇게 5까지 반복하다 5가 작아지면 4가 5보다 작으므로 이번엔 4를 C에넣는다.

 

그 후엔 5와 6을 비교하고 5를 C에 넣는다.

 

남은 6, 7, 8 은 하나씩 C에 추가해준다.

---

병합정렬

# 병합정렬
array = [5, 3, 2, 1, 6, 8, 7, 4]


def merge_sort(array): # N만큼의 시간복잡도
    if len(array) <= 1:
        return array
        # 만약에 [5]가 들어오면 더 이상 정렬을 해야될 필요가 없다. 이미 정렬된 상태니까
    mid = len(array) // 2
    left_array = merge_sort(array[:mid]) #재귀의 방식으로 계속 쪼갠다.
    #0부터 시작해서 mid까지, 반을 쪼개서 왼쪽에 있는것만 반환됨
    right_array = merge_sort(array[mid:])
    #오른쪽 절반

    return merge(left_array, right_array)
    #바로 밑의 merge 함수를 이용해서 합쳐줌 (병합 해 줌)


def merge(array1, array2):
    # len(array1) + (array2)
    # = O(N) 시간
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge_sort(array))  # [1, 2, 3, 4, 5, 6, 7, 8] 가 되어야 합니다!

분할 정복의 개념

 

분할 정복은 문제를 작은 2개의 문제로 분리하고, 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략.

 

예를 들어 [5. 4] 라는 배열이 있다면,

 

이 배열을 [5]와 [4]를 가진 각각의 배열로 작은 2개의 문제로 분리해서 생각하는 것.

 

이 둘을 합치면서 정렬하면 결국 전체의 정렬된 리스트를 볼 수 있다.

 

 

MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))

 

0부터 N까지 정렬한걸 보기 위해서는 0부터 N/2까지 정렬한 것과 N/2부터 N까지 정렬한걸 합치면 된다는 개념.