[파이썬][알고리즘] 병합 정렬

병합 정렬 (merge sort)

• 재귀 함수를 함수를 이용한 정렬이다.

  • 리스트를 자른다.
  • 각 데이터를 두개씩 묶어서 정렬한다.
  • 이를 반복하여 정렬을 한다.

• 참고 주소: https://visualgo.net/en/sorting

데이터가 4개 일 때

  

• 두 부분으로 나눈다

  

• 또다시 각각 두 부분으로 나눈다

 

• 각각의 부분을 정렬해서 합친다

  

• 두 번째 부분의 0번 인덱스를 첫 번째 부분의 숫자와 비교하여 정렬한다.

  

• 이것을 반복한다.

  

알고리즘 구현

def merge(part_a, part_b):
    merged = list()
    a_index, b_index = 0, 0

    # 데이터가 아직 남아있을 때
    while len(part_a) > a_index and len(part_b) > b_index:
        if part_a[a_index] > part_b[b_index]:
            merged.append(part_b[b_index])
            b_index += 1
        else:
            merged.append(part_a[a_index])
            a_index += 1

    # part_a만 남아있을 때
    while len(part_a) > a_index:
        merged.append(part_a[a_index])
        a_index += 1

    # part_b만 남아있을 때
    while len(part_b) > b_index:
        merged.append(part_b[b_index])
        b_index += 1

    return merged

def divide_merge(num_list):
    if len(num_list) <= 1:
        return num_list
    part_a = divide_merge(num_list[:int(len(num_list) / 2)])
    part_b = divide_merge(num_list[int(len(num_list)/ 2):])
    return merge(part_a, part_b)

import random
num_list = random.sample(range(100), 10)

num_list

[23, 54, 57, 12, 55, 65, 17, 95, 49, 33]

divide_merge(num_list)

[12, 17, 23, 33, 49, 54, 55, 57, 65, 95]